When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

TheOneYouWant's blog

By TheOneYouWant, history, 4 years ago, In English

Hello, everyone! It was a delight for us to have you participate in our contest. We hope you enjoyed the problems! Here, we present to you the solutions of the problems. I have also prepared some memes for you to enjoy — disclaimer: not all of them were created by me.

Tutorial is loading...

Author of this problem was Ashishgup.

Relevant Meme
Code for A
Tutorial is loading...

Author of this problem was Ashishgup.

Relevant Meme
Code for B
Tutorial is loading...

Author of this problem was TheOneYouWant.

Relevant Meme
Code for C
Tutorial is loading...

Author of this problem was FastestFinger.

Relevant Meme
Code for D
Tutorial is loading...

Author of this problem was Ashishgup.

Relevant Meme
Code for E
Tutorial is loading...

Author of this problem was FastestFinger.

Relevant Meme
Code for F
  • Vote: I like it
  • +854
  • Vote: I do not like it

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

Auto comment: topic has been updated by TheOneYouWant (previous revision, new revision, compare).

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

like D

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

    I have another idea: because $$$ 1000 <2 ^ {10} $$$, we can perform the $$$ log_2 {k} $$$ query, and the $$$ i $$$ query the union of the sets which binary expression of the set number's $$$i-th$$$ bit equals to $$$1$$$ in the $$$ i $$$ th query. This can also find the position of the maximum value :-)

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

      Doesn't it take $$$2\lceil\log_2k\rceil$$$ queries?I think you may need to query twice for each bit?

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

        What you said is my initial idea, but it is not really necessary. In fact, this algorithm can pass this question! Maybe it’s because I’m a foreigner, and the English expressions I use are not good enough. You can look at my code and try to understand my method. https://codeforces.com/contest/1363/submission/82139983

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

          Now I think I've understood it.Thank you so much.And,orz :-)

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

      What if there are multiple positions with maximum value? Consider: N = 5 and Arr = {10, 10, 10, 10, 10} For bit position 0 (index = 0, 2, 4): Max = 10 For bit position 1 (index = 1, 3): Max = 10 For bit position 2 (index = 4): Max = 10 According to the queries, the index with max value is (111) in binary representation which is 7 and it is out of bound. Correct me if I am wrong.

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

        In fact, the maximum value does exceed the range, but this does not affect the correctness of the algorithm! I did not directly access the position of the maximum value, I just made a judgment on the index of 1~n to determine whether it is equal to the position of the maximum value. You can look at my code and try to understand my method. Sorry for my poor English. https://codeforces.com/contest/1363/submission/82139983

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

    1 8 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8

    For this test case in C question, the answer should be Ashish but according to the editorial it is Ayush. Please correct me if I am making a mistake. Thanks in advance

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

      no it is Ayush.Ayush will start removing leaf node and Ashish will be the last person to remove third last leaf node after that only two leaf nodes(x and some node v) remain from which Ayush can remove x and he wins.

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

      Actually Ayush is true, you can see that we will remove node 4,5,6,7,8 in sequence and then it is just like pretest 1, but this time it is Ashish's turn not Ayush's.

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

    That really wonders me how you think in that much easier way.

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

    you're doing a nice job.

    but what about "video tutorial for D" for the next contest? ;)

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

Never imagined C could be easier than A.

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

    :(

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

    Never imagined B and C could both be easier than A.

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

      True bro, I wasted a lot of time in A(almost 45 minutes) rather than going for B or C but still anyhow managed to solve all of the three problems 3 minutes before the contest ended.

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

        what's the logic behind your B submission??

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

          exactly same as the editorialist's concept but if you have seen my code, I used a minimalFilps function directly from geeksforgeeks to get the count of minimum number of flips required to convert the array such that all 1's appear on left side and all 0's appear on right side. Here is the link to that function. Feel free to ask me if anything regarding my approach is not clear to you. Thanks for your time to have a look on my solution.

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

      sushant23y what's the logic behind your B submission??

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

        for every index calculate the cost of making every bit to left of this index to 1 and to right of this to 0. Take the min of these.

        Then do the same again but for every index calculate the cost of making every bit to left of this index to 0 and to right of this to 1. Take the min of these.

        Check this answer https://codeforces.com/contest/1363/submission/82186217

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

Nice problemset, like it. But shitty D statement has spoiled an impression a bit :(

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

fast editorial

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

FastestFinger ==> FastestEditorial

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

    Agreed, fast editorials, good problems, nice memes, strong pretests. (At least for me lol) Great contest!

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

I am having trouble deciding what sucks more — this contest or your sense of humor.

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

Relevant Meme for Problem D is too close to heart <3

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

i'm in love with those pictures too :ddd

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

Adding memes to editorial is becoming a trend

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

Missed n==1 case for C. FML -_-

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

Thanks for such a good contest !

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

How is N^2 passing in B, even Reds have written N^2 to solve fast. How they knew it's gonna pass.

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

    by looking at the constraints

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

    Because scanning memory byte-by-byte is extremely fast. Reds write brute forces if they pass because it takes less time to write.

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

this was a nice contest and editorial is also very much fast.

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

Problemset was nice.

Here is a simpler solution for Problem A :

let k denote the number odd values in the array.

Answer is "no" if one of the following satisfies :

1) k = 0

2) k = n and x is even

3) x = n and k is even

Why ? (Left to reader)

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

    I had actually done the same

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

    i have done the same .....and solution is accepted.... but question says that element should not be consecutive ... and in the solution we have not consider this

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

      Question says that elements don't necessarily need to be consecutive but they can be consecutive.

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

The C meme is hilarious

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

How to solve E when digits aren't necessarily binary?

I accidentally tried to solve this harder variant during the contest because I didn't read that digits are binary (oops...)

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

In problem B, I think simple O(n^2) should pass as length of string is less than 1000. But gave TLE on simple approach. Correct me if I am going wrong.

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

    My O(n^2) solution passed easily.

    Here is my Solution

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

    Numbers of Test cases were 100 ! It would be 10^8 in total ! My Solution failed for O(N*N) approach then I opted for using a prefix sum array !

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

      Thanks for clarification. I wasted my attempt due to this even after knowing the efficient method :(

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

      This might be the silliest of my doubts...But I've read in comments people saying for O(N*N) it would be 10^8. How come it should be 10^8 when |s|<=1000 and |t|<=100...so in the worst case it should be (1000*100)^2 = 10^10. Please tell me what I'm thinking wrong?

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

        For EACH test case, O(1000*1000). There are 100 testcases = 100 times O(1000*1000) = O(10^8)

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

        O(N*N) for solving each test case.
        T*N*N in the worst case, therefore, 10^8.

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

          Got it thanks!!, and one more doubt pls...what is the expected upper bound on number of operations that can be successfully executed in 1 sec without TLE. Until today I thought it was 10^7.

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

            The upper bound is indeed 10 ^7 to 10^8 operations under 1 second to my knowledge! Correct me if am wrong !

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

            The upper bound is close to 10^9 operations in a second with fast I/O. You can verify by running a for loop of 10^9 operations in custom invocation. But if you have multiple operations in the for loop, I would suggest not running a loop of more than 2*10^8.

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

Can someone please explain A's solution? Why does it work? I don't get it.

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

    Umm I will attempt to explain ! For choosing out K elements who sum up to give an Odd Number ! So it is prerequisite that We calculate in handy about how many odd and even integers are there in this array , now if no odd number exists it is clear that sum will never be able to get odd ! Another case is when You Have K as odd and CountOfOdd greater than equal to K you can fit these odd numbers in K and get a result , (For eg if you take 1 3 and 5 and sum up it gives 9 so it should be remembered that Taking ODD count of Odd Numbers and summing up gives and Odd Number , Another case will be when You have Not sufficient odd numbers to complete you K in that scenario you can take 1,3,5.. of the odd numbers you have in your count and can opt for taking other even numbers ,There is a catch for N==K case ! it is explained well in Editorial I think

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

question 1 9 7 11 14 1 6 3 12 3 20 16 how this is YES

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

    11 14 1 6 3 12 20 you can see sum is odd

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

    take 11 14 1 6 3 12 20, the sum will be odd

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

    You can take 11 14 1 6 3 20 16 which has odd sum 71

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

System tests to problem D might be weak, I hacked my own submission 82140938.

Feel lucky tonight :P.

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

    Read this : comment by mike

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

      piyush33patel, thanks for the infomation. I submitted to problem D only 2 minutes before the end. When waiting for pretest, I checked my code and found a bug. I thought it would certainly fail system test since it is easy to construct a test against that bug. It is ok for me if the rating change is not final.

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

        Uphacking doesn't affect standings, so you will keep your rating.

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

Please, for the love of god, someone tell me what is wrong with the following answer to E: https://codeforces.com/contest/1363/submission/82145487 I really hope something is wrong so I won't feel I was python-robbed again.

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

    You likely hit stack overflow. It's a shame an equivalent C++ solution passes just fine.

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

    For Python you might be able to set a new stack limit. I'm not too sure if CodeForces allows this but you could do:

    import sys
    sys.setrecursionlimit(10**7)
    

    This may give an error but it's worth trying. (On a side note, a Java solution with dfs also works fine)

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

    I did similar thing using JAVA and I am simply applying DFS here, https://codeforces.com/contest/1363/submission/82320024 , but its showing TLE on 9th test case. IT IS SO SAD CODEFORCES.

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

      Use Fast IO if you are using JAVA, I am using JAVA for a long time and haven't faced a single issue of TLE if I use Fast IO, My solution :82417618

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

    I ended up finding one solution, and creating one solution.

    1) At first I searched for a while, and found "bootstrap recursion" that someone posted a while ago. Solution: https://codeforces.com/contest/1363/submission/82165464

    2) I implemented an iterative dfs. That was challenging, because you need to deal with the return values for the "recursive" calls, and also maintain local variables. Unlike a simple dfs, you can't just push all your neighbors onto a stack, but you have to push one, finish with it, somehow get a return value, and then push the next. I kept a counter that shows how many of the node's children visited the node, and when the counter reached len(neighbors), I filled the return variable, and popped it from stack. Maybe it's trivial and this solution is simple, but I looked a while for solutions for this and did not find even one (only a reference to a pdf that didn't work, about this matter). Solution: https://codeforces.com/contest/1363/submission/82215100

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

That's sad when your 100 lined code was actually checking n%2

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

Who wants to help me with D? https://codeforces.com/contest/1363/submission/82145477 Looks like I'm writing or reading incorrectly (wrong answer Token "162" doesn't correspond to pattern "!|?" error) but I don't see the mistake.

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

    It seems that when asking for the maximum of all indices not in the same subset as the index with the maximum value, you assume the input set was ordered, then use z to iterate through the indices to ignore. If the set containing the index which has the maximum value in the array is not ordered smallest to greatest, extra indices are printed in the query.

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

Is it just me or someone else also got deceived by the constraints of Problem C with $$$N$$$ = $$$1000$$$

I spend a lot of time doing dfs or building $$$O(N^2)$$$ solution in the end to realise that except for the degree of $$$x$$$, even all other edges are useless :P

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

If anyone wants a detailed explanation on A https://www.youtube.com/watch?v=0_b4YKuIPeU

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

Press F for everyone who failed the systest in problem D

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

The meme of D is the truest thing I've seen lately. Nice contest!

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

Interesting tutorial i've ever seen. :)

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

...

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

    I guess it meant that both of the guys wanted to remove it first(special node). To do so they will make each other to remove unwanted leaf nodes. So they will start from the farthest.

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

The problem C is very very interested.I was completely off track the solution.Feels like crying after seeing that the solution is such easy.

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

Where am I going wrong for question D:

error: Idleness limit exceeded

code logic: get maximum by querying for 1 to n ans will be maximum for all k except one slot. use binary search for finding the slot number in which maximum belongs query for found slot.

Code link:82134674

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

    Note that not all of the indices need be in a subset. In one of the last loops you print all subsets except one, but since some index might not be in a subset, it could print less indices than indicated (the first number after ?), then block waiting for input.

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

      Oh I didn't see that coming.

      I thought every index is part of exactly 1 slot.

      Thank you. It was my first interactive that I have solved on my own.

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

Anybody knows where can we find more problems like A? (Once in a while such A's tend to totally massacre the contest, if possible I would like to train on such kind of problems to save myself from such wreckage.)

There was a similar problem from Dreamoon's contest. Round#631 div 2-A

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

Does the author of problem himself selects the relevant meme, if so FastestFinger you've won this round unanimously.

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

I just want to take a moment and say POOR MEME GAME -_-

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

I didn't understand E after we reset the cost of nodes (from the start of the greedy solution). Thanks in advance if somebody explains it.

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

Video Solution Of Problem C : Solution

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

Can anyone please help me in problem D.? I have the same idea as explained in this tutorial. I'm getting, "wrong output format Expected int32, but "-4260782116" found" in test case 7. My submission: https://codeforces.com/contest/1363/submission/82151133

Update: No need . I've got my answer from previous comments. Problem was. it is not always true that given set always contains all the indices.

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

    can u please tell me my mistake in problem D,it;s giving a weird error in test case 1 itself.

    https://codeforces.com/submissions/Lord_Saga

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

      When asking for mv, you don't specify how many indices you are going to provide.

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

        Got AC . I was worried that i might not get any reply but you made my day by helping me out.

        Thanks sooo much :) <3

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

        Btw how did you put "mv" in the special box? Do you use any software?

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

          That's inline code — you can use it from the top bar of the editor (a script-like button) or by wrapping some text in `, like `mv`.

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

https://codeforces.com/contest/1363/submission/82151479 Can't get rid of Idleness limit exceeded on test 7 ... can someone help?

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

![ ]

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

this is gonna be the most upvoted editorial ever!! XDXD and maybe this cmmnt will be most downvoted ever XD (typical cf community i fkng love it)

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

1 8 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8

For this test case in C question, the answer should be Ashish but according to the editorial it is Ayush. Please correct me if I am making a mistake. Thanks in advance

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

    Posting the same qn again and again ain't gonna fetch you the answer. I hope you understand that. Be patient someone will eventually pick up your qn.lllll

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

    Remember, node $$$x$$$ can be picked up when it's degree is $$$<2$$$.

    The answer should be Ayush, indeed. Let's simulate it.

    Ayush picks $$$8$$$.

    Ashish picks $$$7$$$.

    Ayush picks $$$6$$$.

    Ashish picks $$$5$$$.

    Ayush picks $$$4$$$.

    Ashish picks $$$3$$$.

    Now, Ayush can pick either $$$1$$$ or $$$2$$$. He chooses $$$1$$$, and wins.

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

For problem d

Suppose the root node has two children is it possible to shuffle values of two children (do they both belong to the same subtree)

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

    yes it is possible and it is problem E not D

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

For this problem B, I submitted a code1 and it gave Runtime error. Here I have used long long int as the data type for all suitable variables using a 'typedef long long int ll' declaration at top

Now I just changed all the data types to 'int' by changing it to 'typedef int ll' and everything worked fine code2

In some other submission I changed the string declaration to char and again everything worked fine [code3](https://codeforces.com/contest/1363/submission/82147815)

I am not really able to understand the failure of code1. Please help me out !!!

** For this problem my friend too faced the same issue. ***

Failed code

Passed code — just changed long long int to int

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

Since (some of you) liked the memes, I decided to post two of the others I had prepared, but did not post lest the editorial look messy,

Relevant Meme, Problem C
Relevant Meme, Problem D
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

One of the best contests in quite a long time and the sweetest statements, and fast editorial! Thanks so much!

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

can anyone please explain to me why this N^2 solution of the problem B is giving TLE on test case 4. My Code

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

    try to use ss.clear() instead of creating a new vector everytime. check this 82160254

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

      Thanks for the reply but I found that even My code got accepted when I submitted it with GNU C++ 14 / GNU c++ 17 (64). but giving TLE with GNU C++ 17 although I don't know the reason

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

        Can you please explain your N*N approach a bit.

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

          Yeah sure, we have to observe that there are only limited strings (exactly 2*N) that can satisfy given conditions. A string should be such that first i characters are all one and rest are zeros or all first i characters are zeros and rest are ones i varies from 0 to n(size of given string). Then I simply calculated difference of each of the 2*N strings with given string and took the minimum answer

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

            It would be propably much faster if you actually do not create the strings in the first loop, but simply act like you would have done in the second loop.

            It is fairly simple to find if ss[i][j] is 1 or 0.

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

Can some one explain to me why in this test case "Ayush" wins not "Ashish" 1363C - Game On Leaves

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

    Ayush picks node $$$4$$$. Now, it is like the first test case, only the roles are reversed. No matter what Ashish picks, he will make node $$$2$$$ pickable for Ayush.

    UPD: I read your question wrong.

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

      why not pick 3 first

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

        Because they are playing optimally. Both of them would pick the most favorable one each move.

        It is mentioned in the problem statement:

        Determine the winner of the game if each player plays optimally.

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

        If he chooses 3 it will lead to 2 being the Leaf Node and in the next chance Ayush will choose it and win so playing optimally he wont choose 3 first

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

    If Ayush takes node 4, Ashish is forced to take either 1 or 3, both leaving 2 as a leaf node.

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

      why not Ayush take node 3 first

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

        Remember, both play optimally. Since taking node 3 would give Ashish the option to take node 2, Ayush won't do that, being able to guarantee a win by taking node 4 first.

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

Coolest Editorial Ever!

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

Come on, i thought i would be the first problem setter who splits key idea from complete solution :(. Nice job TheOneYouWant.

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

what does

if(arr[u] < mn)

signify in E's Editorial code ?

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

In Problem D, can't we use binary search to find the index of the max element and then use that fact. Since k<=n, the no. of operations at its worst should be equal in both cases.
What I m getting wrong? Here's my submission: 82156330
Thanks in advance!!

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

    What if the index with the maximum value is not in any of the subsets?

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

      Thanks, got AC with that approach too. I completely forgot that the subsets are not exhaustive and this case may arise.

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

Out of all possible errors how did I get memory limit exceeded for D ? :(( 82128649

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

Problem C is a harder (easier?) version of B. Binary Tree. The observations are almost identical in both problems.

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

can someone help me with the recursive dp or memoized approach for Problem B.

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

    Ummmm ! Now that you have mentioned I suppose it can be done using recursion with some clever memoization where recursively create all the strings of the form 1111's followed by 0000's and strings of form 00000'ss followed by 1111's We will create all the strings and check for a minimum ans out of all such possibilities and to add some memoization for any string we can calculate number of mismatches upto some index and later use it for fast computation !

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

    But Yes DP will be overdoing things a single prefix array will suffice to crack this problem !

    Happy Coding :)

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

in c problem if the test case: n=6 x=2 1 2 1 6 2 3 2 4 2 5 then ashis will be winner but n is even . anyone help please

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

    I don't think Ashish is the winner in this case ! in the first chance Ayush will go for 3,4,5 or 6 which are the leaf nodes and subsequently he is playing optimal so if you make any sort of choices from this state You will always Find Ayush having the last laugh!

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

Any clue about test case 37 of Problem D ?

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

https://codeforces.com/contest/1363/submission/82161309 why fflush(stdout) is not working??

upd: fflush(stdout) will not work if you are using fast con,cout in c++

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

Is there any approach for C involving grundy numbers and/or nim sum? I tried really hard to find someone..

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

    My idea is make the tree rooted from node x and calculate the amount of sons it has for each brach. Since for win the game I have to make the node x leaf, and for that need to eliminate all nodes of each branch first(all except one branch, I mean if there are k branchs, it is enough to eliminate k-1 of them) then the game is reduced to a modified nim game where the goal is reach the state {0 1} and for each turn the player can select one "heap" (amount of sons calculated previosly) and decrease it by 1.But I can't find a winning strategy for that game, please let me know if I am making some mistake..

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

      Solved: I realized that if I consider each heap as a nim heap the grundy number of each one will be 0 if it's even and 1 otherwise (this is because I'm only allowed to take 1 element each turn and 0 is a losing state) then I find the nim sum of the k-1 heaps, if the grundy number of the remain heap is 1 my nim sum change, otherwise nothing happen. So it is enough to find the nim sum of all of them. The special cases are handled seperately. This is equivalent to the approach of the editorial, but using Spargue-Grundy theorem

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

I loved the editorial.What an Explaination!Thank you so much FastestFinger Ashishgup TheOneYouWant. You guys won many hearts today!

Waiting for more Indian Rounds!

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

In Problem D, instead of binary searching the subsets, we can query[1..n] first to get the maximum, then binary search the index of the maximum by querying [1..mid] each time.

In this way, we can get the exact index of the maximum (when there are multiple, the first one).

Then we just check whether a subset contains this index. If so, we query its complement.

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

    UPD : Got it!

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

    Yes. Because $$$ S_i \cap S_j = \emptyset $$$, there's at most one subset which has index of first maximum element. Except this one, all position's password will be the maximum value. Then ask answer for this one with its complement.

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

    I did exactly the same but i am getting Idleness limit exceeded. Can you help me? https://codeforces.com/contest/1363/submission/82288138

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

      Your binary search is wrong. You are query [lo..mid] instead of [1..mid].

      My bad. Querying [lo..mid] is OK.

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

        Thanks for taking the time to see my code. The error was that ind's size was supposed to be n not k.

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

my logic for b was exactly the same don't know why test case 3 did't pass.

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

[Deleted]

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

Though I couldn't solve much I enjoyed it!

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

82161582

Can anyone tell me why this solution for Problem D is failing for testcase 37 ?

The basic idea behind the solution is that the variable lo is used to store the index of the maximum element; and mx and mn are the highest and the second highest elements of the array respectively.

After the binary search, I use one query to check the subset lo+1,lo+2,....,n-1,n because this subarray may hold the second highest number (This is because in all the previous queries, the mx variable would overshadow the the second highest number if it fell in the lo+1,lo+2,....,n-1,n subarray.)

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

    Is the second highest element always the one which is used for the subset which contains the maximum index?

    Here is a small failing test case:

    k = 1
    n = 3
    A = [3, 1, 2]
    S_1 = {1, 3}
    Correct: [1]
    Yours: [2]
    
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Wow!!

what a nice contest!

thank you so much.

especially an interactive problem on my level after a long time was so good.

I enjoyed it.

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

Nice problems. I enjoyed a lot. Thanks.....

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

Can anyone explain how to solve F?

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

Can someone help me why 82180993 getting RTE on test 9?

My idea is to sort the nodes non-descending by its cost and try to shuffle as many nodes as you can from the lowest-cost node.
I use segment tree and euler tour tree. After every shuffling, I updates every shuffled nodes with lower bound on sets (Maybe this one causes RTE)

I know there are neater implementation using root-to-leaf minimum, I'm just curious why my code gets RTE. Thanks

EDIT: Found it! Segment tree size is not enough. set segtree size to 1,2 mil apparently gives ac, idk why it needs that much for this problem

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

@hey i am just a beginner could u plz help me in editorial of B problem as iam unable to get .plz

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

    I will try to explain it to you ! To make a string free of any sub sequences of '101' and '010' I think you must have deduced that much that the only possible string which will form an answer must of one of the following forms.

    1) A series of 1111's 2) A series of 0000's 3) A series of 1111's followed by a series of 0000's 4) A series of 00000's followed by a series of 1111's

    So The Editorial of B is trying out all Possible such strings and considering the answer as a string with minimum mismatch between the given string as input and string we are considering ! Now Trying out all strings can Give U TLE ! So Using a prefix sum array to store in handy the number of 111's you have till i'th index will help you calculate the ans !! I can help you with the code part if idea is clear to you

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

I'm having very rough times solving C. Since last 3 contests, I've found a D/E that I found easier than C. This time it was E, I could do it in about 20 minutes after contest.

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

Hey guys i am having some trouble debugging my solution to E.I have added a few comments to my code here. my approach involves using dfs and if a node has a cost smaller than all its ancestors, we use this weight and do all changes possible to the subtree(including the node) of this node. Any kind of help will be appreciated. Happy coding :).

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

Hello Codeforces!

Thanks for the great contest FastestFinger Ashishgup TheOneYouWant

I am facing problem in Question D.

My approach is almost the same

1) First I find the maximum among the whole array.

2) Then I keep lo = 1 & hi = n and do queries to find the index between [1, n] which has highest element in the array A.

3) Then I iterate over all the subsets in S to see if it contains the index having the highest element in A. If it contains such an index then I make a query on indexes not in that subset and print that. Else I print the maximum element.

I am getting the wrong answer on test 4.

My code can be seen here:- 82190773

TIA

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

    After guessing the answer you are not reading the string "Correct" or "Incorrect". Just fix that and your code is good to go!

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

      Oh! I completely missed that

      Thanks a lot man for taking out your time.

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

    Note that it fails on the first test set with multiple test cases. There was a notice after the sample:

    Do not forget to read the string "Correct" / "Incorrect" after guessing the password.

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

      Oh! I completely missed that

      Thanks a lot man for taking out your time.

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

I have a solution for E which is similar to the idea in the editorial but it uses a small trick and without maintaining the parent and instead storing how many unbalanced cases are to be resolved by shuffling in sub-tree of a node. Code

For the case of impossibility if summation of bi != summation of ci, we print -1 otherwise we have a solution. We have a global variable ans which we print if it's possible to reshuffle values to get desired structure. So we maintain a global array 'unbalanced' which stores how many 1s in sub-tree of the node still require shuffling while maintaining a[node] <= a[par] for node != 1 (the root). So for any node let the initial unbalanced amount be c[node] — b[node]. We will see how this comes handy later. Now if we sum unbalanced[v] for all v in children of node with unbalanced[node] we get the number of 1s that cannot be shuffled within the sub-tree rooted at node. Even if it turns out to be negative it is fine as it will get balanced by some other nodes as summation bi = summation ci. Now unbalanced stores the number of 1s in sub-tree of v which cannot be resolved by any shuffles within the tree and the number of shuffles which can be made in the sub-tree is {summation abs(unbalanced[v]) | node is a parent of v + abs(c[node]-b[node]) } — {abs(unbalanced[u])}. We multiply this with a[node] and add it to the global answer variable, as the optimal cost for shuffling can only come from this because a[par] >= a[node] which I maintain by this, if(a[v] > a[node]) a[v] = a[node];

It might seem difficult to understand. A lot a of expressions in this comment would have cleared it even more. I hope someone reads this and finds it useful. :-)

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

Is that unrated?

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

Another solution B: resultant string will be of form s1+s2,where s1="00.." and s2="11.." or s1="11.." and s2="00..".looking at constraints O(n*n) will work .so we can check all strings of these type to find minimum number of changes.

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

I love the way you guys made this editorial. The concept of Key Idea and Detailed Explanation was really good .

»
4 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it
In problem E, if we change this part of code:
for(auto &it:g[u])
	{
		if(it == par)
			continue;
		pair<int, int> p = dfs(it, u, min(mn, arr[u]));
		a.first += p.first;
		a.second += p.second;
	}
To this:
for(auto &it:g[u])
	{
		if(it == par)
			continue;
		a.first += dfs(it, u, min(mn, arr[u])).first;
		a.second += dfs(it, u, min(mn, arr[u])).second;
	}

It dosen't work, why?

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

    Because dfs is not a pure function. If you call dfs twice, it will add to cost twice and cost will be wrong.

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

Good contest. My ego made me stuck on A and still couldn't solve in 5 attempts.I found B and C easier.

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

can anybody explain how to solve problem E i am not getting it as i want to know how to things will work on tree can anybody show tree diagram??

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

    Consider the following graph 4 1 2 2 3 3 4 then subtree of 1 is 2 3 4,subtree of 2 is 3 4 and subtree of 3 is 4 . then you are given some value of b and c . if value of b is 1 and value of c is 0 then you can shuffling between them ,and at the mean time you will consider the cost of the parent which cost is less. suppose you can shuffling node ( 2 , 4 ) or ( 3 , 4 ) .but the cost of 2 is 10 and 3 is 20 . so you will choose 2 as parent . and you will perform dfs and track down the minimum cost . To understand better you can watch this solution : https://codeforces.com/contest/1363/submission/82224132

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

In the editorial for D, why do we iterate from 0 to mid (inclusive) instead of st to mid (inclusive)?

Code:

		for(int i = 0; i < k; i++)
			if(i == st)
				ans[i] = interact(ask);
			else ans[i] = max_element;

I have something similar but mine is not passing.. . 82227750

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

    The problem encountered in that submission is due to poor handling of multiple test cases — in all cases, the second test case should produce an error.

    There is also a problem with the inverse querying.

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

Please,why I get “Memory limit exceeded” in probem D,82232793

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

    One large problem I see is the case when lab is left as -1 — in that case, too many numbers get added to ANS and likely corrupt the querying for the next test case. Since no error checking is done, that could leave some variables with an undefined value, possibly later causing a huge loop.

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

Please somebody help me out. I have done problem D using binary search as suggested in editorial but getting error: IDLENESS LIMIT EXCEEDED on test case 7. Link to my submission https://codeforces.com/contest/1363/submission/82238839 Thanks in advance :)

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

    No need to put your brain on it. I got my silly mistake i was doing. Sorry for asking such silly questions :(

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

In Subsequence Hate , I got "Wrong answer on pretest 2".

My submission : 82118663

But when I checked the testcase, it said for

10111101000010100

the answer should be 7 flips

but I can make it good by using 4 flips only 1(1)11110(0)0000(0)0(0)00, which is valid

Correct me, if I'm wrong on understanding the problem statement.

Resolved: My mistake! Thanks dorijanlendvaj for correcting.

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

    Your solution says that the answer is 7; the correct answer is 4.

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

    The answer it expects is 4 and your code gives ans as 7 ! I have seen your code and I suppose you are tring to find first occurence of 1 and then making 0's after that as 1 and also doing the same thing for first occurence of 0' this logic will not work !! I suppose you should try to approach the problem with trying all the series possible cleverly and form an answer in O(N) time

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

Can anyone give a rigourous proof for the dp solution for f. What does the dp state define?

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

A new era is arrived and that is EDITORIAL WITH MEMES....

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

https://codeforces.com/contest/1363/submission/82288453 can anyone tell me why i am getting memory limit exceeded in my code?? i have submitted 10 times not able to figure it out please help??

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

    Your code produces a wrong answer on some test cases. However, since you don't check for the string being "Incorrect", the code attempts to read more values, leaving some variables (especially importantly k) in an undefined state.

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

      Can you guide me how to fix it?? It's my first interactive problem...

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

        First, please do check for "Incorrect" — this should give you the correct verdict and allow you to better analyze what went wrong.

        For the underlying problem, I can provide a (hopefully) failing test case:

        n = 6
        k = 2
        A = [3, 1, 2, 3, 1, 2]
        S_1 = {1, 3, 6}
        S_2 = {2}
        Correct: [3, 3]
        Yours (expected): [1, 3]
        
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          So in my while loop I should make a if condition if the input string is correct then I will continue loop and if it's incorrect I should return 0?? In this way it will work or different syntax I should prefer for this??

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

            Yes, return 0; or exit(0); should work fine for exiting if the string read in is "Incorrect".

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

        Honestly, I spent about an hour looking at this code previously — it behaves just like mine and seems to work on the same principle, but I can't find anything that should be wrong. I even tried a few tests against it on my machine.

        My next line of action would be to create a problem host (providing the problem / interaction), then generate (small) random test cases to see whether an error can be found to analyse what goes wrong.

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

          I will do this. Thank you so much for your time and help

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

            OK — I took yet another look at this, and I'm pretty sure I noticed the error at last:

            vector<bool> ind(k + 5);
            for (auto s : subs[i])
                ind[s] = true;
            

            ind could be accessed with values up to $$$n$$$, but $$$k \leq n$$$, so this could go out of range, causing all sorts of problems.

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

              Silly mistake as always !! Thank you so much i was really struggling and couldn't find the error. much appreciated.

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

I am getting Idleness limit exceeded on problem D. Can somebody help me? https://codeforces.com/contest/1363/submission/82288138

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

Can someone explain the editorial solution of 1363F - Rotating Substrings in detail..

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

    I'd like to hear another explanation too because I'm also confused about this solution

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

I have implemented same logic in problem D as explained in editorial still getting wrong answer. Query Function is returning a garbage value. Plz help anyone? Here is my submission id :- https://codeforces.com/contest/1363/submission/82306483

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

    You're trying to query in the middle of printing the password.

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

      Now I have removed query while printing password but still I am getting garbage value in query thats why it is printing garbage value in answer when i tried in custom input. Sir plz help, this is first time when I am doing a Interactive problem. https://codeforces.com/contest/1363/submission/82337085

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

        You're getting a garbage value since the testing program closed its input, but the code is stuck in a loop trying to get more values. Note my other comment.

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

          Sir , now I removed the infinite loop case but still it is giving wrong answer. Plz help sir https://codeforces.com/contest/1363/submission/82339279

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

            Now, you query the maximum of the set that contains the maximum element in the array, using that value for the position where elements from that set should be ignored.

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

              I have done this but still its giving me wrong answer :-( Please help sir. https://codeforces.com/contest/1363/submission/82363733

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

                Interestingly enough, the first test is an edge case for your program — what happens when the greatest element is in the last set (so only the start = mid + 1; branch gets run)?

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

                  Sir, now i took care of that condition also but now it is giving wrong answer on test case 14 https://codeforces.com/contest/1363/submission/82369145

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

                  The problem now is that you're making up to 11 queries to find the correct set, one to find the maximum value and another one to find the maximum outside the set which has the index corresponding to the largest value.

                  You need to get rid of a query somewhere, possibly changing your approach.

                  The second-to-last paragraph of the explanation mostly addresses this problem.

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

                  Sir, but in question maximum queries allowed are 12?

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

                  Yes, however your code might make up to 13 queries, since it could make up to 11 queries in the binary search.

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

                  Ohh, I got my solution accepted:-).Thank you very much for your time , without you it was not possible for me.

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

    Also, the actual issue currently causing the first test to fail — your binary search gets stuck in an infinite loop if the greatest element is inside one of the subsets.

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

I am a newbie can you help me with code below? Codeforces Round 646 Div-2 1363A-Odd selection what is wrong in my code?

https://codeforces.com/contest/1363/submission/82093977

Also all suggestions will be welcome :)

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

    Please, instead of pasting your code in the comment, provide a link to your submission — it reduces the size of the comment and makes the code more readable.

    82093977

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

    You have access to the test that failed, and it is quite well readable — you can step through your code logically to see where the fault occurs.

    In particular, note this branch of the main logic:

    if(o>n){
        // ...
    }
    else{
        if(o%2!=0){
            cout<<"Yes"<<endl;
        }
        else
        cout<<"No"<<endl;
    }
    

    An easy counter-example would be an array with two odd numbers and two even, asking for whether the sum can be an odd number when picking 3 elements.

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

In Problem D, i am getting WA in case 16, but i cannot figure out why? My Approach : I first got the maximum value of full array, than by binary search find out the position of that maximum value in the array. Than just proceed the k subset. Can anybody look at my code and help me to figure out please, My Code

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

    marko312 at first sorry for mentioning you, i saw you did reply to many comments, can you help me pls!

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

      Since $$$1000 > 2^9$$$, you will need to make more than $$$9$$$ queries in your binary search for large enough inputs. It was mentioned in the editorial that the bound was tight.

      You can try the following test case:

      n = 1000
      k = 1
      A = [2, 1, 1, 1, 1, ...]
      S_1 = {1}
      Correct: [1]
      Yours: [2]
      

      In this case, your code will think that the second index in the array has the largest value.

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

        Thanks, i miscalculated the iterations value, i count printing the answer as one of the query that is s why i took iteration = 9, now i just changed iteration = 10 and it got Accepted :D
        How silly i was :(

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

damn!! the editorial is really good!!

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

Could someone please explain me problem E ? I missed something and I really don't get it and it angers me.

Why is last example impossible?

2
109 0 1
205 0 1
1 2

Just take node 1 and switch digits of nodes 1 and 2... Cost : 218.

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

    Node 1 contains 0, needs 1.

    Node 2 contains 0, needs 1.

    If you swap the values they have, neither of them reaches its target value. Hence it is impossible.

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

      Thanks, i didn't understand the word "shuffle" correctly.

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

Good follow up for beginners -
In Problem A, count the # of ways of choosing $$$x$$$ numbers so that the sum is odd.

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

What is the purpose of the variable mn in the editorial's solution for E?

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

Can someone please explain how the moves will carry out for this input -

1 5 5 4 5 4 2 3 5 4 1

I presumed -> Ayush takes 1, Ashish takes 2, Ayush takes 4, Ashish takes 5 and wins

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

    That is correct. However, based on your solution, I think you thought that was the test that failed your code — the failing test was actually the next one:

    1
    4 1
    1 3
    2 1
    4 1
    

    Here, Ayush can win after Ashish's move, but your code output that Ashish'd win.

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

solution :- https://codeforces.com/contest/1363/submission/82384349 code for D, getting an absurd error if anyone could help?!

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

    The diagnostics output gives quite a good warning:

    Error: attempt to subscript container with out-of-bounds index 0, but container only holds 0 elements.

    Looking at the code, the reason is quite clear:

    pre.clear();
    for(int i=0;i<k;i++){
        int c;
        cin>>c;
        if(i==0) pre[i] = c;
        else pre[i] = pre[i-1] + c;
        // ...
    }
    

    You likely want to resize the vector before assigning new values to it.

    Also, note that the vectors in s are never cleared.

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

can any one explain 1st problem?

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

    This was my thinking in the contest:

    Look at the array 'a' modulo 2. It will be 1s and 0s.

    Count how many 1s there are — 'numOnes' and how many 0s there are — 'numZeros'. The minimum sum we can create with x elements is lb = max(0, x — numZeros), where we took as many 0s as possible. The maximum sum we can create is ub = min(x, numOnes), where we took as many 1s as possible. Since the entire array is 1s and zeros, we can also create any number in the range [lb, ub].

    Now the sum of the x elements we pick can be odd if and only if the sum of their remainders modulo 2 is odd, that is, when there exists an odd number in the range [lb, ub]. Obviously this odd number will not exist if and only if the range consists of a single even number, that is, lb == ub && lb % 2 == 0.

    My code: https://codeforces.com/contest/1363/submission/82065526

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

can someone help me on question D? I am getting "Idleness limit exceeded on test 7" though I used cout.flush(). Here is link to my submission : https://codeforces.com/contest/1363/submission/82422145

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

    Have you tried going through the failing test case with your code? It prints too little numbers in the last query sometimes.

    Note: the test cases there are in the hack format, so the second line of each case describes $$$A$$$.

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

      Yeah, Later I realized my mistake, But it is still failing on test 74. But I could not see the full test description.

      Link to my submission : https://codeforces.com/contest/1363/submission/82456592

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

        In if(tot < n), maxm is set to the maximum of all values corresponding to indices not in a set. However, in the code that follows, you use it as if it was the maximum of all elements in the array.

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

I came here for the memes

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

82879714 It said,"Wrong answer on test 2."

what is the problem? I don't understand. Please help me.

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

    You have got some double cases here, then you output more than one answer. Maybe just a break is missing.

                       else if((x-i)<= even)
                            cout<<"Yes"<<endl;
    
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please add the link of the editorial with the problems.

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

Problem F ( Rotating SubString ) :: Commented Code With Explanation

101216700

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

In Question C what this line means "and remove it together with any edge which has this node as one of its endpoints."

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
  • I am seeing Tag of Problem as Hint and rather than it being helpful,it is just pointing in wrong direction.It is doing more harm than good.
  • DP tag is default for every question. If you use array to read input then DP tag is being added to question since it is using Memorization.
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    well just ignore it.besides i don't think it is that bad.

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

Problem E I was sorting the array of values and then trying to Exchange the pairs and trying to update the tree but I was struggling to update the tree in less complexity and couldn't come up with a solution and thought this is right approach or requires some Datastructure or some technique.