errorgorn's blog

By errorgorn, 4 years ago, In English

1491A - K-th Largest Value

Setter: syksykCCC
Prepared by: syksykCCC

Hint 1
Hint 2
Solution
Code (C++)
Code (Python) (vim1729)

1491B - Minimal Cost

Setter: syksykCCC
Prepared by: syksykCCC

Hint 1
Hint 2
Solution
Code (C++)

1491C - Pekora and Trampoline

Setter: oolimry
Prepared by: errorgorn

Hint 1
Hint 2
Solution
Code (C++)
Code (Python)

1491D - Zookeeper and The Infinite Zoo

Setter: errorgorn
Prepared by: errorgorn

Hint 1
Hint 2
Hint 3
Hint 4
Solution
Code (C++)
Code (C++) (gamegame)
Code (Python)

1491E - Fib-tree

Setter: Widowmaker
Prepared by: Widowmaker and syksykCCC

Hint
Solution
Code (C++)

1491F - Magnets

Setter: 3.141592653 and star_xingchen_c
Prepared by: 3.141592653 and star_xingchen_c

Hint 1
Hint 2
Hint 3
Solution
Code (C++)

1491G - Switch and Flip

Setter: errorgorn and oolimry
Prepared by: errorgorn

Hint 1
Hint 2
Hint 3
Solution
Code (C++)
Code (Python)

1491H - Yuezheng Ling and Dynamic Tree

Setter: Ynoi
Prepared by: Widowmaker and Ynoi

Hint 1
Solution
Code (C++)

1491I - Ruler Of The Zoo

Setter: oolimry
Prepared by: oolimry

As the solution to this problem is very long, the full editorial is split into $$$4$$$ parts. If you want to challenge yourself, you can try reading one part at a time and see if you get any inspiration. You can also try to read the specific hints for each part.

Part 1 Hint 1
Part 1
Part 2 Hint 1
Part 2 Hint 2
Part 2 Hint 3
Part 2
Part 3 Hint 1
Part 3 Hint 2
Part 3 Hint 3
Part 3 Hint 4
Part 3 Hint 5
Part 3 Hint 6
Part 3
Part 4
Code (C++)
Code (C++) (errorgorn)
  • Vote: I like it
  • +255
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it +53 Vote: I do not like it
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any stream coming up for post-contest discussions?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No one as per I notice for this contest.

»
4 years ago, # |
  Vote: I like it +32 Vote: I do not like it

In the editorial for D, it has the &amp thing

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yep it was fixed. writing & on codeforces latex equations is finnicky :/ you have to do \\&

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      There is still the &amp thing in the solution part for D

»
4 years ago, # |
Rev. 4   Vote: I like it +4 Vote: I do not like it

I thought D very differently

Observations :-

If you want to reach from X to Y
1) X>Y this case is a clear NO. it needs no explanation.
2) THE NUMBER OF SET BITS IN Y can never be greater than X if you want to reach from X to Y.
3) IF YOU HAVE AN ODD X then you can reach every Y which has number of set bits less than of equal to Number of set bits in X.
4) NOW IF YOU HAVE AN EVEN X , I was stuck on this case and had no patterns to observe , if anyone has done it this way , please share your approach

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I think your case 3 is wrong. Consider X=1000110 and Y=0111001 where least significant bit is on the left. We cannot obtain Y from X.

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      I think the case you have given me has number of Set Bits in Y as 4 and number of set bits in X is 3 , My case 3 says for Odd X we can reach any Y which has number of set bits less than or equal number of set bits in X.

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 3   Vote: I like it -9 Vote: I do not like it

        wait sorry. X=10011100 and Y=01100001

        Another thing you have to check is that there exists a matching. Here, the $$$2$$$ bits in Y can only use $$$1$$$ bit in X.

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +1 Vote: I do not like it

    I have got accepted in this way. Idea was if you want to reach X to Y then Y have to be smaller or equal than X, number of setbits in Y should be less or equal than number of setbits in X and all setbits index in Y should be later or in same index corresponding to X. Because if one of the setbit of Y is before the corresponding setbit of X then you will never decrease Y to X.

»
4 years ago, # |
Rev. 2   Vote: I like it +61 Vote: I do not like it

As a Chinese writer, here is the Chinese version of the tutorial (A-H).

Hope you enjoy it. :D

UPD: The tutorial of problem I has been attached.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it -67 Vote: I do not like it

    Can Chinese visit internet? I heard that China is the censorship king? Are you here through a VPN?

»
4 years ago, # |
Rev. 2   Vote: I like it +55 Vote: I do not like it

A perfect round I see.

And I want to explain why some people fst on H.

They pushdowned lazytag to every a in the block.

It's wrong actually. Its complex is $$$O(n^{\frac{5}{3}})$$$

I am sorry to say that I thought it when I doing with my data, but I think no one would write like that because it's easy to change it into just pushdown when query.

Sorry for the fster.

FST is the soul of CF. —— Sooke

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +5 Vote: I do not like it

    [user:Wodiwmaker] What is "fst" ?

    Edit: Ans->FST is short for failed in system testing.

»
4 years ago, # |
  Vote: I like it -18 Vote: I do not like it

In the problem B there are some cases when |a[i] — a[i — 1]| > 1, but answer is not 0.

One of that cases is:

n = 4 a[1] = 1 a[2] = 3 a[3] = 1000001 a[4] = 1000000

If we want to reach to the node (4, 1000001), we will move one of the obstacles in node (3, 1000001) or (4, 1000000).

This means, that in this case answer is not equal to 0.

»
4 years ago, # |
Rev. 3   Vote: I like it +270 Vote: I do not like it

I'm sorry, but I'm honestly not sure how it's even possible to write such egregiously weak pretests. My E fails on any test case where N is not a Fibonacci number, as it doesn't return after printing no (and thus prints either yes or a second no afterwards), and yet it passes all pretests and ultimately gets FST24. I would understand the FST if I had some minor bug in an edge case, but a generator that outputs trees completely at random would fail my submission nearly 99.99% of the time. (And evidently, pretests for A, B, C, and G weren't so strong, either...)

I would have assumed y'all were intentionally aiming for weak pretests if not for the comment on the other thread hoping for few FSTs. Especially given that comment, I think it was pretty reasonable to assume that a test covering this sort of case was included in pretests. I appreciate the preparation that went into the remaining problems, but it probably shouldn't be too hard to understand why losing 90 rating over this FST sours my opinion of this round in general.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +64 Vote: I do not like it

    LOL the same thing happened to me too. I got RE on test 24 (my code also fails in any test where n is not a fibonacci number). That's very upsetting because I could have found my bug in a few minutes and the effect of this minor error cost me over a 100 rating points (and a t-shirt :( )

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +63 Vote: I do not like it

    I want to say a lot, but I can just say sorry now.

    I did write a generator for that case.

    It has 1/5 posibility to generate a non-fibonacci-number $$$n$$$.

    For some reason, I just upload it and add a test to tell them I have written a generator for E.

    But they write a new generator and forget this case.

    So finally We just used that to create a test however. And unluckily, it's not in that case.

    Sorry again :sadness:

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I saw tourists solution of C in O(n) using DSU, how to solve it using DSU?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Typo in the solution for 1491D? bit from v from u from the

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can we get an example for this — 1491D We can convert any u+v move to a series of u+v′ moves where u&v′=v′ and v′=2k.

»
4 years ago, # |
  Vote: I like it +239 Vote: I do not like it

You serious?

Part 1 Hint 1
Part 1
Part 2 Hint 1
Part 2 Hint 2
Part 2 Hint 3
Part 2
Part 3 Hint 1
Part 3 Hint 2
Part 3 Hint 3
Part 3 Hint 4
Part 3 Hint 5
Part 3 Hint 6
Part 3
Part 4

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Got the correct idea of E but failed to implement it :(

»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Problem B got me confused with the constraints during contest. Didn't realise that the obstacle can't be placed on first and last column which led to completely different approach. And rather complex bounds to deal with.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Didn't realise that the obstacle can't be placed on first and last column

    I realized this only after reading your comment. OMG.

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I think I have the same logic in 2nd question but the test didn't pass. How can I know which test case made it wrong?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can scroll down through your submission to see on which case your o/p differ. But there is limitation to number of test case shown.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Peko Peko

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think C's editorial is kinda overcomplicated although the final idea is the same. You always need to start from the first s_i that is not 1 and perform s_i-1 jumps, then it is just a simulation problem.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Can u demonstrate plz more ? I did the following : each number can't be more than 5000 (worst case) because it throws the rabbit out so we add to the answer A_i — 5000 if A-i >5000 then iterate from left for every value that is not 1 run a simple DFS starting from this index until it becomes 1 and simulate the process but that was TLE since it is O(n³) I need to improve it to become O(n²)... thanks in advance.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Just maintain an array nxt[i] for the position of next non-1 number after i. Then if a[i] is 1, use nxt[i] instead of simply i++.

      Since after use nxt[i], you can always land on a non-1 number and decrease it by one. And the initial total height of all a[i], as you said, is at most 5000*5000. Therefore, this solution is O(n^2).

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Can you please explain the solution to C a bit in detail , I can't get what the editorial is trying to say at all

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks, upsolving time

»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

what about when the obstacles in (0 ,1) and (n-1 , 1e6+1) in problem "B"!!

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    The first and the last column are excluded from having obstacles, see the constraints!

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is written that 1<=a[i]<=1e6

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

In problem E, I started dfs from 1 and calculated the sizes of all the subtrees and checked whether the size of any subtree is a part of fibonacci sequence, but can anyone please explain why it gave wrong answer on pretest 14, link to my SOLUTION. Thank you :)

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I got WA using the same algorithm, and find the counter example:

    8
    2 1
    3 2
    4 3
    5 1
    6 1
    7 1
    8 4
    
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Can anyone explain C better that is what is happening in editorialists solution?

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +5 Vote: I do not like it

    Have an array curr which holds all the jumps made on an index.

    For an index i:

    • if the jumps made so far (curr[i]) were not enough to get it to 1, then add to the solution the remaining Si-1-curr[i] jumps (each of these jumps is a new pass because i is the first non-1 trampoline).

    • after the if is executed, temp is the number of jumps on index i

    • temp — (Si — 1) = the number of jumps on index i — the number of jumps necessary to get to strength 1 = all the jumps that jumped to i + 1. So we add all of these jumps to curr[i + 1]

    • add 1 jump to curr[j] for j in range [i + 2, i + Si]. These jumps are performed in order to get the trampoline i to strength 1

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      emp — (Si — 1) = the number of jumps on index i — the number of jumps necessary to get to strength 1 = all the jumps that jumped to i + 1. So we add all of these jumps to curr[i + 1]

      can you explain this part a bit ! I just cannot understand how is this true ?

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        When the for loop gets to index i:

        • curr[i] represents the number of jumps that happened already on trampoline i

        • curr[j] where i < j (all indexes to the right of i) represent the number of jumps on trampoline j that were the second jump of a pass. This is the key point. If a pass started at index 1, jumped from 1 to 3 and from 3 to j, this jump on j is not yet added to curr[j].

        Example: Si = 3, curr[i] = 5.

        • The first jump gets us to i + 3 (we add this to curr[i + 3])

        • The second jump gets us to i + 2 (we add this to curr[i + 2])

        • Jumps 3,4,5 jump to i + 1 but we don't add +3 to curr[i + 1] in the second for loop, that only does cur[j]++. So when we get to index i, we add these 3 jumps to i + 1. This is done in curr[x+1]+=temp-arr[x]+1;

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

can someone explain c more clearly?

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

someone please Explain C ..... the editorial is too complex at least for me

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same here

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      You have to jump on the first number which is greater than 1, then just add 1 to all the further indexes where current number will jump (for this you can keep an temp array) and for any further number check how many times you came on it already , then jump more if then number is still greater than 1

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    it's clear that for each i from 1 to n you have to jump in the i'th position a[i]-1 time right?

    ok we will do it lets start from the first position and jump on it until it become 1 but on each jump on this element tell the next positions that you have jump to them

    how??

    ok if n = 10

    and a[1] = 5

    in the first jump you will go to the position 1+5 ok just tell the 6'th position that you will go to him

    know a[1] = 4 and that next jump will take you at the first step to 1+4 yes tell the 5'th position you will go to him

    when a[1] become 1 you will have told each position that you will jump to him

    so when you go to i+1, i+2, i+3.... you can know that you jump on the current position some times if this number of jumps grater then a[i]-1 you don't have to make any other jumps in the current position else you will do the remain jumps

    but don't forget you have just calculate one step from each position to another so when you are in some position j you have to till the next positions that you are jumped on them

    O(n^2)

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      now i know the basic O(N^3) solution with help of some and your comments. can you explain how to reduce it to O(N^2) time complexity?

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So basically what I can conceive is that we don't really wanna do the jumps as in a simulation but all we do is store where those jumps are going to be so that when we want to start the procedure at index j we will determine if that index is already has become 1 or it is valid to start another jumping journey from it . If I'm right then your explanation should really be the editorial :D

  • »
    »
    4 years ago, # ^ |
    Rev. 4   Vote: I like it +29 Vote: I do not like it

    I finally get how to solve C. Here's how:

    Problem Recap

    Jump from any trampoline (say index 'i'), land at index (S[i] + i). If index (S[i] + i) is in bounds, then continue jumping in a similar manner until you're out of bounds. At each hop, you're reducing the trampoline's strength by 1. Make all trampolines' strength 1. How many initial jumps does it take?

    Observations

    1. Trampolines can only propel you to the right. Which implies that you need to start from the left and start jumping from the first trampoline that's greater than 1 (Note that you could jump from the leftmost trampoline as well — it has the same effect as starting from the first trampoline with a strength greater than 1).
    2. Consider what happens when a trampoline i has a strength of 1 (i.e. S[i] = 1). It simply propels you to the next trampoline to its right (i + 1).
    3. Next, consider what happens when a trampoline i has a strength of 4 (i.e. S[i] = 4). On it's first jump, it lands on trampoline i + 4, and S[i] becomes 3. On the next turn from the same trampoline i, it lands on trampoline i + 3, and S[i] becomes 2. Finally, it lands on trampoline i + 2 and S[i] becomes 1. We can now move on to the next trampoline to its right.
    4. So, for any trampoline i with a strength of S[i], we jump once to each of indexes i + 2 up to i + S[i]. We need a way to track this. Use prefix sum markers (add 1 to the beginning of the range: pref[i + 2]++, and subtract 1 after the end of the range: pref[i + S[i] + 1]--). Here pref[] is the equivalent of prior incoming hops to those subsequent trampolines.
    5. Observe how we're simply marking how many times a jump would go to a future index (and not processing that future index at this time — we will get to it eventually). Also, note the final result only calculates the total number of hops initiated from the current trampoline.
    6. Say we now get to the trampoline at index i + 7 and you've landed here 4 times from prior incoming hops (which would mean that pref[i + 7] = 4). Since you've landed here from prior hops, those hops should not count towards the final cost. So the net sum for this trampoline would be S[i] — 1 — pref[i] (since you need S[i] — 1 hops anyway out of which pref[i] are from prior hops). Of course, if this is negative, you discard it. So if S[i + 7] were 6, since you've already come here 4 times from prior hops (you'd be left with a net strength of S[i + 7] = 6 — 4 = 2), and you'd need to initiate just one hop to make S[i + 7] = 1.
    7. IMO, a very tricky part of this problem is when prior hops exceed S[i] — 1. In that case, S[i] would've become 1 already at some point, and every additional prior hop (i.e. incoming_hops[i] — S[i] + 1) would land at position i + 1. Using prefix markers, we can increment pref[i + 1] by this additional hop count and decrement pref[i + 2] by the same.
    8. Also, another thing that I found confusing was the relationship between incoming hops and current strength. There is no correlation between the two. You would have to jump S[i] — 1 times regardless of whether you came via incoming hops or initiated the jumps from the i'th trampoline. The only difference is the cost (the more the prior hops, the lesser the net cost in terms of jumps initiated from position i).

    Reference

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Thanks for the clean explanation!

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks a lot. Nice explanation!

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This is best to be included in official editorial.

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 47   Vote: I like it 0 Vote: I do not like it

      Thanks for the explanation. But I am not getting what pref[] array is storing. I got that starting from any non-zero value of s[i] we can increment the range (i+s[i],i+2) by 1 and when we will get there we will decrement that s[j] by 1+pref[j] but how we are maintaining this pref[] array?

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        In general, pref[i] stores t[i]-t[i-1], where t[i] is the number of ranges that started at some j<=i and will end at some k>i. Notice that we can always derive t[i] from the pref array, using the formula t[i] = pref[0] + ... + pref[i]. If i is running from 0 to n-1, deriving t[i] per i is O(1), since pref[0]+...+pref[i-1] is pre-computed. The advantage of maintaining pref[] (instead of t[]) is that, updating information for a range is faster: just 2 operations (Observation 3 in sh_maestro's post). Whereas if we maintained t[], that would be linear in the size of the range.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for the descriptive explanation.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks, very nice explanation, I just to understand point $$$6$$$

      what is incoming hops, did you mean $$$pref$$$

      can you please elaborate more on point $$$6$$$.

      I have implemented this during contest, but it did not work.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think incoming_hops[i] is the total number number of jumps from previous positions to position i. We have that incoming_hops[i] = pref[0]+...+pref[i] = incoming_hops[i-1] + pref[i]

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it +4 Vote: I do not like it

        I'll elaborate here (I've also added a little more context to the original explanation)

        pref[] is the same as incoming hops. When you are at index i, you need a way to designate the indexes that index i will hop to. Say the trampoline at index i has a strength of 5 and hence hops from indexes (i + 2) to index (i + 5). pref[] will add 1 for each element between these 2, inclusive (i.e. pref[i + 2]++, pref[i + 3]++, pref[i + 4]++, pref[i + 5]++). Note that you don't actually need to update each index as that would be an expensive O(N) operation. You can do it in O(1) by simply updating the bounds (one at start, and one right after end) and have a rolling prefix sum to calculate the net result so far (pref is called "here" in the reference code — I should've been more consistent).

        To elaborate on point 6 (which is now point 7 since I added one), consider this example:


        Strength: [**4**,4,4,2,3] Pref: [0,0,0,0,0] Answer: 0

        At index 1, a strength of 4 means that it will initiate 3 jumps (to indexes 3 through 5). Lets update pref accordingly.


        Strength: [**1**,4,4,2,3] Pref: [0,0,1,1,1] Answer: 3

        Move to the next trampoline to its right.


        Strength: [1,**4**,4,2,3] Pref: [0,0,1,1,1] Answer: 3

        At index 2, initiate 3 more jumps (to indexes 4 and 5 and once out of bounds).


        Strength: [1,**1**,4,2,3] Pref: [0,0,1,2,2] Answer: 6

        Done with this trampoline. Move on to index 3.


        Strength: [1,1,**4**,2,3] Pref: [0,0,1,2,2] Answer: 6

        At index 3, notice that there was 1 prior jump so 2 (i.e. pref[3] == 1) new jumps need to be initiated to bring its strength to 1. Total of 3 jumps (one prior, 2 new) — once to index 5 and twice out of bounds.


        Strength: [1,1,**1**,2,3] Pref: [0,0,1,2,3] Answer: 8

        Done. Lets move to index 4.


        Strength: [1,1,1,**2**,3] Pref: [0,0,1,2,3] Answer: 8

        Now, index 4 is different from the rest. It has had 2 incoming jumps and has a strength of 2. The first hop makes it jump out of bounds, and brings its strength down to 1. The second hop makes it jump to index 5 (i + 1, instead of the i + 2 that we've seen so far). Had there been a third jump, that would've gone to index 5 as well. Note that the answer remains 8 since no new jumps had to be initiated here.


        Strength: [1,1,1,**1**,3] Pref: [0,0,1,2,4] Answer: 8

        Finally we move to the last index


        Strength: [1,1,1,1,**3**] Pref: [0,0,1,2,4] Answer: 8

        Here again, the incoming jumps (pref[5] = 4) exceed strength — 1 (3 — 1 = 2) by 2. So no new jumps need to be initiated and the answer remains 8.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Excellent explanation, this is more than what I could hope for! thank you so much for your time.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Just want to say thank you! Finally understood the solution.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Trampolines can only propel you to the right. Which implies that you need to start from the left and start jumping from the first trampoline that's greater than 1
      

      Why we can't start from 1 as we eventually reach first non-one and it did not increase the pass count ?

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Good point. You could start from the first trampoline on the left — it has the same effect as starting from the first trampoline with a strength greater than 1. I've updated the text around this.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I have 2 questions: 1.) What is "count" doing? 2.) Why decrement one from the position after range? I mean, why here[mx + 1]-- and why not here[mx]--?

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        1) after some pass s[i] will be equal to 1. then pekora will jump from i to i+1 trampoline when it is on i-th trampoline . here count variable counts the number of incoming hops on i after s[i]=1

        2) to increment the number of incoming hops from i+2 to i+s[i]. To understand it better you can read this article.

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        To your first question:

        "count" tracks the number of extra hops (i.e. for any index i, it's incoming hops — (strength — 1)). The reason for counting this separately is that these hops will all go to index i + 1.

        To recap, if incoming_hops is 10, and strength is 4. Then the first 3 hops will go to indexes i + 4, i + 3 and i + 2. At that point the strength becomes 1. But there are still 7 (10 — 3) more incoming hops. Those 7 will all go to index i + 1.

        To your second question:

        When you want to add an "amount" to a range [l, r] (both inclusive), the way you do it is to mark pref[l] += amount and pref[r + 1] -= amount. This is because you want pref[l] through pref[r] to all get incremented by that amount, and then decrement by the same as soon as you step beyond r. Then at each index, you accumulate the sum. So pref[l + 1] += pref[l], then in the next iteration pref[l + 2] += pref[l + 1], etc. — this way the sum gets carried over from the current index to the next.

        The link shared by Saimun_Islam explains it in detail.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it
This is optimal as we can consider the first trampoline that Pekora jumps on for both these passes. It is clear that the series of trampolines jumped on in these 2 jumps does not change.

Please someone explain this in Problem C.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It basically says that you can freely exchange the order of trampolines you choose to start and the resulting strengths in the end will always be the same. You can play around with some examples to see why this is true.

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone help me to figure out why and where I am getting that one extra (0/1) in the answer in Testcase 2 in Problem A Solution . Thanks in advance for your help.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My self worth took a big hit during this contest.. The round was really great though! Kudos to the authors..

»
4 years ago, # |
Rev. 20   Vote: I like it +6 Vote: I do not like it

The problems had a lot of variety. I appreciate your hard work in setting such a nice contest and for such a quick editorial. Wish more such contests keep happening!

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I've done C with a lazy propagation segment tree (adding a constant on the range), so my solution is O(n log n). Any ideas how to get to O(n)?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You need to add on range right, so you can just maintain a array and increase $$$l$$$ by $$$1$$$ and decrease $$$r$$$ by $$$1$$$. So you are just iterating from left and these range additions are also accounted for.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can u plz explain your approach ? I'm learning segment tree right now so this would be so helpful

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please Help me In Problem C, I have done normal simulation as given in editorial O(N^2) and still am getting TLE on TC 9.

My Submission Link https://codeforces.net/contest/1491/submission/108727431

Please Codeforces community

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    TLE because O(N^3)

    The editorial doesn't simulate all the jumps in order. I did, but I skipped all the jumps equal to 1 by using a set of intervals for these trampolines. The code is long and ugly though.

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

In python solution of 1491C — Pekora and Trampoline

What is the meaning of line

temp+=arr[x]-1-temp

doesn't it just means temp = arr[x] — 1?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    no , it means temp = temp + arr[x] — 1

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      temp += arr[x] — 1 — temp

      this is equal to : temp = temp + (arr[x] — 1 — temp)

      which means temp = arr[x] — 1

      Am I doing anything wrong here?

»
4 years ago, # |
Rev. 2   Vote: I like it +151 Vote: I do not like it

In problem E, my code will have some problems when n is not a fib number, I noticed that after I locked problem. There is a person in my room who make mistakes with data like this, I submitted a hack data (this data also can hack myself), and it returned unexpected verdict.

I Failed System Test in E, and my hack has been ignored. But this submission was hacked by me, I didn't get 100 score.

Why is it?

»
4 years ago, # |
  Vote: I like it +51 Vote: I do not like it

雪花飄飄北風嘯嘯 天地一片蒼茫

:D

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In fact, I have some questions about the problem B.

In the tutorial, we can find that the answer will be one of the three numbers: 0, min(u, v) and v + min(u, v). But considering the following data:

4 3 4

1 0 1000001 1000000

, we can find that we have to move two obstacles to make sure that we can reach (4, 10000001) from (1, 0). And in my opinion, the answer will be 2 * min(u, v).

If I'm wrong, I'll highly appreciate if you can tell me which condition I missed. Thanks.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Read the problem description carefully.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh, thanks. I find that where I'm wrong. The $$$a_i$$$ is not greater than $$$10^6$$$, so the situation I considered won't happen.

      Thanks again.

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

My ugly O(n^2\log n) solution for C passed...... My solution is simulate the jump, and use a balanced BST to find the next trampoline with S > 1 in O(\log n) time. Number of total jumps is O(n^2)

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My submission for C got TLE even though i'm sure it's $$$O(N^2)$$$, can anyone help me? Probably a problem in the while loop but hard to tell for me. Submission Link

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +36 Vote: I do not like it

    Naive simulation is actually $$$O(N^3)$$$. It hits that bound on test 5000 4999 4998 ... 2 1.

    I probably should make editorial more clear about how to simulate in $$$O(N^2)$$$.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain D to me

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    means what is the intuition behind this?

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 4   Vote: I like it +2 Vote: I do not like it

      Let's take a binary string here as example, 1001100101. Notice that if we pick any number which has one set bit(i.e a power of two) whose set bit lines up with a set bit in the given binary string(for example binary string 100), then its bitwise and will be the string itself(1001100101 & 100 =100). Now when we add the two numbers, two cases might occur. If there are no consecutive set bits ahead of the set bit, then the set value shifts by one bit(1001100101+100=1001101001). If there are consecutive set bits ahead of the set bit, then the first set bit in the consecutive set bits shifts by 1 bit, and the other consecutive set bits disappear(1001100101+100000=1010000101). So if we can reach number v from number u by applying these two possible operations, then there is a path between them.

»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Can someone tell me what is wrong in my submission for problem E? I am getting WA on Test 14

1491E - Fib-tree108766255

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone help me out why am i getting WA on test case 8 in E My submission — Your text to link here...

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The problems had a lot of variety. I appreciate your hard work in setting such a nice contest and for such a quick editorial. Wish more such contests keep happening!

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you explain D bit more ? Why exactly do we want v = 2^k ? And what does this line mean ?

This is because we can add each bit from v from u from the highest bit as adding a bit to a number will not affect lower bits.
»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

the Python solution in this editorial for problem 1st gets TLE in both Python3 and PyPy 3. So heres my solution which got accepted 108784095

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Why this number is so common among testers and random generators :XD

Capture

This is the 27th testcase of problem C

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In the question B, do we have to move the obstacles before starting our movement or can we move the obstacles while we are at some other node(instead of 1,0)? Because then the answer changes for this test case:- 2 100 1 1 2 If we move the obstacle 1 and move it to our current node then we cannot go pass through the obstacle and hence the answer is 2(by moving the second obstacle twice towards right) but if we can move the obstacles during the journey then the answer would be 1. According to the solution the answer should be 1 but according to the problem statement its not possible because then the obstacle is at the starting node.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nvm I got it. We can move the second obstacle towards the right.

»
4 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

I have a doubt in B. What if the obstacle in last row is present on 10e6+1 and on all rows before that, its present on 10e6 then v is not a possible answer. Please enlighten me.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    1<=ai<=1e6. So the obstacle will be never on the column 10e6 + 1.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks I had missed that

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Same bro i also missed the part that 1st and last columns are empty. You should try when there are no such restrictions. I submitted a general code assuming no restrictions in the placement of obstacles in column.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Your code doesn't even solve the general case and you have a couple of redundant if statements.

»
4 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

errorgorn oolimry In C editorial's python code is giving tle.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you please tell the DP approach for problem C....I got stuck at it just because I kept thinking that it had to be done using DP

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain C to me?

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    Because of greedy works, we should reduce S (to 1) from left to right.

    Use tmp(i) to present the numbers of jumping on the i-th Trampoline from Trampoline 1~i-1.

    When we come to think about the i-th Trampoline, the first thing we need to do is to add ans with max(0,S(i)-tmp(i)-1), because we can jump tmp(i) times for free.

    The next thing we should do is state transition, we should add the tmp(i+2,……,i+S(i)) with 1. tmp(i+1) should be specially handled---add it with max(0ll,tmp[i]-(S[i]-1))

    The more detailful things are in my code

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

A nice contest.

Although it's the first global round I participte in, I perform as good as I expected before the contest.

The first four problems are a little harder than the first fours in the Div.2, and I had a difficult time trying to solve D. (I AC D before the contest ended by 5 mins)

This shows me I still have a long way to go, so I will continue to work hard and improve myself.

Hope everyone can enjoy the contest!

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

[problem:B] In the statement n is "<= 100", but I can't pass. After I set N as 1e7, I get AC. And in the Tutorial, N is 1e6. So I think the data is different with the statement.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem F : As all the previous answers are 0, it's easy to prove that the magnet we found is the second one we have selected.

Is there anyone who can proof it for me?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D, I was not able to prove that if v has smaller or equal no of set bits than u where v>u then we can always reach to v. Can somebody help me in that?

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +3 Vote: I do not like it

    What you are saying is necessary but not sufficient.

    For example take (in binary) u = 001001001 and v = 010000011 , clearly v>u and number of bits in v is equal to number of bits in u , but you cannot reach v from u.

    We can reach v only if number of bits occurred till position $$$i$$$ in v is less than or equal to number of bits occurred till position $$$i$$$ in u and v>=u (sufficient condition).

    One of the way we can approach the proof is that we can shift the bits of u any distance toward left but above condition must hold because whenever we add the subset it increases the u and shifts it's bits toward left by one and may cause some of bits disappear because of adding (they become carry).

    00001100011 + 00000000011 = 00001100110 . Here we can see first two bits shifted toward left by distance 1.

    00001100011 + 00000000001 = 00001100100 , here we can see that second bit shifted toward 3rd position and first bit disappeared .

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Pekora and Trampoline — O(n) Solution

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi there,

Could I get some help with TLE for E?

108832717

It should have the same complexity as what the editorial says. Is it because I use recursion for my findSplit function?

Thanks!

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any proof for problem E that Fib-tree can be partitioned within at most 2 ways.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You can notice that parts of size $$$F_{n - 2}$$$ must be disjoint (otherwise it would imply $$$2F_{n-2} \geq F_{n}$$$, which is false). Therefore number of partitions is bounded by $$$\lfloor{\dfrac{F_{n}}{F_{n-2}}\rfloor}$$$.

»
4 years ago, # |
Rev. 6   Vote: I like it +10 Vote: I do not like it

I added some pictures to explain the proof of E. For a Fib-tree, there are two cases. In one case(see picture below, that's the case described in editorial), there are two ways to cut the tree, both ways are valid.

In another case(see picture below), there is exactly one way to cut the tree: cut "First Edge" first, then cut "Second Edge". In this case, "check $$$F_{n-1}$$$ or $$$F_{n-2}$$$" also works: if tree root is in left two parts, we will find a subtree consists of $$$F_{n-2}$$$ vertices; if tree root is in the right part, we will find a subtree consists of $$$F_{n-1}$$$ vertices.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

"exchange argument" .How it is used in C? please anyone explain the proof. I can't understand.

  • »
    »
    4 years ago, # ^ |
    Rev. 4   Vote: I like it +8 Vote: I do not like it

    Exchange argument is a greedy proof technique that is to show that we can turn any optimal solution into one that our greedy algorithm will produce and it will do no worse. Here we want to show that it is optimal that for each pass, the trampoline that Pekora will start at is non-decreasing.

    In the editorial, we have shown that swapping the sequence of any $$$2$$$ consecutive passes does not change the final outcome of the strengths of the trampolines. Therefore, by performing a series of swap, we can sort $$$P$$$ (or you can think of it as bubble sort) for any arbitrary optimal solution $$$P$$$.

    For a concrete example, suppose an optimal solution is $$$P=\{3,1,4,1,5\}$$$. Using our proof, we can say that $$$\{3,1,1,4,5\}$$$,$$$\{1,3,1,4,5\}$$$,$$$\{1,1,3,4,5\}$$$ are all optimal solutions.

»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

With respect to problem C: Pekora and Trampoline, I implemented the $$$O(N^2)$$$ solution. However, I still got TLE. In my opinion, an $$$O(N^2)$$$ algorithm would amount to elementary operations of the order of $$$10^8$$$, which should be executed in under $$$2$$$ seconds. I have attached my code below.

My code

If my code is inefficient, please do recommend suggestions. Also, I am aware of the $$$O(N)$$$ solution but I would like to first implement the $$$O(N^2)$$$ solution as it was explained in the editorial that such a solution should also pass the test cases.

Also, please do think before downvoting, and if you still decide to do so consider also informing me what was lacking or offensive in my comment. I have been given a contribution of $$$-1$$$ due to a post of mine but I'm still not able to figure out what was wrong. Due to my negative contribution, I have to face a lot of embarrassment. I hope you understand.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it
    long s[3000];
    long pref[3000];
    

    Why set your array size to $$$3000$$$ when $$$n$$$ can be up to $$$5000$$$?

    After changing this it got AC.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't understand in problem D, why do we have to start checking from LSB instead of MSB ?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

1491G — Switch and Flip

Code (C++)

//雪花飄飄北風嘯嘯

//天地一片蒼茫

(a Chinese song named "A Spray of Plum Blossoms")

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I wonder how to construct test cases that need $$$O(n^3)$$$ moves to solve, in Ruler Of The Zoo.

BTW, here are two hacks.

This hacks rainboy :

4
2 1 12
11 3 6
7 4 8
9 5 10

and this hacks huzhaoyang:

4
2 1 8
11 3 4
12 5 10
7 6 9
  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    I guess if if after $$$n-1$$$ moves all the reds move anticlockwise once, then you can probably do this for $$$O(n)$$$ times before an event occurs. This in total takes $$$O(n^2)$$$ time for an event to occur.

    If we have a lot of REDs, we can make only the last one trigger at the last set of $$$n-1$$$ moves, this will take $$$O(n^2)$$$ moves to occur. Then, since we insert a new BLUE into the belt, we can use this new BLUE to trigger the 2nd last RED, which will require a total of $$$O(n^2)$$$ moves again. Doing this for all $$$O(n)$$$ REDs will require $$$O(n^3)$$$ moves.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you for hack

    To construct test cases that need $$$o(n^{3})$$$,I think we can make even positions RED, and then make them NONRED from right to left

    More specifically,let Ai,Bi and Ci at odd position be large enough

    For even positions,$$$A_{i}=10i$$$,$$$B_{i}=A_{i-2}-1$$$,$$$C_{i}=B_{i}+1$$$

    (In particular, $B_{1}<A_{n}$)

»
3 years ago, # |
  Vote: I like it -10 Vote: I do not like it

I'm sorry for posting this late, but I really need help on problem D. I have a solution but it WAs on token 644 My approach is to try to add the powers of 2 in the binary representation of (v — u) to u from left to right If the bit in both u and v — u is 1 then I add that power of 2 to u and then move towards the left to see if a new bit has been set to 1 that wasn't able to be used before If that bit can be used, add the respective power of 2 and keep moving left The second case is if the bit in u is 0 and if the bit in v — u is 1 Then I used a set to store that that index hasn't been used, next time I reach case 1, I'll be able to use that information to see if I need to use a previous bit Here's my submission: https://codeforces.net/contest/1491/submission/154037118

Is my logic wrong or do I just suck at implementation?