Skip to content
TheChatArchiveThe Chat Archive
DeepSeekDeepseek v3.2· deepseekHugging Face Frontier Reasoning Traces

This week Arkady wanted to cook some pancakes (to follow ancient traditions) and make a…

  1. User

    This week Arkady wanted to cook some pancakes (to follow ancient traditions) and make a problem about that. But then he remembered that one can't make a problem about stacking pancakes without working at a specific IT company, so he decided to bake the Napoleon cake instead.

    To bake a Napoleon cake, one has to bake n dry layers first, and then put them on each other in one stack, adding some cream. Arkady started with an empty plate, and performed the following steps n times:

    • place a new cake layer on the top of the stack;
    • after the i-th layer is placed, pour a_i units of cream on top of the stack.

    When x units of cream are poured on the top of the stack, top x layers of the cake get drenched in the cream. If there are less than x layers, all layers get drenched and the rest of the cream is wasted. If x = 0, no layer gets drenched.

    The picture represents the first test case of the example.

    Help Arkady determine which layers of the cake eventually get drenched when the process is over, and which don't. Input

    Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 20 000). Description of the test cases follows.

    The first line of each test case contains a single integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the number of layers in the cake.

    The second line of each test case contains n integers a_1, a_2, …, a_n (0 ≤ a_i ≤ n) — the amount of cream poured on the cake after adding each layer.

    It is guaranteed that the sum of n over all test cases does not exceed 2 ⋅ 10^5.

    Output

    For each test case, print a single line with n integers. The i-th of the integers should be equal to 1 if the i-th layer from the bottom gets drenched, and 0 otherwise.

    Example

    Input

    3 6 0 3 0 0 1 3 10 0 0 0 1 0 5 0 0 0 2 3 0 0 0

    Output

    1 1 0 1 1 1 0 1 1 1 1 1 0 0 1 1 0 0 0

  2. DeepSeek Assistant

    We need to solve the problem: we have a process of adding layers from bottom to top? Actually careful: They start with an empty plate, and perform steps n times: each step, place a new cake layer on the top of the stack. So initially empty, then place first layer => stack has layer 1 (bottom). Then pour a1 cream on top; it drenches top a1 layers (i.e., from the top down). After that, place second layer on top => now stack has layers: bottom layer 1, then layer 2 on top. Then pour a2 cream; drenches top a2 layers, etc. After all n steps, we want to know for each layer (from bottom to top? The output: "i-th of the integers should be equal to 1 if the i-th layer from the bottom gets drenched, and 0 otherwise." So we need to output for layers in order from bottom (layer 1) to top (layer n) whether they are eventually drenched (after all n steps). Cream can drench layers multiple times, but being drenched once suffices to be drenched.

    So we need to simulate the effect of all pours after each addition.

    Constraints: total n up to 2e5 across test cases, t up to 20000. So O(n) per test case, maybe O(n log n) is fine but likely O(n) needed.

    We have to process n actions: each action: add a new layer to top, then pour a_i cream that drenches the top a_i layers.

    If we think backwards: The final state of layers after all operations. Since we only care whether a layer is drenched at any point, we can consider the effect of pours that occur after a layer has been placed. Because when a layer is placed, later pours (with later indices) can also drench it if it is within the top x layers at that later time. So each layer can be drenched by pours at times >= its index (i.e., after it's added).

    We can simulate forward with a data structure that supports: add a new element (layer) to the top; then mark the top a_i layers as drenched. But we need to output for each layer (by its position from bottom) whether it got drenched at any point. Could simulate using a stack with flags. Since we only need final drench status for each layer, we could process backward: consider the last pours that cover layers. Because if we go backwards, we can track the "coverage" from future pours.

    Standard solution: Iterate from n down to 1, maintaining a variable 'cream' representing how many layers from the current position (starting from the top) are drenched due to pours that happened later? Actually let's think.

    Suppose we have an array ans[1..n] initially 0. We process i from n down to 1. Let current cream coverage be a variable 'cover' (or 'remaining') that indicates how many layers from the current index upward (i.e., layers with index >= i) are drenched due to pours that we have processed so far (i.e., pours with index >= i). When we process step i (the step where layer i was added and then a_i poured), we need to consider the effect of that pour on layers. But if we go backward, we encounter the pour at step i after we have already considered later pours. However, the pour at step i affects layers that are among the top a_i layers at that moment (i.e., layers with indices from current top (which is i, because after adding layer i, the stack has layers 1..i) down to i - a_i + 1? Actually careful: At step i, after placing layer i (the newest layer), the stack has layers 1 (bottom) to i (top). Then we pour a_i units of cream on top, which drenches the top a_i layers. That means it drenches layers i, i-1, ..., i - a_i + 1 (if a_i > 0). If a_i is larger than i, it drenches all layers (1..i) and excess wasted.

    So this pour directly drenches a contiguous suffix of the current stack (from top down) of length min(a_i, i). So it drenches layers from max(1, i - a_i + 1) to i.

    Thus each pour is essentially a range update on indices from L = max(1, i - a_i + 1) to i, marking them as drenched. And these updates are applied in chronological order i=1..n. The final state is the OR of all these updates. So the problem reduces to: given n intervals (each is [max(1, i - a_i + 1), i]) (or [i - a_i + 1, i] but if less than 1 then start at 1), we need to output for each index j whether it was covered by at least one interval.

    But note: The intervals are not independent because a_i can be larger than i, but we handle as L=1. So it's range cover. We can just compute prefix sums of coverage? Since total n sum is 2e5, we could for each test case create an array diff of size n+2, and for each i, do diff[L] += 1, diff[i+1] -= 1. Then prefix sum to find coverage count. Then answer is 1 if coverage>0 else 0. That is O(n) per test case. That seems straightforward. But careful: The intervals are exactly the drench ranges at each step? But does the cream only drench the top a_i layers at that moment, which are exactly the latest layers? Yes. And that matches the interval [i - a_i + 1, i] (with bottom boundary at 1). So we can compute that.

    But is it exactly that? Let's test with example.

    Example 1: n=6, a = [0,3,0,0,1,3] Compute intervals:

    i=1: a1=0 => drenches top 0 => no layer? Actually a1=0 => no layer drenched. So interval? L = max(1, 1-0+1)= max(1,2)=2? That's not correct because if a_i=0, it should drench no layers, so interval empty. So we should treat a_i=0 as no coverage. So we can simply skip. For a_i>0, L = max(1, i - a_i + 1). But careful: For a_i=0, i - a_i +1 = i+1 > i, so L > i, so we can skip any intervals with L > i.

    So more precisely, the range is from max(1, i - a_i + 1) to i, but only if i - a_i + 1 <= i i.e., a_i >= 1. So we can compute L = i - a_i + 1; if L <= i (i.e., a_i >= 1) then effective L = max(1, L). But if L < 1, then it's from 1 to i. So we can handle with diff array: add 1 at max(1, i - a_i + 1), subtract 1 at i+1, only if a_i > 0 and L<=i, which is always true if a_i>0 because i - a_i + 1 <= i.

    But what about a_i > i? Then i - a_i + 1 <= 0, so L=1. So range [1, i]. That's fine.

    Thus we can simply for each i with a_i > 0: L = max(1, i - a_i + 1); diff[L] += 1; diff[i+1] -= 1.

    Then compute prefix sum over indices 1..n: coverage[j] = sum_{k=1..j} diff[k]. Then ans[j] = 1 if coverage[j] > 0 else 0.

    Let's test on examples.

    Example 1: n=6, a: [0,3,0,0,1,3] i=1: a1=0 skip. i=2: a2=3 => L = max(1, 2-3+1)= max(1,0)=1; range [1,2]; diff[1]++, diff[3]--. i=3: a3=0 skip. i=4: a4=0 skip. i=5: a5=1 => L = max(1, 5-1+1=5) => 5; range [5,5]; diff[5]++, diff[6]--. i=6: a6=3 => L = max(1, 6-3+1=4) => 4; range [4,6]; diff[4]++, diff[7]-- (7 out of bounds but okay).

    Now compute diff array size maybe 8: Initialize diff[1..7]=0. After i=2: diff[1]=1, diff[3]=-1. i=5: diff[5]=1, diff[6]=-1. i=6: diff[4]=1, diff[7]=-1. Now prefix sum: index1: 1 => coverage=1 => ans1=1 index2: + diff[2]=0 => coverage still 1 => ans2=1 index3: + diff[3]=-1 => coverage 0 => ans3=0 index4: + diff[4]=1 => coverage 1 => ans4=1 index5: + diff[5]=1 => coverage 2 => ans5=1 index6: + diff[6]=-1 => coverage 1 => ans6=1 Output: 1 1 0 1 1 1 matches.

    Example 2: n=10, a: [0,0,0,1,0,5,0,0,0,2] Compute intervals: i=1:0 skip i=2:0 skip i=3:0 skip i=4:1 => L= max(1,4-1+1=4) =>4; range[4,4]; diff[4]++, diff[5]--. i=5:0 skip i=6:5 => L= max(1,6-5+1=2) =>2; range[2,6]; diff[2]++, diff[7]--. i=7:0 skip i=8:0 skip i=9:0 skip i=10:2 => L= max(1,10-2+1=9) =>9; range[9,10]; diff[9]++, diff[11]-- (out of bounds ignore after n) Now diff: index2:1, index4:1, index5:-1, index7:-1, index9:1. Add: prefix sums: 1:0 2:1 => ans2=1 3: still 1? after index3 diff[3]=0 =>1 => ans3=1 4: + diff[4]=1 => 2 => ans4=1 5: + diff[5]=-1 => 1 => ans5=1 6: + diff[6]=0 => 1 => ans6=1 7: + diff[7]=-1 => 0 => ans7=0 8: 0 => ans8=0 9: + diff[9]=1 => 1 => ans9=1 10: + diff[10]=0 => 1 => ans10=1 Index1: 0 => ans1=0 Thus output: 0 1 1 1 1 1 0 0 1 1 matches.

    Example 3: all zeros => no intervals => all zeros => matches.

    Thus the problem reduces to range addition via difference array. Complexity O(n) per test case, total O(N) sum of n.

    But wait, is it always true that the effect of a pour is exactly marking that range? Let's double-check the process: When we pour a_i units on top, it drenches the top a_i layers. However, does it drench layers that are already drenched? Yes but that's fine. And does the cream only affect the top layers at that moment? Exactly. So it's exactly a range on the current stack (ordered from bottom to top, indices 1..i). So marking that range is correct. However, there is nuance: The stack changes over time; later layers are added after earlier pours. So a later pour may drench earlier layers only if they are among the top a_j layers at that later time. That is exactly captured by intervals as above: at step j, the top a_j layers are the layers from index j - a_j + 1 to j (provided a_j > 0). So each pour covers a suffix of the current sequence of layers. So the union of all these suffixes across j yields the final drenched set. So yes, we can compute the union via difference array.

    But careful: Could there be an issue where a pour drenches layers that are not contiguous due to some layers being already drenched? No, it's always contiguous because it's the top a_j layers of the stack, which is a contiguous block from the top downward. So it's a suffix.

    Thus the difference array solution works.

    Now consider constraints: sum n <= 2e5, t up to 20000. So we must handle many small test cases efficiently. Using vector of size n+2 per test case is fine. Might also use a global array and reset but easier to allocate per test case.

    Edge cases: a_i can be up to n. L = i - a_i + 1 may be negative, so max with 1.

    Implementation details:

    • Read t.
    • For each test case:
      • Read n.
      • Read list a of length n (1-indexed or 0-indexed).
      • Create diff array of size n+2 (or n+5) initialized to 0.
      • For i from 1 to n:
        • if a[i-1] > 0: L = i - a[i-1] + 1; if L < 1: L = 1; // Actually we can L = max(1, i - a_i + 1) diff[L] += 1; diff[i+1] -= 1;
      • Then compute prefix sum cur = 0; For j from 1 to n: cur += diff[j]; ans[j] = (cur > 0 ? 1 : 0);
      • Print ans with spaces, newline after.

    We must ensure that i+1 may be n+1, which is within diff size (size n+2). So ok.

    Time complexity O(total n). Memory O(n) per test case.

    Let's test with some random small cases by brute force simulation to ensure correctness.

    I'll also think about alternative solution: reverse iteration with cream variable.

    But diff array approach is simpler.

    But we should be careful: The intervals are indeed independent as we treat them as range updates. However, could there be a scenario where a pour affects layers that are not exactly a suffix because some layers might have been removed? No, layers never removed. So stack only grows. So the indices of layers are fixed: layer added at step i always remains at position i from bottom (since we never remove layers). So it's a static array; we just apply range marks on the positions that exist at that time. That's fine.

    Thus solution is correct.

    But wait: The problem statement says: "When x units of cream are poured on the top of the stack, top x layers of the cake get drenched in the cream. If there are less than x layers, all layers get drenched and the rest of the cream is wasted." This matches our range from L = max(1, i - x + 1) to i, but if x > i then L = 1. So yes.

    Now implement.

    One more nuance: Could a_i be larger than n? Input says 0 ≤ a_i ≤ n, so fine.

    Thus solution is straightforward.

    However, is there any hidden trick? Perhaps they expect a solution with stack simulation or a "sweep from top" with cream variable. But the difference array works.

    Double-check using small example: n=1, a1=1 => after adding layer1, pour 1 cream drenches top1 => layer1 drenched. Our method: i=1, a1=1>0, L = max(1,1-1+1=1) => diff[1]++, diff[2]-- => coverage[1]=1 => ans=1. Good.

    n=1, a1=0 => no diff => ans=0.

    n=2, a = [2,0] => step1: after layer1, pour 2 drenches all layers (only layer1) (so layer1 drenched). step2: add layer2, pour 0 => no effect. So layers: 1 drenched, 2 not. Our method: i=1 a1=2>0, L= max(1,1-2+1=0)=1 => diff[1]++, diff[2]--. i=2 skip. prefix: j1:1 => drenched; j2: cur after adding diff[2] is 0 => not. Good.

    n=2, a = [0,2] => step1: no drench; step2: after layer2, pour2 => drenches top2 layers: layer2 and layer1 => both drenched. Our method: i=2 a2=2>0, L = max(1,2-2+1=1) =>1, diff[1]++, diff[3]-- => coverage: 1->1,2->1 => both 1. Good.

    Thus solution works.

    Edge cases: large a_i values may cause L to be 1, diff[1]++ many times, but that's fine.

    Now we need to output each test case's answer in a line with spaces and trailing space? The example output has trailing space: "1 1 0 1 1 1 " with space after last number? In typical Codeforces style, they don't mind trailing spaces. But we can format without trailing space: print numbers separated by space, but not add after last. Usually fine.

    Implementation: In Python, we can read fast because total input size up to 2e5 numbers plus t etc, so using sys.stdin.read may be faster.

    But I'll write in Python as it's simple.

    Let's implement:

    import sys

    def main(): data = sys.stdin.read().strip().split() it = iter(data) t = int(next(it)) out_lines = [] for _ in range(t): n = int(next(it)) a = [int(next(it)) for __ in range(n)] diff = [0] * (n + 2) # index 1..n+1 for i in range(1, n+1): x = a[i-1] if x > 0: L = i - x + 1 if L < 1: L = 1 diff[L] += 1 diff[i+1] -= 1 cur = 0 ans = [] for j in range(1, n+1): cur += diff[j] if cur > 0: ans.append('1') else: ans.append('0') out_lines.append(' '.join(ans)) sys.stdout.write('\n'.join(out_lines))

    if name == 'main': main()

    That should be fine.

    But consider if a_i could be 0, we skip. The diff array size is n+2. Works.

    Time complexity: O(total n). Memory: O(n) per test case, but we allocate and discard.

    Now check for potential overflow: diff values are integers up to n (number of intervals), but n ≤ 2e5, int fine.

    Thus solution done.

    But wait, there might be a nuance: The problem might have intended a different interpretation: The process is: we place a new layer, then pour a_i units of cream. But the cream drenches the top a_i layers of the current stack. That's what we used.

    We are asked: which layers eventually get drenched (i.e., at some point during the whole process). So union.

    Our method works.

    Thus we can present solution.

    However, I recall that typical solution for "Napoleon cake" (Codeforces problem) uses backward sweep with cream variable. But diff array is also valid and simpler.

    But is there any subtlety that the intervals are not independent because the cream may also cause some layers to become drenched that then affect subsequent pours? No, because the drench status doesn't affect which layers get drenched by later pours. The later pours always drench the top a_j layers regardless of whether they are already drenched. So union is fine.

    Thus solution stands.

    Now double-check with some random test via brute force simulation to ensure correctness. I'll do a mental check:

    Case: n=3, a=[1,1,1]. Process: Step1: add layer1, pour1 => drench layer1. Step2: add layer2, pour1 => drench top1: layer2. Step3: add layer3, pour1 => drench top1: layer3. Final: all drenched. Our intervals: i=1: [1,1] i=2: [2,2] i=3: [3,3] Union all => each covered => 1,1,1.

    Case: a=[2,0,1]. Step1: add layer1, pour2 => drench layer1 (only layer1 exists, so all => layer1 drenched) Step2: add layer2, pour0 => none. Step3: add layer3, pour1 => drench top1: layer3. Final: layer1 drenched, layer2 not, layer3 drenched. Our intervals: i=1: [1,1] (since L = max(1,1-2+1=0)=1) i=3: [3,3] (L= max(1,3-1+1=3)=3) Union: 1,0,1.

    Case: a=[3,1,2] n=3. Step1: add layer1, pour3 => drench all layers (only layer1) => layer1 drenched. Step2: add layer2, pour1 => drench top1: layer2. Step3: add layer3, pour2 => drench top2: layer3 and layer2 (since top2 are layers3 and2) => both drenched (layer2 already). So final all drenched. Our intervals: i=1: [1,1] i=2: [2,2] (L= max(1,2-1+1=2)=2) i=3: [2,3] (L= max(1,3-2+1=2)=2) Union: layer1 covered by i1, layer2 covered by i2 or i3, layer3 covered by i3. => all 1. Works.

    Case: a=[0,2,0] n=3. Step1: no. Step2: after layer2, pour2 => drenches top2: layer2 and layer1. Step3: add layer3, pour0 => none. Final: layers1,2 drenched, layer3 not. Intervals: i=2: [1,2] (L=max(1,2-2+1=1)) Union: 1,1,0.

    Good.

    Thus solution is correct.

    Now think about memory and speed: diff array of size n+2 each test case, with sum n <= 2e5, so total memory across all test cases not huge.

    So we can implement.

    But consider Python performance: we have to process up to 20000 test cases, many of which could be n=1. The overhead of creating many small arrays is fine. However, we need to ensure that reading input is fast; using sys.stdin.read and parsing all numbers at once is fine.

    Now ensure output formatting: The example shows each test case's answer line with a trailing space, but that's not required. We'll output without trailing space.

    Now I think it's done.

    We should also note that we could also solve by backward iteration: keep a variable "cream" representing how many layers from current index to the top are drenched due to later pours. At step i from n down to 1, we consider a_i: it says that when we poured at that step, it drenches the top a_i layers. But when processing backward, we need to incorporate that pour's effect on earlier layers? Actually backward solution: maintain a variable "cover" initially 0. For i from n down to 1: cover = max(cover, a_i) ??? No, let's derive.

    Alternate approach: When we process from top down, we can simulate how far the cream from later steps extends. But let's not complicate.

    Our diff array solution is simpler and less error-prone.

    Now let's consider potential pitfalls: The intervals are inclusive on both ends. Our diff method includes i. We add +1 at L and -1 at i+1. That's correct for range [L, i] inclusive.

    Also, we need to be careful with 1-indexing. Use 1-index in diff.

    Now code in Python as above.

    One more nuance: When a_i is huge, L may be 1, and we add diff[1]++ and diff[i+1]--. Works.

    So we'll produce final answer.

    But wait, I recall a Codeforces problem named "Napoleon Cake" that had many solutions using a stack or reverse sweep. However, many participants used difference array. So it's a known approach.

    Now we should test with random brute force: I'll write a small script mentally to simulate process for small n and compare.

    But for peace of mind, let's think about correctness more formally.

    Define layers indices 1..n, where layer i is added at step i (i-th step). At step i, after adding layer i, we apply a range update: for j in [max(1, i - a_i + 1), i], set drenched[j] = True (or OR). The final drenched status is OR over all i. That's exactly what we compute with difference array (cumulative sum > 0).

    Thus solution is straightforward.

    Now answer.

    One more thought: The problem statement says "top x layers get drenched". If x=0, none. Yes.

    Thus done.

    Implementation details:

    We'll use Python's fast I/O. Alternatively, we can use sys.stdout.write.

    Now I think we can output final solution.

    But I'm also thinking: Could there be a scenario where a_i is less than 1? No.

    Thus final answer.

    Now we need to produce final ChatGPT answer: Explanation and code.

    Will provide explanation of reduction to range updates, using difference array, and complexity.

    Let's write final answer. ### Solution Explanation

    We can think of the process as performing a sequence of range updates on the layers. At step (i) (1-indexed), after placing layer (i) on top, the cream drenches the top (a_i) layers. The current stack consists of layers (1, 2, \dots, i) (from bottom to top). Therefore, the drenched layers form the suffix from (\max(1, i - a_i + 1)) to (i) (if (a_i > 0)). If (a_i = 0), nothing happens.

    The final status of each layer is the logical OR of all such updates – a layer is drenched if it belongs to at least one of these intervals.

    Thus the problem reduces to: given (n) intervals (possibly empty), mark all positions covered by at least one interval. This can be solved efficiently using a difference array:

    • Create an array diff of size (n+2) (1-indexed) initialized with zeros.
    • For each (i) from (1) to (n) with (a_i > 0):
      • (L = \max(1, i - a_i + 1))
      • diff[L] += 1
      • diff[i+1] -= 1
    • Compute the prefix sum over diff; for position (j) the cumulative sum cur equals the number of intervals covering (j). Then the answer for layer (j) is 1 if cur > 0, else 0.

    This method works in (O(n)) time per test case, and total (O(\sum n)) over all test cases, which is acceptable given the limits.

    Complexity

    • Time: (O(\sum n))
    • Space: (O(n)) per test case (auxiliary difference array).

    Code (Python)

    import sys
    
    def main():
        data = sys.stdin.buffer.read().split()
        it = iter(data)
        t = int(next(it))
        out = []
        for _ in range(t):
            n = int(next(it))
            a = [int(next(it)) for _ in range(n)]
            diff = [0] * (n + 2)          # indices 1 .. n+1
            for i in range(1, n + 1):
                x = a[i-1]
                if x > 0:
                    L = i - x + 1
                    if L < 1:
                        L = 1
                    diff[L] += 1
                    diff[i+1] -= 1
            cur = 0
            ans = []
            for j in range(1, n + 1):
                cur += diff[j]
                ans.append('1' if cur > 0 else '0')
            out.append(' '.join(ans))
        sys.stdout.write('\n'.join(out))
    
    if __name__ == '__main__':
        main()