Monogon's blog

By Monogon, history, 3 weeks ago, In English

I hope everyone enjoyed the contest!

UPD: Added implementations for all problems.

1405A - Permutation Forgery

Author: antontrygubO_o

Tutorial

Implementation

1405B - Array Cancellation

Author: hugopm

Tutorial

Implementation

1405C - Balanced Bitstring

Author: Kuroni

Tutorial

Implementation

1405D - Tree Tag

Author: Maripium

Tutorial

Implementation

1405E - Fixed Point Removal

Author: hugopm

Tutorial

Implementation

1404D - Game of Pairs

Author: Ari

Tutorial

Implementation

1404E - Bricks

Author: Monogon

Tutorial

Implementation

 
 
 
 
  • Vote: I like it
  • +416
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it +36 Vote: I do not like it

Thanks for a good round and fast editorial!

»
3 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

Thanks for a good round and fast editorial!

»
3 weeks ago, # |
  Vote: I like it +430 Vote: I do not like it

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

    I had to google how during the contest and actual real-life trees kept popping up lol

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

      smh this guy didn't do the tree basics set, what a cyan...

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can't do the tree basics set if it isn't open for virtualing yet :/

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          The problems should all be publicly available, but how do I open it for VP?

          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            This should come up in the "Edit" tab of the contest (I think)

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

              Here's what I see:

              • »
                »
                »
                »
                »
                »
                »
                »
                3 weeks ago, # ^ |
                  Vote: I like it -13 Vote: I do not like it

                On the same page, there's also this, which should do the trick

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

                  What do you mean by "on the same page"? I literally just posted what the page looks like for me and that isn't there.

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

                  Doesn't it already say that, in case the visibility isn't private, the following will be set to defaults, where "virtual allowed: yes" is in the list

                  UPD: Btw, I am able to click on "virtual participation" under the contest, and it asks me to register. So, I'd say it's some issue on ScarletS's side.

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

        I'm just a cyan with a good keyboard tbh, will watch your vids later tho :)

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

        I only got AC because I saw your video and reused the code that I submitted for your contest. You are a prophet orz

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I got the diameter idea just because I did those gym questions. Thanks!

»
3 weeks ago, # |
Rev. 3   Vote: I like it +45 Vote: I do not like it

Hi, I believe that it is not necessary to use binary lifting for problem d1C. We could use a segment tree of pairs (v, -index), and do a range minimum value on this.

This will automatically tiebreak for the larger-indexed nodes to come first.

Edit: Thanks for the round, the problems were interesting!

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

    Yup it's true, a lot (including me) solved it like this. However, the tutorial's solution can be implemented using only Fenwick tree, and we feel like it's more beautiful to include such a solution.

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

    can u explain more how can we do that? i seen your submission when u take query why u have change your b to N-b

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

      I’ll assume you mean why I insert the value v=mp(s-A[s],-s) as your question.

      The reason why the first value of the pair is s-A[s] is as stated in the editorial. When we query, to prevent numbers from going below zero, we would like to find the maximum index that is zero. Since c++ compares values by the first digit, then second digit, and that we have a minimum value segment tree, we acquire the maximum index by inserting -s as the tiebreaker. This means the largest index is reflected as the minimum value.

      Hope this helps!

»
3 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

STRONG PRETESTS

»
3 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

nice problems

»
3 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

Good problems! Congrats on great round!

»
3 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

In the tutorial of tree tag in case 1 why are we saying that alice tags bob in the first move? Did the question mean that even if alice and bob share a vertex once ..alice wins??But i don't think it was mentioned as such??Can u please answer[user:Monogon]

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

    The statement said in at most 10^100 moves, meaning Alice can win before that many moves are done. I hoped the explanation of sample 1 would make this clear. Sorry that the statement wasn't more clear about it.

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

      I got confused by the last line saying that if after 10^100 moves they occupy the same place. Thanks for the clarification. Great round.

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

My Code using Vectors gave Runtime on Test 4 while the Same code using Array Passed!

Someone please help?

Edit: Got it

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

    You call v.clear() after every test, which means your f(i,0,k+1) v[i]="" and so forth only work for the first test. After that it's UB / crash. See 92079157.

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

      Oh! Got it Thanks!

      Now I'm wondering how it

      • worked on my local compiler (Sublime Text 3)

      • passed the first 3 pretests lol

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

        Undefined Behaviour means that anything is possible. Unlike some more programmer-friendly languages, C++ is rather harsh and won't check for things like "out of bounds access" because that would be a waste of time for a correctly-written program (unless you enable the debug mode!).

        The first two tests seem to have small sizes of $$$n$$$, and the third one only had one sub-test.

        Data in a vector lives in some block of memory allocated to you by the OS, and it will be at least a couple of kB. It just so happens that this block was large enough to fit the small tests (you were still going out of bounds, but it kinda worked because there was accessible memory there). But when your program tried to reuse over 1 MB of memory that had no longer belonged to it, you were out of luck.

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

          OH. I didn't know. Thanks ! :)

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

          That's the best explanation of UB that I have ever seen!

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

<rant> Ahhhh I got the first 2 cases for D1B / D2D, but didn't expect such as simple algo for 3rd and 4th cases. I guess I need to work on proofs for next time. </rant>

Great contest, hope to see more like it :)

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

Can someone explain me the meaning of problem Div2.D (Tree Tag). I read it again and again for about one hour and yet could not relate the meaning of the problem.The problem statement is so unclear.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'll try to explain in graph theory terms.

    Alice and Bob are each located at some node in a tree (undirected fully connected graph without cycle). Each edge has length 1.

    On Alice's turn, she starts at her current node and can take any walk any path with length <=da to end up at her next node. On Bob's turn, he does the same (with path length <=db instead of da). Alice wants to end up in the same node as Bob at some finite time. Bob doesn't want to be in the same node as Alice.

    Print whether Alice reaches same node as Bob or not.

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

      Thanks, I got it now. I thought that for alice to win,alice and bob had to be in thier same respective initial nodes .

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

    The variables used for notation were unclear to me at first as well.

    We have a tree T on n vertices. Alice is initially at vertex 'a' of T, and Bob is initially at vertex 'b' of T. Now, Alice has a jump-power of "da" (this da is unrelated to the vertex a, nor is it d*a). da (better written as d_{Alice}) is the maximum distance Alice can jump in one move. Similarly, db (better written as d_{Bob}) is the maximum distance Bob can jump in one move.

    Now they take turns jumping from vertex to vertex. In each move, Alice can move from her current vertex (say u) to a vertex v such that

    dist(u,v) <= d_{Alice}.

    The legal moves for Bob are similar, but with d_{Bob} instead of d_{Alice}

    If within 10^{100} moves, Alice can force herself and Bob to be on the same node, then she wins, else Bob wins.

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

somehow i feel prob B is the hardest :v

»
3 weeks ago, # |
  Vote: I like it +53 Vote: I do not like it

Very cool problems! Thank you!

»
3 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

STRONG PRETESTS..

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for a nice round with cool problems.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Please attach codes also

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For Div2D, my code mysteriously fails on pretest 9... : https://codeforces.com/contest/1405/submission/92071460. I have the same logic/cases as the editorial, and I calculate the diameter of the tree with two runs of bfs. Any help would be greatly appreciated.

I'm a little bummed because I was so close to solving 4 questions which was my goal for this contest.

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

    I think you forgot to reset maxDist to 0 between test cases D:

    EDIT: Oh wait I see you did. I think you might have forgot to reset something, not sure.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hack case:

    1
    5 1 5 2 5
    1 2
    2 3
    3 4
    4 5
    
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think it should be if(2*da+1 >= maxPath) cout << "Alice\n" instead of just if(2*da >= maxPath) cout << "Alice\n";

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

        My code returns Alice for that test though, which I am pretty sure is correct (she can stand on node 3 and then catch Bob on the next move). Also in the editorial it is 2*da >= diameter (and diameter = maxPath in my code).

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

          I think in


          int bfs2(){ int m = 0; queue<int> vis; vector<bool> vist(n);

          Especially at vector<bool> vist(n); it should be vector<bool> vist(n+1); instead due to your node was 1 base index.

          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Omg, thank you so much, it got AC. Haha, one missing "+1" derailed my whole solution. Next time I should probably just decrement all the nodes by 1, lol.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can You please explain to me your bfs2 function?? The diameter of a tree implies the longest common path from one leaf node to another. So how are you calculating that longest path?? Thanks in advance.

»
3 weeks ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

The real question is how did your checker for problem D work if they choose to play as the first player? It sounds way easier to solve than to verify...

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

idk about all of you.... but I used two pointers and it somehow worked lol

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

In problem DIV2(D) Tree Tag , nowhere in the problem statement it is mentioned that if Alice catches Bob then Alice wins or vice versa. I think that the problem statement should be updated! Correct me if I am wrong :)

Edit: Finally understood what "If after at most 10^100 moves, Alice and Bob occupy the same vertex, then Alice is declared the winner. Otherwise, Bob wins." means :)

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same mistake i also did bro.

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

    Alice and Bob occupy the same vertex, then Alice is declared the winner.

    It was quite obvious from the above line that Alice will try to catch Bob (occupy the same vertex) and Bob will try to avoid.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can Anyone tell me Why Did Codeforces compiler gave Run Time Error in my Solution to Problem B Div 2.

My Submission: 92070449 while other compilers like https://www.onlinegdb.com/ gave correct answers?

I wasted the whole 1 and a half hours to debug this still can't. Can anyone tell me why did it happen?

I just Used Lower Bound to find the position of the lowest index greater than my present positive index and after operation erases it.

Please Help !!!

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

    I think itr = -1 causes a problem; what do you do when neg becomes empty?

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      neg will never become empty because the sum of all elements of array is 0.. So vector pos and neg will become 0 at the same time.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Actually, I printed itr immediately after

        auto itr=lower_bound(all(neg),pos[0])-neg.begin(); if(itr>=sl(neg)) itr=sl(neg)-1;

        and I did see itr = -1.

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Ok, you're right.. When I added if(itr<0) break, the code worked, Thanks for Help !! b/w how did you debugged the code.. When I was trying to print it was giving run time error and I don't know how to use debugger..

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

            You said your code worked on onlinegdb, so I tried it there. It did not give a runtime error there because of how it handles neg[-1], perhaps.

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

My submission for Div2 D Tree Tag gives WA on pretest 2.

I checked the cases in below order:

  1. If db < 2*a + b. Alice Wins

  2. If distance of Bob from Alice <= da. Alice Wins.

  3. If diameter >= db. Bob wins, otherwise Alice Wins.

Is there anything I'm missing(as per editorial I think not) or my implementation has a bug?

submission : 92063203

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

    In case 3,even if diameter is smaller than db, Bob can win because min(diameter, db) needs to be greater than 2*da.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Got it. Thanks :)

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I confused why this solution fails for Div2 D in the pretest 2

      The Algo, I am using to get diameter is

      • Find a leaf node

      • Do DFS to get the farthest node to it

      • This node will be one endpoint of diameter

      • Find second diameter endpoint by doing a DFS again

      My Submission

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please help me find the type of input my solution is failing in Div2C. It shows wrong answer on 2343rd case in test case 2.My Solution

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    would you explain what you are doing in your code?

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I'm grouping the characters in the string with respect to their position modulo k. If in any of these groups both O and 1 is present output NO. If only 0 is present add the size of this group to a variable called zero. If only 1 is present then add the size of the group to variable called one. Finally if n is even check and if either one or zero is greater than n/2 answer is NO or if n is odd and either one or zero is greater than n/2 + 1 answer is NO. Else the answer is always YES.

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

    I think your code fails the following case

    1 6 4 110011

    Your code gives No whereas the answer is Yes. Hope this helps!!!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D is was stated "Note that when performing a move, a player only occupies the starting and ending vertices of their move". Then shouldn't Alice win on his second move when 2 * da >= dist(a, b)?

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

    I think it means that the players 'teleport' instead of walking along the tree

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If after at most inf moves, Alice and Bob "occupy" the same vertex, then Alice is declared the winner.

      I assumed I have to consider both starting and ending node of one's last move :facepalm:

»
3 weeks ago, # |
  Vote: I like it +91 Vote: I do not like it

I think I have superpower, no matter how much time do I have, I can still solve a problem in a minute AFTER the contest ends))

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why didn't this work in div2 D 92059623?

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it +7 Vote: I do not like it

    You should use 2*da >= db instead of 2*da > db in line no 71.

    Test case:

    1
    3 1 3 1 2
    1 2
    2 3 
    
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sorry, wrong submission 92060277

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

        if(*min_element(dp.begin(), dp.end()) <= da) I think, this is the bug in your code.

        Test case:

        1
        6 2 5 2 5
        1 2
        1 3
        1 4
        4 5
        5 6
        
        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          I confused why this solution fails for Div2 D in the pretest 2

          The Algo, I am using to get diameter is

          • Find a leaf node

          • Do DFS to get the farthest node to it

          • This node will be one endpoint of diameter

          • Find second diameter endpoint by doing a DFS again

          My Submission

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Really good contest!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Div2 C has appear in earlier Contest on Codeforces itself(k periodic string)

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

I just don't get it. Why cant I solve problems like today's Div2-B? I mean Mathy questions like these. What should I do to solve such questions? What tags should I solve, or what question types? In fact, what is even this category — Greedy + math, Math, Problem solving?

Any one who was weaker on such problems and now comfortable in them, can you share what you practiced for these?

I am not so bad at CP that I should not even be able to solve it in 2 hours. Its just the approach doesn't strike me. I look at the test cases, develop some method to at least have a functional code for the visible test case then try some cases of my own. Finally when I cant think of any test case that might fail for my code, I submit just to see Wrong answer on Pretest 2. I know this is not the best of the methods but that is just how it happens with me. :(

Some insight please!

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it +7 Vote: I do not like it

    Dude, you need to relax. If you try to rush things during the contest you will not solve the problem!!! When you read a problem, 99% of the time you will have no idea how to solve it. But don't panic!!! First thing you should do is to read statement very slowly, identify all details that look important. Then stay away from the computer and take a sheet of paper to try some test cases. Always solve a problem on paper first!!!

    You need to be organised with your notes, otherwise you will get confused. Use as much paper as necessary, don't restrict yourself to tiny margins.

    You need to look for patterns you have seen before. This requires PERSISTENCE, leave no stone unturned. If making an assumption helps, do it! Breaking the problem in cases just gives you powerful assumptions to work with.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I agree this is nothing to panic. Thanks there! It just gets a bit frustrating when you know you are capable enough to solve it but still fail. I agree with the persistence thing and I also agree that practice is the only key but I also want to practice smartly!

      If something is above my level, I read the editorial and try to upsolve it but for such problems, I think there has to be something cleverer that you can do rather than just practicing a lot.

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

In div2D Tree Tag

initially, we have to check case 1 that is fine as Alice has the first move

why do we need case 2 as for every test case will fall in either case 3 or case 4?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If $$$2da \geq \text{tree diameter}$$$, the answer is Alice even if $$$db > 2da$$$

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

      Thanks! I got it, db will not matter as bob is limited by the diameter of the tree so he can't use his db to full extent to escape.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

s=[f(1,r),f(2,r),…,f(n,r)] ?

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

For problem Div2 D my logic was similar to the editorial. Yet, I got WA on 274th case in the second test case.

I would be much obliged if someone could go through my code or give me some test case where my code fails.

Code

Also adding the link to my submission Link

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

The contest was well balanced. Thank you for organizing it.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

92082520 I’m very confused about this wrong submission. Anyone can help me? Thanks!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone have an intuitive solution for Div2 B?

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    The solution I wrote in editorial is not very intuitive, but I chose it because it is easier to prove. Here is another way to view things:

    You can visualize $$$a_i > 0$$$ as a pile of $$$a_i$$$ tokens, and $$$a_i < 0$$$ as a "gap" that need to be filled with $$$|a_i|$$$ tokens. You want to make everything flat.

    Free operations move tokens to the right. Imagine walking on the array from left to right, having a "bag" of tokens. When you encounter a pile ($$$a_i > 0$$$), put all these tokens in your bag. When you encounter a gap ($$$a_i < 0$$$), empty your bag here as must as you can.

    This is equivalent to doing $$$\text{sizeBag} := \max(\text{sizeBag} + a_i, 0)$$$.

    It is "intuitive" that you use free operations as best as you can. The final answer will be the final size of your bag (the number of tokens you couldn't put into gaps).

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

    For free operation ->

    i<j and you are to increment aj and decrement ai, so by decrement if you have to make ai zero then it should be positive number right. so a negative number can make positive numbers of past towards zero in free.

    	int positive = 0;
    	for (auto i : a) {
    		if (i > 0)positive += i;
    		else positive -= min(positive, abs(i));
    	}
    	cout << positive << endl;
    
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Thanks. I find the backward version also fairly intuitive :

      long long sum_pos = 0;
      long long sum_neg = 0;
      for (int i=n-1; i>=0; i--)
      {
          if (a[i]<0)
          {
             sum_neg += a[i];
          }
          else if (a[i]>0)
          {
             long long free = min<long long>(a[i], -sum_neg);
             sum_neg += free;
             sum_pos += (a[i] - free);
          }
      }
      cout << sum_pos << endl;
      
      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Backward version can be a bit clearer.

        Walk through a, if last (current) element is negative then accumulate it to accum — there will be "free of charge" turns to make it zero. If it positive and accum + last is positive then we need "paid" turns.

        My submission 92031517 (I use Kotlin). Note reversed() method in the read data part.

        val n = readInt()
        val a = readArr(n).reversed()
        
        var accum = 0L
        var ans = 0L
        for (ai in a) {
            accum += ai
            if (accum > 0) {
                ans += accum
                accum = 0
            }
        }
        println(ans)
        
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can't we do 'C' using the Sliding window technique?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice problems and thanks for fast result and fast editorial!!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why I was getting TLE plz can anyone help in test case 9 Code:https://codeforces.com/contest/1405/submission/92085005

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    prob B

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

      the complexity of the algorithm is n squared and do not write such shit code because no one will ever help you look for errors in such code

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        OK bro thanks for helping

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        How to make a code simple? Is my way of writing code shit or my logic is shit???

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          u code style is shit :), check example my code or code of a famous coder (red mb)

          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Bro can u explain your approach to me how you managed to solve this question in O(n)

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

This round made me blue, so can't complain. Nice and fast editorial :)

»
3 weeks ago, # |
  Vote: I like it +79 Vote: I do not like it

Authors solution for E is pretty cool, but there were a similar (but much harder) problem in ptz winter 2020 which inspired me for this solution:

Let's decide for each cell will we cover it by a vertical (V) line or a horizontal (H) line. For test form the statement it will be like this:

V.VV
VHH.
VH..

We can see that we pay for horizontal line once in its beginning. So we pay for ".H" or "VH". Similarly for vertical lines. So we have to choose one of two options for each cell, and we pay something for choosing different options for some pairs of cells and also something fixed for each choice. That's standard min-cut problem.

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

Why this solution fails My submission I am trying to debug it from the last 1.5 hours, Fully exhausted now, Any help will be highly appreciated! UPD: I got it!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

i am getting WA on 829th token of second test case in Div 2C https://codeforces.com/contest/1405/submission/92087888 please assist me

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please help me understand what is the error in my code?

The submission id is: 92058038 .

Any help would be appreciated.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

what if we have to tell "weather Alice can capture Bob in almost k turn" or "what is the guaranteed min turn in which Alice can capture Bob", in question D Tag Tree.

the following will be the ans, right ? or Am I missing something

case 1 : 1 turn.

case 2 : 2 turn .

case 3 : -1 (never)

case 4 : ceil(dis(a, b) / da).

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In div2A if I reverse the array of odd length then the middle element remains in the same position, can anyone explain how reversing gets the correct answer, I know I am sounding dumb but I got this doubt. I actually didn't get a thought about it when I submitted my code.

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

    The permutations are considered different if they disagree at some index, not all indices. $$$[1,2,3]$$$ and $$$[3,2,1]$$$ are different permutations.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I am happy for this round. I became Pupil from Newbie :)

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone provide a DP based solution for Div2/C

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

please help me with this. Div2 D. it's showing runtime error on test-2. https://codeforces.com/contest/1405/submission/92077516 variables meaning- ans=initial dist from alice to bob. path=dia of tree.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What to do if I can't understand the proof of div2-b task? How do you upsolve if you can't understand the editorial?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem 2E, what exactly is the BIT you want to maintain? Because s is already weakly decreasing, binary search on s for the lmax will be log(n), but the tutorial said naive binary search needed log^2. Very confused. Can someone help me

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    An operation on BIT takes $$$\mathcal{O}(\log n)$$$ time, and binary search do $$$\mathcal{O}(\log n)$$$ operations on the BIT. Hence, finding $$$l_{\max}$$$ with this method $$$\mathcal{O}((\log n) \cdot (\log n)) = \mathcal{O}(\log^2 n)$$$ time.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I mean, wouldn't BS on s just be fine? Or is s just the bit?

      Do you mean s[i] = f(1, r)+f(2, r)+....+f(i, r)?

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        s is a BIT, not just an array. We need to both "increment on prefix" and "get an element" in $$$\mathcal{O}(\log n)$$$.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      My current understanding:

      For each step, (if necessary) use binary search on s to find max, and use a BIT which is the prefix sum of s to increment [1, l] by 1?

      So I don't know why binary search is on the BIT? Is something wrong?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

A nice trick of divC!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

https://www.youtube.com/channel/UCBStHvqSDEF751f0CWd3-Pg?view_as=subscriber

Video Editorials of all latest contests , all questios . Even courses for various coding techniques will be taught . Do share , subscribe and like

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

sorry hugopm for bothering again:

In tutorial: Note f(l, r) the maximum number of elements we can remove in the subarray a[l...r] (zero if l>r). During our iteration over r, we're going to maintain the answers for each l: s=[f(1, r),f(2, r),...,f(n,r)] <-------- here do you mean f(l, r)? Also, do you mean for each l we maintain s_l=sum of everything in the bracket?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't really understand why solution for Div2. B is working.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Would it be possible to solve Div1C using Mo's algorithm ? I misread the ai = i condition and thought that ai = i should hold for the sub-array [L, R] (with indexes from the sub-array).

For Mo's algorithm, addition/deletion from the end point should be pretty simple while addition/deletion from the beginning should be doable by using a deque(I'm still a bit confused about this part)

The TL of 4s seemed pretty generous so I got stuck on thinking about Mo's Algorithm ;-;

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

    Mo's Algorithm doesn't work there.Because when deleting/adding from the begining , the effect will be quite complex!Though deleting/adding from the end is easy!

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yeah i just realized that while trying to code the solution ;-;

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

i'm still not able to understand the tree tag question and then it is obvious not get the tutorial to can someone please suggest me what are the prerequisite in need to know or if someone is uploading it's video tutorial then please share the link ... thank you in advance

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

    Some points to note in this question are-

    ->If Alice can catch Bob in first move then she wins.

    ->Bob wont try to move unless Alice comes to catch him.

    ->If the length of longest path on the tree (i.e. the diameter of tree) is <= twice the length of range of a (i.e. da) i.e. Alice can reach the midpoint of the diameter and if then Alice has her range such that she can reach both the endpoints of the diameter in one jump then she will definitely catch Bob because Bob must be in her range (as diameter is already the longest path).

    ->If Bob can in a single jump go from a vertex u to vertex v such that Alice can only have a single vertex (either u or v) in her range then Bob can keep jumping from u to v (when vertex u is in range of Alice) and v to u (when vertex v is in range of Alice).

    ->If Alice can have both the vertices u and v in her range in a single jump then she will catch Bob in the end.

    ->Alice will try to stay (da-1) distance away from Bob in order to maximise the distance that Bob needs to escape her.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

One more hack case for D: 1 7 3 6 2 3 1 2 2 3 3 4 4 5 5 6 5 7

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1405/submission/92122526 My submission for Div2, C problem is giving wrong answer on Test set 2 (156 case). I am counting number of ones, zeros and question marks, in substring of length k and assigning value of 1 or 0 to a question mark only when a substring contains just one question mark.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone please explain in brief how the diameter of tree has been calculated with only one dfs in the above implementation in Div 1-B / Div 2-D problem Tree tag. Thanks in advance.

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

    For each node, you basically calculate the sum of the two longest paths from it (or one if it's a leaf) except for the path to it from the initial vertex. If the initial vertex is a part of a diameter-length path, it's obvious this will return the right result.
    If the initial vertex is not a parth of such path, consider the first vertex you encounter during the DFS that is indeed a part of such path. Let us denote that first vertex by u. The counter intuitive part is that you don't consider the path from the initial vertex to u — BUT, since all the vertices on the path to u were, by definition, not a part of any diameter-length path, they do not need to be considered. You will then take the sum of the two longest paths from the current vertex, not including the path to it, and that will be the diameter.

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

is it rated? my change has gone away..why?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I have a problem for Div1 B: if $$$tree\ diameter\leq 2*da$$$ then Bob can't win.But why if $$$tree\ diameter > 2*da$$$ and other cases are all satisfied ,Bob is sure to win?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If diameter > 2*da then bob every time go to that long diameter place and if distance between them <=da then bob goto to the other side of that diameter..so alice can not touch him anyway.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But can you make sure that Bob can walk to the diameter?

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Bob will run to the leaf node away from Alice(it can be proved that there will always be one), from there he will make a jump,if alice cant catch him in first move,he can't catch till he reaches leaf node as db>da and he is running in opposite direction.

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          But if Bob reach a leaf ,he can't find a node which he can reach but Alice can't?

          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            sorry I didn't get it, bob reaches the leaf node and which node should he find?

            • »
              »
              »
              »
              »
              »
              »
              3 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              The node that Bob can reach but Alice can’t reach

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

                I am not sure if I get your question properly, but once bob reaches the leaf, Alice should be at a distance of atmost a(if greater than 'a' we will wait for him to come nearer), then we make a jump, since we are at the leaf node we can jump at a distance of min(db,diameter) and this distance should be greater than 2*da, as it should cross Alice and he should not catch us in the next move also. Root the tree at bob's initial position, it will be easier to visualize

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Ok thank you very much

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Or can you prove it can't happen?

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

It's a bit late, but I have a solution for Div2E/Div1C that isn't that practical, but I find rather cute (it was also the first thing I thought of).

Instead of doing what is in the editorial, consider solving the problem without constraint of $$$x$$$ or $$$y$$$. The following greedy algorithm works: At every step, choose the highest $$$i$$$ to remove if possible. The reason is obvious: if there are multiple with $$$i=A[i]$$$, the only one that won't force the others to become $$$i<A[i]$$$ is the largest. Therefore define a prototypical sequence of removals $$$R$$$, from the greedy algorithm. (To actually find $$$R$$$, I used a lazy propagation segtree with pairs — there may be an easier method.)

When there is the constraint of $$$x$$$, notice that after the first element $$$R[i] \leq x$$$, the rest of $$$R$$$ after it cannot be removed. We can have prefix min on $$$R$$$ and binary search for this element, let's call it $$$k$$$. Also, for the constraint of $$$y$$$, all elements where $$$R[i] \geq y, i<k$$$ cannot be removed as well by definition (but our inability to remove them doesn't affect our ability to remove other elements). To get this count we can answer queries offline in increasing order of $$$y$$$ using BIT.

Write-up is long, but the idea is really simple. However, implementation is some mess.

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

    Yeah, I actually came up with this simulation solution before the official BIT-only one.

    You may want to check my implementation, which is short and fast. The trick is that, in order to decrement a suffix beginning at $$$i$$$, we can decrement the whole array, and when we go down the path leading to the leaf $$$i$$$, each time we go to the right child, we add $$$+1$$$ on the left child. Hence, we can do "descent in the tree" (finding rightmost zero) and "decrement on suffix" in a single function "pop".

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is this algorithm to find the Diameter of a tree is correct

  • Find a leaf node, say N

  • Do DFS to get the farthest node to it

  • This node will be one endpoint of diameter, say p

  • Find second diameter endpoint by doing a DFS again from this endpoint p

But for me it fails, I don't know why My Submission

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your code is long, so I couldn’t totally tell, but did you make sure that the first dfs and second dfs don’t overlap? If they do, the actual diameter is shorter than it would output.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Actually both DFS are copies of each other, one(DFS1) returning "one end of diameter" and the other(DFS2) computing the Diameter by doing a DFS traversal from this endpoint

      I'm sure my BFS code is correct..there aren't any issues in it

      Actually I'm keen whether this algo/method will work...finding one endpoint then computing diameter from it

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

    There are two bugs in your code:

    1) BFS is wrong. Line no 26 should be x.d = 0;

    Testcase

    2) DFS2 is wrong. Line no 103 should be x.d = 0;

    Testcase

    Bonus: In DFS1 also, line no 64 should be x.d = 0; but it won't affect the final solution because x.d is increased by 1 for all nodes and here you only concern about the node number with max x.d.

    AC Submission : 92202644

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please tell where did I go wrong in this solution for div2C?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In the tutorial of 1405D — Tree Tag, the inequality in Case 3: dist(b,a)+dist(a,v)≤da+(da+1) confuses me. We already know that dist(a,v)=da+1, so the above inequality is saying that dist(b,a) <= da, but how can this be true? If dist(b,a) <= da holds, then we are already done in Case 1 and won't go to Case 3, can someone help me to understand that? Thanks in advance.

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

.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice Editorial

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

Fast Editorial & Ver Concise....!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Imagine Alice and Bob actually playing Tree Tag game for 10^100 moves.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1405/submission/92515764 why it is giving TLE? i checked for hours for potential infinite loop in my while loop. but both positive_index and negative index are always decreased no matter what the condition is. or am i wrong??

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please give me hack cases for Problem C Div2. My solution is not working at a point and I can't figure out why...I'm a complete beginner so if someone is looking at my code then I'm sorry about the quality of code. Any help will be much appreciated. 92764694

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

The tutorial for B is so messed up.

»
36 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't know have anyone here now , but i got TLE for pro D.

This is my code :https://ideone.com/hwulqr

i can't fix my code although my solution is very simple . I thinhk i wrong somewhere in my code . If you see this comment , you can help me ? -- Sorry for my poor English .