FastestFinger's blog

By FastestFinger, 4 months ago, In English

1370A - Maximum GCD

Tutorial
Code

This problem was prepared by the_hyp0cr1t3

1370B - GCD Compression

Tutorial
Code

This problem was prepared by Ashishgup and ridbit10

1370C - Number Game

Tutorial
Code
Relevant Meme

This problem was prepared by FastestFinger and Ashishgup

1370D - Odd-Even Subsequence

Tutorial
Code

This problem was prepared by Ashishgup

1370E - Binary Subsequence Rotation

Tutorial
Code

This problem was prepared by smartnj

1370F2 - The Hidden Pair (Hard Version)

Tutorial
Code
Relevant Memes

This problem was prepared by FastestFinger and Ashishgup

Meme credits: ridbit10 and the_hyp0cr1t3 and FastestFinger

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

»
4 months ago, # |
  Vote: I like it -182 Vote: I do not like it

Maths only round

»
4 months ago, # |
  Vote: I like it +25 Vote: I do not like it

And the fastest editorial award goes to....

»
4 months ago, # |
  Vote: I like it +15 Vote: I do not like it

FastestFinger actually has fastest fingers... Thanks for the fast EDU!

»
4 months ago, # |
Rev. 2   Vote: I like it -16 Vote: I do not like it

Wow! Quickest Editorial ever provided. Hats off Ashishgup

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

    In case u don't know, once Radewoosh uploaded tutorial before the starting time of the contest ! so technically it's not the fasted tutorial :p

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

      oh really? what action did CF take then? was round made unrated or something bigger?

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

FastestFinger be like

»
4 months ago, # |
  Vote: I like it -86 Vote: I do not like it

CodeForces? More like MathForces

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

    How was this mathforces lol?

»
4 months ago, # |
  Vote: I like it -10 Vote: I do not like it

i got stuck in problem C because i thought it would get tle for checking primality for some numbers as large as 10^9

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

    Lol. It would be fine if you just check up to sqrt(n) though.

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

      plz post your solution for problem C

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

        I think you missed some corner cases. Try cases where n==1, n==2, n==6, and n==18. Nevertheless, here is my submission 84452415 (It's in Java tho)

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

        Just prime factorize the number. If two is not a prime factor which means odd number AG wins. Else if 2 is a pf and its power is 1 then we have to check the powers of other pf's. Let sum of other powers be 'Count'. If its AG turn he will form an odd number with count — 1 powers and divide so that FF get a number 2*(prime number) so only option he has is to divide by the prime number and AG wins. Rest of the cases can be covered in similar way. You can check my submission.

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

          I was doing this way only dont know why wrong answer

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

        try this video solution for clarity: (https://youtu.be/6vVDl0e5jjk)

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

        Hey here is a simple video solution to problem C.

        Click here for Video Solution

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

      yeah, you are right, i feel so stupid

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

      In the editorial, why they have taken min(n,50,000) in case of prob C?

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

    I did that ..but wrong ans

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

    Primality checking is O(sqrt(n)), so 10^9 should be fine.

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

      this is my solution 84504888

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

        Try out this case: n = 30. Ashishgup should win because if he removes an odd prime, say 3, then FastestFinger has no choice but to remove the other odd prime, 5, leaving Ashishgup with 2 and giving him the win.

        The case where there is more than one odd prime (powers are distinct) and exactly one power of 2, Ashishgup will always win, because he can remove all but one of the odd primes, and Fastestfingers will have no choice but to remove the last odd prime, leaving Ashishgup with 2.

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

    I too did got stuck in the same thought, since you can't make a prime table with sieve method and doing brute method will obviously wouldn't work (stupid me :P) so I went back to check if I did some mistake while coming up with a pattern only to waste 20 valuable minutes to understand my foolish mistake in undermining sqrt(n) method of finding prime

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

      You can use this algorithm for checking prime instead of going for SIEVE OF ERATOTHENE!!

      bool prime (ll n) { if(n == 2) return true; for(int i = 2; i <= sqrt(n); i += 2) { if(n % 2 == 0) return true; if(i == 2) ++i; else i += 2; } return false; }

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

        It can work fast for power 10 ^ 9 range queries by lopping only 32 times or less :) cheers.

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

          How would it loop only for 32 times? :O

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

            Oh i am so sorry i made a mistake? Lopping will happen 100 to 110 times in 10 ^ 9 range totally!!!.

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

    why to check primality if n is odd then ashish wins because he will divide the number by n

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

      try this video solution for clarity:(https://youtu.be/6vVDl0e5jjk)

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

      You don't need to check for primality if N is odd. If N is odd, Ashish wins by dividing the number by itself, as you said. You need to check for primality if N is even. Suppose N is even and N > 2(if N = 2, Ashish wins by substracting 1), then Ashish can't subtract 1 from it as N — 1 would be odd, leading FastestFinger to win. Another thing that you need to notice that if N is a perfect power of 2, i.e. N = 2^x and x > 1, then Ashish always loses as he has no other option other than to subtract 1 from N. So if N is even, all he can do is to divide by an odd factor. Since N is even and has some odd factor, we can write is as N = 2^x * P^y, now there can be two further cases down from here, if x > 1, then Ashish can simply divide N by P^y and he wins with ease. The problem comes when x = 1, Ashish can't divide N by P^y obviously, so, in order to win he needs to divide N by a number Q such that N / Q = 2^x * R, where R is a Prime Number, if this can happen then Ashish wins because FastestFinger would have no option other than to divide N / Q by R, or subtract 1 from it(either case Ashsish FTW). This can happen only if P^y is not a prime.

»
4 months ago, # |
  Vote: I like it -27 Vote: I do not like it

I am amazed to see Problem A solution ..I mean WTF!!!!!

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

A Quick editorial with 0 available tutorial at first few minutes. (x

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

Can someone help me figure out why 84488594 is failing for problem D? Seems like I have the main idea..

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

    Yes please! For the love of god please someone tell me what pretest 10 is :((

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

    Try this case: 4 4 1 4 3 2 Your program gives 2 but the correct answer is 3 (I made the same mistake in the contest :P)

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

      Thanks. Figured the mistake. Looks like I'm going to be stuck at 1730ish for a while lol.

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

        What was your mistake can you tell?

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

          Basically, if we only enforce invariant that the smaller subsequence cannot have consecutive elements, you might end up with two consecutive elements inside the bigger subsequence.

          Not sure about you, in the counterexample that is provided my solution picked out 1 2 as the smaller subsequence. But the correct smaller subsequence is 1 3

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

          Codeforces Round #651

          Problem A and B

          Problem C

          Problem D

          Problem E check it out guys for complete understanding

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

          if k is odd then we can't choose the Nth element to be part of even indices, similarly if k is even we can't choose the Nth element to be part of odd indices

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

I almost got Problem C. I thought I followed the right logic. Can someone explain why it doesn't work? (failed on pretest 2)

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

I think they create the editorial before creating the problems

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

Wowwwww fast editorial! And nice problems!

»
4 months ago, # |
  Vote: I like it -11 Vote: I do not like it

Maths only round?

Yes!

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

anone can tell how to get the intution behind using binary search in problems like D?

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

    Do lots of problems w/ Binary Search tag.

    I've found there are two types of Binary Search Problems: problems you can solve with lower_bound / upper_bound, and problems similar to the one in this contest.

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

      exactly .....like suppose you do it with tags mind will look in that direction only .......how to get the idea automatically is what i am asking

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

        I find that typically for maximization and minimization problems, I try to see if DP or greedy work. If not, then try binary search and brute force.

        I guess it goes without saying that this requires you to come up with possible solutions and also counterexamples quickly before you start coding.

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

        looking at the constraints might also help..since here the constraints are 2*10**5...so we can use O(nlogn)..which usually means we can use any kind of sort in the answer or we can use binary search with O(n) for each iteration of the binary search

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

      can you suggest some problems like these ones?

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

        1208B, 1077D are the ones I've done on CodeForces

        875 on LeetCode is also a good one.

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

        You can try these problems in Lightoj, they can help :D

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

    I will share my idea. Whenever you see a monotonic function (step boolean function in problem D is monotonic) you can apply binary search. In fact monotonicity leads to the correctness of binary search.

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

@Ashishgup how can you prove that binary search would definitely work in problem D?

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

    Define $$$f(x)$$$ as $$$whether$$$ $$$it$$$ $$$is$$$ $$$possible$$$ $$$to$$$ $$$make$$$ $$$answer$$$ $$$<=$$$ $$$x$$$. Clearly, if $$$x$$$ works, then $$$(x + 1)$$$ works as well. You can easily check whether $$$f(x)$$$ is true in $$$O(n)$$$. Hence $$$binary$$$ $$$search$$$ $$$for$$$ $$$answer$$$ works.

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

Can someone give a better mathematical intuition of the problem B? Never mind got it :D

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

    Now total elements are even (2n). Which means possibilities are: even no of even numbers and even number of odd numbers | odd number of odd numbers and odd number of even numbers. Now if it is the first case simply remove 2 elements from any one but if its second case remove 1 element from both. At the end we have even number of even numbers and odd number of odd numbers. First choose pairs from odd set and then choose pair from even set. All elements will be even hence gcd is at least 2.

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

    if you add two even numbers you get an even number. if you add two odd numbers you get an even number. So if we want gcd(b1,b2,b3...)>1 we can see that if every element is even this is true.

    now imagine we turn the array into 0 and 1 numbers, where 0 represents an even number and 1 represents an odd number.

    now we will begin with a small array size and see why it always works. if n = 2 our array will look like 1111 1110 1100 1000 0000 we only need "half — 1" pairs and it is clear in all cases we can pair a (0and0) or (1and1) at least once. if n = 3 111111 111110 111100 111000 110000 100000 000000 again we see that in this case we can pair them again to get n-1 pairs.

    Here is a way to see that you will always be able to get n-1 pairs. Start with an all odd array

    1...1 here u can make n pairs.

    if we switch one odd number for an even to get

    1...0

    u can now make n-1 pairs

    if we switch another odd to even to get

    1...00

    u can now make n pairs again (because u can now pair 0s to get an even)

    if we switch another odd to even to get

    1...000

    u can now make n-1 pairs...

    if u see the pattern we can always make at least n-1 pairs. So the question simply wants us to pair as many even numbers and odd numbers together until we have n-1 pairs then we stop. The reasoning above is kind of like induction, we start with a base case (all odd numbers) and show that if we keep switching one odd number to even we will always have enough pairs (n-1 pairs).

»
4 months ago, # |
Rev. 2   Vote: I like it -44 Vote: I do not like it

Deleted

»
4 months ago, # |
Rev. 2   Vote: I like it -42 Vote: I do not like it

3 reasons why people like Ashishgup should be permanently banned from problemsetting:

1) Round 646

2) Round 648

3) Round 651

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

    get a life bro you had only 3 submissions credited to your account , atleast grind more and be in an order to say sth to the problem setters cz right now you are in no position to say so

»
4 months ago, # |
  Vote: I like it +49 Vote: I do not like it

Why always asking names as output in C ? instead we can use Yes, No that would be easy and convenient.

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

I tried sieve on A.

//Ashishgup gets me again cause upto 10^6..

anyways still better than the horrible 2 no solves streak..

»
4 months ago, # |
  Vote: I like it -33 Vote: I do not like it

Today Problem C

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

On problem E, does anyone have an intuitive explanation why LCS doesn't work?

I think my submission LCS might recommend that we rotate an odd parity subsequence (which is useless). But my brain is fried so I can't come up with a counterexample.

Failing submission:

84510608

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +7 Vote: I do not like it
    10
    1100100110
    0011011001
    

    Answer should be 3 (your program gives 2):

    • Rotate indices $$$0, 3, 4, 5, 8, 9$$$
    • Rotate indices $$$1, 2$$$
    • Rotate indices $$$6, 7$$$

    LCS doesn't work because you have to account for both 101010... subsequences and 010101... subsequences, and LCS causes you to overlap them (indices 4-9 above).

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

      Great explanation! Thank you very much :D

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

can someone help me with my code for C, I think I did what's in the editorial but in a different way 84494512

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

Can someone explain why we cannot solve C using greedy approach? I tried to maintain 2 different array/sets, and started inserting numbers into them in increasing order, while ensuring that no 2 numbers with consecutive indices land in the same bucket. Final answer should then be min(max(bucket1), max(bucket2))?

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

    I think you're referring to D.

    Let's say n=4 k = 4. **Suppose your sorted array (value, index) pairs are as follows : (1, 2) (2, 1) (3, 3) (4, 4)

    Your solution ends up selecting values [1, 4], max=4. We want [2, 3], max=3.

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

      Hey, thanks for your reply. Although I think I might have failed to explain my solution properly. It'll work as follows:

      (1,2), (2,1), (3,3), (4,4)

      Bucket1: empty

      Bucket2: empty

      -> I look at (1,2), insert it in first bucket.

      -> I look at (2,1), try to insert it in first bucket, but it already has an index which is adjacent to index of current element that is being considered, so I insert it in bucket 2.

      -> I look at (3,3), insert it in first bucket

      -> I look at (4,4), try to insert it in first bucket, fail, insert it in second bucket.

      The buckets finally are [1,3] and [2,4], out of which I return 3.

      This is the link to submission in case it helps: 84501650

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

        You can try

        6 6
        1 2 1 5 2 1
        

        I think in general, your solution puts the 1 1 1 in one bucket, but the other bucket becomes invalid 2 5 2 has adjacent elements

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

Here's my simpler(imo) solution for F: find a node in the path as described in the editorial, note that this also gives you the lenght of the path you have to find. Keep the delimiting nodes of the path u,v at the beginning both equal to the node you found. While dist[u][v] != solution lenght, make a query with all nodes x with min(dist[u][x],dist[v][x])>=(solution lenght-dist[u][v]+1)/2. At least one of these nodes must be in the solution, so with each query you at least halve the remaining lenght of the path. So you will use 1+log2(path lenght)=11 queries at most. I did not get AC, and I think that is only because I did not read correct/incorrect strings, I'm pretty sure this should be AC... Ok, proofed by AC by reading the strings

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

How can we prove formally for question D (Odd-Even Subsequence) that the found element while doing binary search always exists in the given array? I tried on some sample tests its working fine, but I am not able to correctly identify why the element does exist in the original array.

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

    In the last phase of binary search, it allows mid = a[i] (where, i is any position in array).

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

    The boundary where check(x) fails and check(x+1) passes can only exist if x+1 is in the array (otherwise the result of check wouldn't change).

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

[deleted]

»
4 months ago, # |
  Vote: I like it +9 Vote: I do not like it

What the f---! Binary searching over the answer is the COOLEST idea!! Thanks for the quality questions!

WOW!! I learn so much!

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

When I submitted A and B it shows "Pretests passed" and which took my whole time then I think this time i am not able to solve a single question but now I just checked both the solution get accepted.

No problem next time i try my best great question by the way.

»
4 months ago, # |
  Vote: I like it +14 Vote: I do not like it

le editorial usually : come again another day

le editorial with FastestFinger : fast as F boi

»
4 months ago, # |
Rev. 5   Vote: I like it -13 Vote: I do not like it

Ignore this comment #Brainfreeze

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

    The highest odd factor is 15.

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

      My bad! Thank you for the clarification

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

      Please help me with the tutorial for D.

      I cannot get what does binary search over the "answer" mean in the key idea of the tutorial?

      I am posting it here since I don't know how to get my doubt to you other than this way.

      • »
        »
        »
        »
        4 months ago, # ^ |
        Rev. 2   Vote: I like it -8 Vote: I do not like it

        sort the values in the given array.

        lets index it from [1..n] where A[i] <= A[i+1].

        Let left = 1, right = n.

        Now, take mid = (left+right)/2. and check whether you can get a subsequence with A[mid] as min(max(odd_indices),max(even_indices)), if you can, then your answer lies in [mid,right] else it lies in [1,mid-1].

        EDIT: I am not suggesting to use the sorted for check() function. check() function should be used with original array. I am suggesting Bsearch on sorted array (instead of Bsearching from 1 to 10^9).

        Would recommend you to read about binary search and its applications for more clarity.

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

          Sorry, I may not have been able to clearly state my question. I appreciate your reply.

          I know how to implement binary search but was confused with the explanation in the tutorial which asked to binary search the "answer". I assumed the answer meant binary searching the original array and could not understand how is binary search possible for an unsorted array.

          Later, after going through all the comments I found that people were talking about binary searching from 1 to 10e9. After mulling on it for a good amount of time I got that the "x" of the tutorial was indeed to be found using binary search (but not on the array given).

          So, in all, I was able to upsolve the problem

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

          If you could kindly say, why are they binary searching on 1 to 10^9 instead of the sorted array? Thanks in advance

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

            I don't think there is any specific reason for that. Maybe it is just done to reduce the complexity of explaining the solution.

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

              Actually, why is there not a probability for that to give wrong answer?

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

                Why should it give a wrong answer? There isn't probability thing going on here..

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

                  Because it may satisfy for some x that is smallest but not in the array.

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

        If we have a $$$monotonic$$$ $$$function$$$ $$$over$$$ $$$a$$$ $$$range$$$ and it is $$$true$$$ $$$for$$$ $$$some$$$ $$$prefix$$$ and $$$false$$$ $$$for$$$ $$$some$$$ $$$suffix$$$ of the range and it is possible to check it's truth value at a point in the range, then you can search for the point where the function's value changes from true to false by $$$binary$$$ $$$search$$$. The idea being that if for some point it is true, then it will definitely be true for values less than that point.

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

          Sorry, I may not have been able to clearly state my question and I appreciate your reply.

          I know how to implement binary search but was confused with the explanation in the tutorial which asked to binary search the "answer". I assumed the answer meant binary searching the original array and could not understand how is binary search possible for an unsorted array.

          Later, after going through all the comments I found that people were talking about binary searching from 1 to 10e9. After mulling on it for a good amount of time I got that the "x" of the tutorial was indeed to be found using binary search (but not on the array given).

          So, in all, I was able to upsolve the problem.

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

            great! .. actually u could sort the array and do binary search over it as well ..

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

              Yeah, it naturally occured to me after getting the idea of binary search uptil 10e9. In fact, once we sort the array we can fix the index k-1 as the upper bound in our binary search(i.e binary search between 1 to sorted_arr[k-1], where k is the length of the subsequence given as input)

              Just that I was mislead by the tutorial or maybe misread the tutorial.

              Anyways, thanks for your replies.

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

      In Editorial of D, while doing binary search at for all <=x elements at odd positions it is understood that all elements at odd position should be <= x but why are we not checking that max element at even places should be greater than x

      ans = min(max(odd pos) ,max(even pos)) = min( x , max(even posotion))

      should't max(even position) be checked to be greated than x

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

        If we find an odd sequence {$$$a_1 , a_2 , ..., a_t$$$} and its maximum value is atmost $$$x$$$ , then no matter what the even sequence is we can always say that the $$$answer$$$ $$$<=$$$ $$$x$$$ . Same goes for even sequence

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

      I was solving the interactive problem F1 and got WA on test case 3. When I went through the test case I found that there were more than n-1 pairs of nodes in the test case for all the subtests.

      Please, help me with understanding the tree diagram in such a case since as far as I know : a tree with n nodes has n-1 edges.

      This was my first interactive problem and debugging this would really help me with such problems in future.

      Here, is the link to my submission where you can see the test case 3: Code

      I am posting it here since I don't know how to get my doubt to you( @FastestFinger ) other than this way.

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

        The first two nodes are the hidden nodes not the tree edge.

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

          Okay, got it. Thank you.

          I would be able to debug it now on my machine.

»
4 months ago, # |
  Vote: I like it +11 Vote: I do not like it

ashishgup and his team are goats(greatest of all times)

»
4 months ago, # |
Rev. 2   Vote: I like it -14 Vote: I do not like it

.

»
4 months ago, # |
  Vote: I like it -25 Vote: I do not like it

The following is my recursive DP solution of problem 1370C - Number Game

84479320

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

    Fun Fact: naming the array "dp" doesn't make the it a dynamic programming solution

    Fact2: your dp[] value never gets reused.

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

      Thanks for the sharing the fun fact. I agree with you than naming an array 'dp' does not make the solution a dynamic programming solution. And I also agree with you that the dp[] value never gets reused for the same test case. However, in the multiple test cases problem, the stored value may be used if the even value $$$n \geq 4$$$ has been solved in previous test case.

      The following is a small test program for this solution which shows that the dp values are reused in the multiple test cases problem.

      Test Program

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

        Aaaaand using the array named "dp" over multiple testcases doesn't make it dp either. Just saying.

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

          Note that the array stores the XOR value between (p), the ID of the player to make the move, and the ID of the winner of the game, provided that both players make optimal moves. This solution of a sub-problem when $$$n \geq 4$$$ is an even number can be used by another test case that starts with $$$n$$$ or a larger value. Can you suggest more convenient names to the array and to this approach?

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

            Hey man, you can choose any name you like. Even the current name "dp" has nothing wrong in it. You can use the array re-using approach all you want, and yes it will save you at least a little time if you are given such an input that makes you re-use the array. All I'm saying is that it is NOT Dynamic Programming. Re-using a precomputed answer, you can call that memoization at best. You did good, solved the problem, got an AC, congratulations! But for the love of God, don't call it dp.

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

              Thanks for the kind correspondence. I appreciate your concern. I have always thought about dynamic programming to be among the approaches used to solve larger propblems in terms of the stored results of smaller related sub-problems. The following tutorial is very close to this point. DP

              It interesting that removing the unordred map did not change the execution time of the accepted solution. 84540538

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

In problem D, I didn't get how binary searching between 1 and 1e9 gives an answer which exists in the array? I understood the logic but isn't there a possibility where for a value x which is doesn't exist in the array satisfies the check condition?

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

    There may be cases where some $$$x$$$ satisfies the condition and isn't in the array, but the binary search finds the smallest possible $$$x$$$. It's never optimal to choose an $$$x$$$ not in the array because you can just use the largest value in the subsequence $$$\le x$$$.

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

    The loop invariant for the binary search is that check(lo-1, 0) || check(lo-1, 1) is always false, and check(hi, 0) || check(hi, 1) is always true.

    At the end of your binary search, lo == hi. At that point, you know that lo-1 is not a valid x, but lo = hi is valid. So, lo is the smallest possible answer.

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

Question C was very interesting

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

Is there any alternative solution for problem E?

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

    Well the main idea in my solution is same i.e. finding out the longest length of alternating 0s and 1s. I implemented it by deleting the successive index. Here is the link if you want to see it:

    https://codeforces.com/contest/1370/submission/84508975

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

      Sir, I try to guess. That you individually found out all the possible chains right? So you may have used sets??? What is the complexity of your soln?

      Like you will have to use lower bound on sets then again delete it so that's costly, how does your solution passes the timelimits?

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

    just make brackets out of 1 and 0 and find its depth. consider only positions where s[i] and t[i] different.

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

Explanation for C :

Cases when n is odd or power of 2 is clear , also corner cases n=1 and n=2 can be handled separately.

Now when n is even we can observe that :

let prime factorization of n be 2^a1..3^a2….5^a3….and so on

if a1>1 then

ashish can simple divide n by 3^a2…….5^a3 and so on and give it to fastestfinger. What can fastestfinger do now ? since n is now power of 2. he will have to subtract one and thus ashish will win.

but if a1=1 then

ashish can’t do this since only one two will be left and fastestfinger will just subract 1 and hence win.

So if a1=1 and n has more than one odd divisor ashish will win why ?

for example take n=30 =2*3*5

ashish -> divide n by 3

n=10;

fastestfinger->has only one option that is divide n by 5

n=2;

ashish subtracts 1 and hence wins.

that is ashish will always take (all odd prime factors product except one number (example for n=30 he takes either 3 or 5 and leaves 5 and 3 respectively) so that fastest finger will have to divide by that “except” and then ashish will win by subtracting 1.

else if there is only one odd divisor fastest finger will win .

example n=14.. ashish have to divide by 7 so then n=2 and fastest finger will win.

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

    can you explain n = 36 please

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

      For n = 36 : 2,3,4,6,9,12,18 36 = 2*2*3*3 so ashish will div it by 9 Now 36/9 =4 now fastest finger can only sub 1 from it Then it becomes 3 as 3 is odd ashish will win

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

      Ashish divides by 9 N=4 fastest finger does -1 no other option Now n becomes 3 Ashish divides by 3 and wins.

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

      36. Ashishgup divides by 9 . n = 4 FastestFinger needs to subtract 1 . n = 3 Ashishgup divides by 3 . n = 1 FastestFinger cant do nothing Ashishgup Wins

      Any case where n = (2^k)*(Non-prime-Odd), k!=1 Ashish can divide by that (Non-prime-Odd) Now Fastest is stuck with 2^k, which obviously has no odd multiples, hence forced to subtract Ashish gets 2^k -1 which is always odd and divides it by itself Ashish passes 1 to Fastest and wins.

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

      Thank you very much. I understand

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

    Here is a detailed Video Solution

»
4 months ago, # |
  Vote: I like it +26 Vote: I do not like it

Did anyone else use DSU to solve problem D?

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

    Yep, although binary search would probably have been cleaner and faster to implement.

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

    Please can you explain general idea for your dsu submission

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

      Yes, I can try.

      Thought Process: We need to fill either the odd or even places with as small elements as possible, to minimise the maximum. Basically, we need k/2 (or k/2+1 for odd positions and odd k) elements which are as small as possible and no two are adjacent.

      To do this, we need to sort the elements while maintaining their previous indices.

      Now, starting from the smallest, we perform the following:

      • Mark its position (original index) as visited
      • If either of the (original) neighbours have been visited, we merge the current position with them using DSU.
      • We calculate the maximum number of elements we are able to take. If it is <k/2 we continue, if it is = k/2 we need to check for few corner cases here whether to continue for one more iteration or to break right now.

      The last visited number is the answer.

      Now, how do we calculate number of elements we are able to take:

      • Maintain a variable to store how many we can take currently.
      • While making a new set, add 1 to it
      • Note that from each set we may take (x+1)/2 elements maximum.
      • While merging two sets, of sizes a and b, subtract their previous contributions from total, and add the contribution of the new merged set.

      There are a few corner cases to handle too here:

      • If k is odd and we can take k/2 elements currently, we must ensure that it contains neither the first, nor the last element.
      • If k is even and we can take k/2 elements currently, we must ensure that it does not contain both the first and the last element.
      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        how to make sure u don't take both the first and last element when k is even and what happens when two numbers are equal whose index will u add to dsu

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

          We note that we are forced to take the first (or last) element if and only if:

          1. It has been visited
          2. The size of its set is odd
          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            I didn't thought about that answer is last picked number, and without it I had much more cases to consider, because I was calculating answer. So It was too hard to me to check all cases. And here is my workaround.

            • if subsequence length k is even, I solve twice. 1) for all numbers except last. 2) for all numbers except first. And awaiting size of k/2
            • if subsequence length k is odd, I also solve twice. 1) for all number. awaiting size of (k+1)/2 2) for all numbers except both ends. awaiting size of (k-1)/2.

            For odd size two cases are correspondingly: minimum of maximum is on odd positions, and minimum of maximum is on even positions. Solve is to wait until we can fit required (k/2 or (k+1)/2/...) numbers.

            My code can be easy modified to output subsequence because of this trick. :)

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

              I am doing a similar thing by solving for k, and checking if x (lower bound) is coming from odd and even positions.

              But my solution doesn't pass. It would be helpful if you could tell what is wrong, as our approaches are similar (in terms of splitting into odd even). Please have a look at this 84506317

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

                No, your approach is more close to editorial. But with bug. You only checking values that <= x, which is wrong. You need to construct subsequences fairly, honestly, without "number of good elements is enough so it should work". At this moment you may pick first element in both cases.

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

                  (I think my code is not so clear) Let's say I am checking if the values <=x are occupying even positions. Then I require floor(k/2) values such that no two are consecutive (so that there is at least one value for each odd index between them ). Also I make sure that an even index does not consider the first value or the last one (last in case when k is odd). In this way I am not just looking for a good enough frequency, but a set which allows me to select values for the other (odd/even) indices also. This makes me feel that the above is not the bug.

                  If possible provide a test case to tell where something is getting added unnecessarily.

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

                  That makes the bug really clear. Thank you so much. Now it makes perfect sense to construct the subsequence honestly.

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

          All the elements (in increasing order of value) only increase the number of numbers we can take. (which is also why the binary search solution works)

          In case of equal numbers, the answer wont change because of the order of taking them because if that number were to be the answer, the last taken occurrence can always lead to the satisfaction of the conditions, even if the occurrences before the last one won't.

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

    I used DSU too (and the same approach) but could not find a bug in my code. Ended up thinking DSU approach would never work. Thanks for the proof by AC :P

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

    I too came up with a DSU-based solution to the problem "1370D. Odd-Even Subsequence". If anyone is looking for such implementation kindly have a look.

    84624201

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

Please help me out with Problem C[problem:1370C]

https://codeforces.com/contest/1370/submission/84502948

all possible cases which I thought were given right by my code.

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

Problem C can also be solved by calculating the Grundy number for the given n. It took only 31ms. 84482491

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

    Can you explain the intuition behind using grundy number?

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

      The Grundy number of a game state is equivalent to the pile size if we think of the state as a single Nim pile. Now, if there is only one Nim pile and it has some stones, first player can just take all the stones. So, in this case if the Grundy number is non-zero, first player wins.

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

In problem E, why are we not treating the strings as circular? or is it the case that not treating it circular will not change the answer.?

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

    Circular won't change the answer.

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

    I don't think it matters if the string is circular or not. My solution was to assign a +1 and -1 to a 01 and 10 respectively and find the maximum and minimum balance(Similar to a parenthesis sequence) and subtract them from each other. A rotation of both strings by an equal amount won't affect the results.

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

      Your solution would have very simple implementation. Could you please elaborate on how you noticed the similarity to the parenthesis sequence and how it works? why the answer is the difference of those values?

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

        Basically in one move I noticed that you could any neighbouring opposite parenthesis and make them vanish. So you could do this for all neighbouring parenthesis in the same orientation. And I also noticed that you could reduce an uphill sequence in the number of steps equal to the max balance same for the downhill sequence. So basically it narrows down to find max of max balance of all uphill sequences and min of min balance of all downhill sequences.

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

          What is this uphill and downhill sequence? Also there is some word missing in the 1st sentence of your reply.. Thanks in advance

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

      Sir, I am very interested in your approach. Can you be a bit more elaborate about how you did this?

»
4 months ago, # |
  Vote: I like it +31 Vote: I do not like it

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

Thanks for the quick editorial :)

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

Am I the only one who failed to observe the pattern and brute forced problem C with a recursive solution?

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

A pure win/lose recursive solution for C is accepted.

https://codeforces.com/contest/1370/submission/84516783

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

How is rating change calculated any ideas?

»
4 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Why does $$$binary$$$ $$$search$$$ work in D??

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

    Because why it shouldn't ? If we apply binary search on answer , Left = minimum element and Right = maximum element of array. And lets find mid. If we can make a sequence such that at odd indices all the elements are less than mid we can say answer will always be <= mid (Don't care what values are at even position). But there is case possible say k=5 and mid = 5 and the sequence till k-1 that we formed looks like 4 2 5 1 _ and the next elements in original array are greater than 5 (mid). Hence if we're just checking if we can form a sequence where all odd indices are supposed to have elements less than mid, in this case answer doesn't exist but check at even position we have 2, 1 and if we putt any value at last index answer will still be <=mid (in this case 2) . Hence we just have to check if for any mid we can form a sequence where either odd elements are less than mid or even elements are less than mid.

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

    To prove that binary search works, we need to prove that the thing we do binary search over, is monotonic. Sorry if my sentence is incorrect. I'm not native english speaker. For example, if "We do binary search over an array", then the thing is "an array", so we need to prove that the array is monotonic. Proving something is monotonic in straight way is hard. So basic approach is to prove by contradiction. Assume that it is not monotonic then get contradiction.

    What is the thing we do binary search over? (sorry again if it's wrong sentence) We do binary search over "can we make subsequence with cost not exceeding x?" As I said, we will prove it by contradiction. What means that the thing "can we make subsequence with cost not exceeding x?" is monotonic? For each x its value is either "yes" or "no", so monotonic means that it's either: all "no" for each x from zero up to some point then "yes" for each other x, or all "yes" for each x from zero up to some point then "no" up to the end. To prove easily, we pick which one we prove.

    Now proof: Assume that it's non monotonic in the way "no", "yes". Then, to find out how can it be non monotonic, is to take definition of monotonic sequence and make negation. Monotonic means that first all "no", then all "yes". Negation of this statement is that after some x with answer "yes" there is some x' with answer "no". Word "after" means x < x'. But answer "yes" for x means that we can make subsequence with cost not exceeding x, thus it also not exceed x'. Thus answer for x' should be also "yes". Contradiction. Proved.

    Now, to understand it under binary search view, we actually prove that if we pick some x in between and answer is "no", then for all x below it answer is also "no", so we don't need to check them. Contrary, if there would be some "yes" then this yes would be x in assumption, and "no" that we checked by binary search is x'. But we proved that for those x and x' it's impossible. I hope it's all clear now.

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

Hello, when I registered for the round my rating was 2102 so I got registered as out of competition but in previous global round I became a candidate master (2088 rating). But cf still shows that I'm out of competition for this round. Can someone tell me if this round will be unrated for me? Thanks in advance!

Upd: Rating has been changed :)

»
4 months ago, # |
  Vote: I like it +14 Vote: I do not like it

My solution for F is quite different from the one mentioned in the Editorial. Here it is:

By asking a query over all nodes, find $$$x$$$ and $$$d$$$. Let $$$s = f = x$$$ and $$$target = d$$$. Notice that, $$$target$$$ is the distance between the hidden nodes.

Now, while $$$dist(s, f) < target$$$, let $$$p = \lceil\frac{target-dist(s, f)}{2}\rceil$$$. Let, $$$l_s$$$ be the list of nodes which are at distance $$$p$$$ from $$$s$$$ and they are reachable from $$$s$$$ without using any nodes on the path between current $$$s$$$ and $$$f$$$ (exclusive). Define $$$l_f$$$ in a similar way. Now, we can guarantee that, at least one node $$$x$$$ exists from the union of $$$l_s$$$ and $$$l_f$$$, which is on the path between hidden $$$s$$$ and $$$f$$$. We can find that $$$x$$$ by asking a query over the union of $$$l_s$$$ and $$$l_f$$$. Then, if $$$x$$$ is an element of $$$l_s$$$, replace $$$s$$$ with $$$x$$$. Otherwise ($$$x$$$ is guaranteed to be an element of $$$l_f$$$), replace $$$f$$$ with $$$x$$$.

In each turn of the loop, the distance of $$$s$$$ and $$$f$$$ increases by $$$p$$$. Also, at the end of each loop, current $$$s$$$ and $$$f$$$ lies on the path between hidden $$$s$$$ and $$$f$$$. In the end, $$$s$$$ and $$$f$$$ will achieve the hidden values. Notice that, the distances we find after first query are useless in this solution!

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

    I came up with the same solution (but failed to implement it in the given time, rip, code in case anyone wanted). The nice thing about this solution is that it takes atmost $$$10$$$ queries without having to resort to handling the kinda annoying edge cases which the editorial solution requires.

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

Can Anyone please help me understand why my these submissions to B give RTE

84447747

84439096

These are failing on test case : 3 1 3 5 7 9 11

While solution with while loop(84447747) passes on local, but I want to know even in for loop case if second(i<v[0].size()-1) condition fails why code goes inside this loop. Am I missing something basic here.

Would be great if anyone can help, Thanks in Advance!

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

    v[0].size() is unsigned. If size is 0 and you subtract 1 from it you get a very large positive number.

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

can you do DP for question D? I tried and got nowhere

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

    I don't think that DP would help here as any information stored with the state information as the length of some prefix should be sufficient only when there is some information on the length of subsequence actually considered.

    Thus at least 2 dimensions — length of prefix and length of the subsequence are required at least. This would demand a lot of space.

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

Can somebody tell me what was your thought process during solving Problem D? How did you get to the solution?

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

    In my case , during the whole contest i was thinking about greedy or dp solution. Later i saw in the editorial the word binary search, closed the editorial, thought for a while and got the solution.

    I think remembering to try to use greddy, dp or binary search for minimization/maximisation problems will help.

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

FastestFinger In A, why there wasn't this test case 100 1000000 1000000 . . .

My solution would have failed, right?

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

Is anyone else able to explain question D? I have read the editorial many times now and honestly I wouldnt given guess it was the answer to the same question I was doing. Thanks

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

Hi everyone, i really need help!!! Can anyone just tell me ,why am i facing RUNTIME ERROR on the 2nd question https://codeforces.com/contest/1370/submission/84517421

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

    You are getting an overflow i think for cases where s1.size()==0 or s2.size()==0 so in your for loops s1.size()-1 will actually become 2^63-1 which is quite large and since size of s1 is 0 it would give a runtime error. To view this on line 21 try to print s1.size()-1

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

      Thank you very much!!! I got what you are saying and will keep this in mind in future contest.

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

    Hey,

    I also faced same problem turns out s1.size() is unsigned so subtracting 1 gives some big number(2^63-1) so you are entering in for loop.

    here is edited version of your solution which would work soln

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

Can somebody please explain how to solve E? Not the key idea, it is very easy, but why finding the maximum sum subarray of that array will work for E, because I cannot understand it from the editorial.

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

    You can read Kadane's Algorithm to find the maximum sum subarray.It's a very standard problem. Here, it's the maximum absolute subarray sum so you can first find maximum positive subarray sum, then replace -1s with 1s and vice versa and then again find maximum positive subarray sum and take max of the two.

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

      Thanks. I understand how to find the maximum sum subarray, but I don't understand how this relates to this task and why it will work. I'm sorry^ I have written my thoughts in first comment in the not right way, so it must be: "Why find the maximum sum subarray of that array will work for E?".

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

        I think the much simpler solution is the one with two sets of posittions. One set contains the 0s in s which are 1s in t, and the other set the 1s of s which are 0s in t.

        With these sets we can more or less simply construct a list of indexes of positions of alternating symbols in s. In each step construct the longest possible list and remove all those elements from the two sets.

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

          I tried to do something like this but without sets and it was giving TLE. How I can construct the longest possible list if I have indexes in sets?

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

            Start with the smallest number of both sets, then take the next higher number from the other set, alternating. Since both sets are always of same size this works fairly simple.

            Example 84498652

            This one is more clean 84488036

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

      Wouldn't the maximum absolute value of the sum of any subarray in a be reduced to maximum length subarray having only 1 or only -1 .

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

    I solved E task by simply making brackets sequence from 1 and 0 and finding it's depth.

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

      That is clever, because it is super simple code.

      But... how did you come up with the idea?

      I stopped thinking and started implementing when I saw a solution with sets of indexes, and simulating the shift process. Which is obviously more work.

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

        I came up with idea in following way. I did write some bunch of zeros and ones for two strings with equal amount of ones. Then I tried to shift few subsequence, and got idea that picking already matching positions is silly, because we can pick any subsequence. So, then, I threw off my test, and wrote new that doesn't match in each place. I wrote new two strings, and tried to move it as a whole. My hypothesis was that they match. So I tried to beat this hypothesis. Question was to find test where strings doesn't match. It was hard to make a good one, so here what I got:

        10
        1011000110
        0100111001
        

        I still have it because I was testing on it my solution. BTW: always save tests you make, with answers. It will help test a lot. So... When I had this test, I realized, that when I shift it as a whole, some ones are matching and vanish. For a moment I thoughts would it give better result if I shift subsequence? I had feeling that it would not. So I thought about following approach: move all once and remove matching. Repeat until all match. Then, I tried to write simulation using sets, I even wrote most of it, but it had issue. I stucked when I had to find those which will match on next step. And when I was thinking about it, they were matching like a brackets. Also, it's like you bought something and now you can sell it. Which is also like a brackets. So I started to think about brackets. First version that I wrote was calculating place where you can start to make correct brackets sequence, and then summing depths of each closing brackets. When I tested it on samples and on my own test above, result was too high. So I revisit why I am thinking about depth summation, and come up with idea that it's just maximum depth.

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

          Thanks!

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

            Oh! At first look I thought this is same: https://codeforces.com/blog/entry/79107?#comment-646441

            So I didn't dig into details. But now I see it's much more complicated! Here is my algo in all details.

            My algo in all details
            • »
              »
              »
              »
              »
              »
              »
              4 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I got a visualization like this, consider string of positions in s[] which differ to the ones in t[]: "10111000"

              1: 101    0
              2:    1  0
              3:     10
              

              The first line are the elements we can change with first operation, second with second etc...

              So it is obvious that we need to depth of the bracket sequence. And shifting the sequence is trivial, we just have to consider max(depth)-min(depth).

»
4 months ago, # |
  Vote: I like it -24 Vote: I do not like it

C was harder than D. Other than that, nice contest!

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

I am unable to find any fault in my code but my code is showing runtime error on test case 2 for problem B. Please help me to get out of this.
Link to my submission is https://codeforces.com/contest/1370/submission/84475986. Thanks in advance for reply :)

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

    Hi I am also facing the same problem https://codeforces.com/contest/1370/submission/84517421

    all that i can conclude that it is because of i<v.size()-1 in the for loop

    but i cant understand the reason.

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

    Did you check the case when the size of your vector is zero?

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

      Yes,Got the mistake

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

      Yes, in that case, program counter does not goes to that loop as i=0 is not less than v.size()-1 as 0>-1

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

        nope v.size() returns unsigned intger , so when the vector is empty it returns 0 and since it is unsinged subrtacting one from it does not make it -1 but makes it 18446744073709551615 . So to avoid this typecast it to signed int first then subtract -1 .

        (int)v.size()-1;
        
»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

For D, I did the same thing — binary search on x. However, I checked separately for odd and even indices, i.e, the maximum number of valid odd places satisfying <=x condition. Similarly for even indices. The count should be >= ceil(k/2) for odd and >= floor(k/2) for even (when assuming that to provide the answer).

I am unable to understand why my submission: 84506317 fails on test-22. It would be helpful if someone could give a smaller input which fails and/or tell me what mistake I have committed.

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

    why the ceil and floor @two-wrist?

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

      If length is k is odd then there will be one more odd index than the number of even indices.

      Ex: if k=5 , 3 odd and 2 even indices

      1(odd) 2(even) 3(odd) 4(even) 5(odd)

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

My nlognlogn solution for D passed the pretests but not the system tests. First I sorted all the numbers in an array in ascending order by value. Then I used binary search to get the minimum length prefix of the sorted array which could alone form either the even or the odd indices (when checking whether is it possible I sorted the array in ascending order by index, thus nlognlogn).

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

Can anyone explain n = 36 for problem c. How "Ashishgup" wins this game.

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

    36/9 =4 4-1 =3 3/3 =1 So fastest finger has 1. Hence winner is ashish.

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

    Ashishgup divides by 9 giving 4 to the other player. Other player can only return 3. Ashishgup can then divide by 3 to give 1 to the other player and win.

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

    So 36 = 4 * 9. In his first move Ashishgup divides 36 by 9, so now number is 4. 4 = 2 * 2. Because 4 do not have odd divisors, another player must decrement it, so now number is 3. Than Ashishgup divides 3 by 3 and now number is 1. Now Ashishgup wins because another player cannot do a move.

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

    Thank you very much all. I understood

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    1. Ashishgup divides by 9. N = 4
    2. FastestFinger is forced to subtract 1. N = 3
    3. Ashishgup divides by 3. N = 1
    4. because N = 1, FastestFinger loses -> Ashishgup wins
»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Many people have done something like +1 for 1-0 and -1 for 0-1 in the problem E.

Can someone explain it? Didn't quite understand the editorial.

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

https://codeforces.com/contest/1370/submission/84475609 why is my answer wrong on pretest 2??

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

    Consider 1 3 5 7 9 11 your ans is printing 1 2 3 4 5 6 when is not supposed to print last pair. Prob need to check how many pairs are being printed.

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

    your code printed 14 lines instead of 12 lines

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

Hi, can anyone tell me what is wrong with my approach for E? Instead of finding the min num of 1010s, I tried to find the longest consecutive 1111's that were not alr in correct position. Its failing on pre-test 10 and I'm not too sure why. A counter example would be nice. Thank you in advance! 84521497

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

How does number of queries get reduced by 1 after setting lower bound of binary search to ceil(l/2) ??

Consider a tree where there is an edge between ith and (i-1)th node for all i>=2.
And the two hidden nodes are 1 and 2. l in this case l would be 1. The max depth of a node would be 999. So earlier (when lower bound of binary search was 0), we would have searched in [0,999]. Now after changing that we will search in [1,999]. So this would also take 10 queries and hence 12 in total.

What am I missing here??

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

    You can also set upper bound to l. In any case I think my solution is more elegant/easier to understand

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

      Thanks, figured that out. Just got AC. btw link you mentioned is of editorial. I had a look at your solution though, your code is really elegant. It's niceee.

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

        It is a link to another comment of mine in this page, which explains my solution, for some reason today I decided to use rust, since it won't be rated for me anyway, so code ended up being somewhat long...

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

I have a question about C — Number Game: What if n is 18, shouldn't FastestFinger win? Here is my reasoning:

Ashishgup — 18 / 9 = 2 FastestFinger — 2 — 1 = 1 Ashishgup — 1

Since Ashishgup has 1, FastFinger should win. Is there something I am doing wrong since my answer WA on test case 2 when n = 18

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

    A — 18/3 = 6 F — 6 — 1 = Lose OR 6 / 3 = 2 == Lose

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

    Ashishgup will play optimally so he will divide by 3 and not 9

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

    Ashish — 18/3 = 6
    Fastest — 6/3 = 2
    Ashish — 2-1 = 1
    Fastest — ....

    Ashish wins

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

    Ashishgup wont be doing 18/9=2 in the first place, since it is not optimal(meaning he wont be able to win this way). The optimal move for Ashishgup will be 18/3=6

    So, Ashishgup--18/3=6 FastestFingers-- Either 6-1=5 or 6/3=2 Both ways Ashishgup will win.

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

    AshishGup being one of the smartest(True Story) will divide by 3 in the first move making n=6 now if FastestFinger makes it 5 Ashish divides by 5 and wins otherwise is FastestFinger makes it 3 Ashish divides by 3 and wins.

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

    AshishGup --> 18/3=6
    FastestFinger--> 6/3=2
    AshishGup --> 2-1=1

    AshishGup Wins !! Hope this helps.

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

    marshu Check this for a detailed explanation

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

Someone please help me with the tutorial for D.

I cannot get what does binary search over the "answer" mean in the key idea of the tutorial?

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

The Round was Amazing with pretty good problems

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

    Praising just to get likes on your comment ? LOL.

    Everyone knows the round was good :)

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

Hey guys, I need help on problem D. The approach I found seems correct, but it fails on TC 10.

Here it goes: Let's say the optimal answer is x. Obviously, x should be equal to an element in our array. Otherwise, assuming we found an optimal answer, we could decrease it until it reaches $$$min(max(s_1,s_3,s_5,…),max(s_2,s_4,s_6,…))$$$ (our answer). Let's now say that $$$x = a_l$$$.

We can try to binary search $$$l$$$ in the following way: Say in our current step we are at $$$mid$$$. We sort the array in ascending order and we mark the first $$$mid$$$ elements (using true/false values). Then, we apply this marking to the initial arrangement. Now, we will try to create a desirable sequence and try to fit as many marked elements as possible at either odd or even indices (I will call them from now on subsequences). Say we can squeeze them in the even indices. Then, we get $$$min(max(s_1,s_3,s_5,…),max(s_2,s_4,s_6,…)) = max(s2,s4,s6,...) <= a_{mid}$$$, as $$$a_{mid}$$$ is marked as well. Hence, we get a valid sequence (and we can decrease $$$mid$$$ in our binary search).

One way to see if we have an answer is to get the maximum marked elements we can get in odd or even indices. If we have two adjacent marked elements, we can only use one of them in our subsequence, because if both of them are included in the even one, then we can't have any element in the odd index between them). So, we can use dynamic programming in the following way:

$$$DP_i$$$ denotes the max number of marked elements that there exist in even or odd indices in the first $$$i$$$ elements of our sequence. Here is our recurrence relationship: $$$DP_{i + 1} = max(DP_i, DP_{i - 2} + 1, if i is marked)$$$. That means, we can either ignore our current element and get the answer from the previous one or (if it's marked) we can include it, but we can't use the previous element, hence the $$$DP_{i - 2}$$$ term.

The maximum subsequence we can form will be equal to $$$DP_n$$$. If it's bigger than the desired length of the subsequence (more about it in a moment), then we can return true on the binary search predicate. But there is one more technicality we need to resolve. What should we do with $$$k$$$? Let's have a look.

*If $$$k$$$ is even, then it doesn't matter whether we are trying to fill an even or an odd subsequence, as they should have the same size. Therefore, we can try and find the min $$$l$$$ such as we squeeze exactly $$$k / 2$$$ elements in an either odd or even subsequence.

*However, if $$$k$$$ is odd, then the even subsequence will be one less. So, we have 2 cases: *if the first element in the array is not marked, then we include it in our odd subsequence and solve the problem on the interval $$$(2...n)$$$ with $$$(k - 1) / 2$$$. *if on the other hand it's marked, then it's best to include it on the odd subsequence. Then, we see that our problem is reduced to the above one (ie. interval $$$(2...n)$$$ with $$$(k - 1) / 2$$$).

Here is my submission: https://codeforces.com/contest/1370/submission/84494240

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

    You might run out of positions for other parity. Try this case

    5 4

    1 2 3 4 1

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

      Thanks for your prompt response! :)

      I did not even think about this!

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

Someone please help me with the tutorial for E.

I don't understand because may be the code was not follow the tutorial

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

Really nice problem sets!! I really got to learn new things from this contest! THANK YOU!

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

Quick Editorials is perhaps the best thing I like :)

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

Any particular reason for declaring all arrays a[N] global?

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

However, we can solve C with DP.

Suppose that dp[n] = 1, is First player wins if we start with n, 2 if second wins.

Then dp[1] = 2, dp[2] = 1. For all odd N, dp[N] = 1. If n mod 2 = 0 and n > 2, we cant subtract 1 from n(because n becomes odd and second player wins).

So we can only divide N. lets find all odd divisors of N greater then 1.

Suppose we find divisor f which is odd. When if dp[n / f] = 2, it means that dp[n] = 1.

Dont forget to save dp states in recursion! Code: https://codeforces.com/contest/1370/submission/84458094.

»
4 months ago, # |
  Vote: I like it +20 Vote: I do not like it

In problem E , can someone prove that why is it never optimal to include any indices $$$i$$$ such that $$$s_i = t_i $$$ ? I couldn't prove this by myself.

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

    I don't know how to prove it. But there always exist a way to get minimum number of operations by ignoring the place $$$s_i=t_i$$$.(The way is mention in tutorial).So we can ignore the $$$s_i=t_i$$$ place.

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

    Taking those indices would always require atleast 2 cyclic shifts in some cases where not taking them does in lesser steps. Also, we don't even need more than one cyclic shift in any optimal answer for each subsequence as we could split string s into many subsequences. This proves that taking indices of equal parity will only increase the number of steps.

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

    In editorial there is no proof. Ashishgup It's bad habit I think to not include proof but place some substitution instead. It it relies on very non-intuitive thing that $$$s_i = t_i$$$ can be ignored. I don't know how to prove it. Ashishgup if you have original proof though, I would like to see it, because here is what I got, and it's complicated enough. I added some redundant explanations just to make it rigorous. Short version could be made, but it is proof not substitution.

    There are some moments in editorial that I would call mistakes. First, is that subsequences must be of the form 0101. And part with "assume $$$c \geq 0$$$ (otherwise we can interchange 1 and -1)".

    Instead of proving that $$$s_i = t_i$$$ could be ignored, I'll prove that algorithm from editorial is correct, and it indeed find optimal solution. I'll use some facts and observation from editorial, but add more details, more facts and fix things I dislike. And fact that you can omit matching positions will be as a corollary of the proof.

    Alright.

    horrible wall of text
»
4 months ago, # |
  Vote: I like it -12 Vote: I do not like it

just like your problems.....the meme was also too good XD:

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

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

    same happened with me.... becauses of which i was only able to do problem A :( but after it i learnt a new thing and never going to do this mistake again

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

    stop making unnecessary memes

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

n&(n-1)==0 for finding power of 2 was an excellent implementation. I thought that I have to write many statements for doing this. Thanks FastestFinger and all other authors.

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

    Yes, that's what we usually do. You should even check some more one liners about BIT manipulation. You'll surely enjoy those.

»
4 months ago, # |
  Vote: I like it +53 Vote: I do not like it

CaseForces :)

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

Hi, please tell me why I am getting runtime error in it. https://codeforces.com/contest/1370/submission/84441745

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

can someone plz explain editorial solution of E

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

This was kind of Mathsforces.. But liked the simplicity of problem statements and toughness of implementing them..

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

Why I am getting RTE on this 84528459 submission on problem E? Upd: I get it

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

A was so easy I actually read the question again since it was Ashishgup.

»
4 months ago, # |