i downvoted both , problem C gave tle on pretest 4 and same logic passed in c++

Problem C seemed so simple yet turned out to be the most painful one. Just wouldnt work with Java

It will published later on...btw it is mentioned above...

Don't swear, It is bad

got runtime error 2 times because of this

This ruined my contest. Literally i got 4 runtime errors on pretest 2 for this reason. In the question it was mentioned if 2*n+1 moves are done then the game finishes. Also there were no pretests that had 2*n+1 moves to make it more clearer.

Same here.

salyg1n, green_gold_dog, ace5, bashkort. Isn't it a mistake on author's part? If so, can we manually set my current AC time to my first attempt in problem C? (As it would've been AC in first attempt without this issue)

Exactly spent 1.5 hr while submitting the same code as I can’t notice any error. The round should be unrated.

+1

Same thing here. I first tried submitting various java solutions only to get TLE. Same logic in C++ passed in first go.

Sounds like a skill issue to me.

Same issue.

My best guess is for test like #4 where T = 100000, the system judge does not generate the input data for next test in stdin fast enough after the previous test complete.

I tried to simulate stdin for 100000 tests each with n = 1 on local machine like below. It measured 185 msec. So the fact that test #4 always TLE in system tests suggest some kind of delay introduced by system test for Java submissions.

  static void simulateLargeNumOfTests() {
    long t0 = System.currentTimeMillis();
    {
      // Prepare stdin for 100000 tests each with n = 1 and mex 0.
      // In such case, an immediate -1 will follow after the input of each test.
      int T = 100000;
      StringBuilder sb = new StringBuilder();
      sb.append(T);
      sb.append('\n');
      for (int t = 1; t <= T; t++) {
        sb.append(1);
        sb.append('\n');
        sb.append(1 + RAND.nextInt(1000000000));
        sb.append('\n');
        sb.append(-1);
        sb.append('\n');
      }
      byte[] data = sb.toString().getBytes();
      InputStream fakeIn = new ByteArrayInputStream(data);
      System.setIn(fakeIn);
    }

    {
      MyScanner in = new MyScanner(true);
      int T = in.nextInt();
      OutputStream out = new BufferedOutputStream(System.out);
      for (int t = 1; t <= T; t++) {
        int n = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
          a[i] = in.nextInt();
        }
        solve(a, in, null, out);
      }
    }
    System.out.format("%d msec\n", System.currentTimeMillis() - t0);
    System.exit(0);
  }

After using a hack to workaround test #4 which always TLE in System Verdict, this submission https://codeforces.com/contest/1867/submission/223000398 is Accepted with runtime 1949 msec on test #6 where the input array has length 100000 and MEX 100000. It is unclear exactly how many IO interactions in test #6 as it depends on how greedily the Judge choose y each time.

Overall, the interactive IOs delays of problem C is too much for the given limit of T and timeout, and the problem is partially to do with the System Test. Problem C should either use a smaller limit like 10000 for T or a bigger timeout so to accept legit Java solutions without losing any generality of the problem.

Same for me. But at the end when I was done with coding, and I was trying some random cases and suddenly it hit me that this should be the accepted solution.

same I almost wasted 30 minutes about thinking it and then I reread the question did it in 5 minutes and then went for e2 made the logic but guess what forgot to print ? in making query and didn't make it whole time I was thinking about my solution but the error was in my code :(

Completely ruined my contest. But it's my fault, I missed "Even".

what???i completely didn't realize n and k are both even even at this time!!! sad about this...

I don't know the completely trivial solution :(

Can you explain it?

How to progress from solution for E1 to E2?

maybe you should learn from SecondThread and profchi :)

Yes.

problem D : if a linear chain of size > k is connected to a k length cycle then how is possible to generate a pattern to get array B?

Actually, I think quite easy to kill random approaches for F, one can just construct a tree with all possible subtrees of size k except for 1 which random will find it hard to find.

Ackchyually, you must know that $$$n$$$ and $$$k$$$ would be even, when the problem is E1.

Where do you see bitwise operator that much. Xor in binary strings = flipping i-th digit. Problem A isn't about bitwise at all

Wait really? I didn't even see, I wasted up my time trying D :/

For Java as well

I use python and got TLE on problem B testcase 11, problem C testcase 4 with default input() method during the contest. But after adding

import sys 
input=sys.stdin.buffer.readline

They all passed the test.

A really frustrated experience for me though.

Yeah, that was very confusing

I don't think there was any ambiguity in the problem statement. The interaction guide says that after you output $$$x$$$, you should read an integer $$$y$$$. It never says that you should read $$$y$$$ only if the game is not already over or that you should read $$$y$$$ only if Bob is making a move: every time you output an $$$x$$$, you need to read a $$$y$$$.

It's particularly easy to get tripped up on interactive problems by making incorrect assumptions about the I/O format, which is why you should always read the interaction section of the statement carefully before beginning to implement your solution.

"To make a move, output an integer $$$x$$$ ($$$0 \le x \le 10^9$$$) — the number you want to add to the set $$$S$$$. $$$S$$$ must not contain $$$x$$$ at the time of the move. Then, read one integer $$$y$$$ ($$$−2 \le y \le 10^9$$$)."

Is it not clear that after every time you output $$$x$$$, you need to read in $$$y$$$?

I also did not solve A, do not worry, sometimes things just do not work out, keep solving tasks and you will improve.

Maybe these help:

• https://codeforces.com/blog/entry/16599
• https://codeforces.com/blog/entry/17842
• https://codeforces.com/blog/entry/66909

Solve more. Whole cp is just trying to see patterns of problems already solved by you in new problems.

It's okay man, I got WA two times on pA this contest also and I almost gave up and just quit. The point is that you need to keep calm and try observing some key observations. Also if div 2 is too hard you can try div 3, 4 and atcoder. GL!

According your code, I think when Nextmove = n; it will wrong. Like this: n = 2 a[] = 0 1 Step 1: A:2 B:1 Step 2: A:1 B:0 Step 3: A:0 B:-1 -> it need n+1 loops

Not necessarily, you can do this to k nodes without them being in a cycle, I will explain solution.

I just checked that every path from a non-zero element leads into a cycle of length $$$k$$$.

UnfairForces

I haven't found any. I found a handful of pypy solutions :(

Found one.

222934542

System.out.println() is every slow so I used c++ for this task. If it was not interactive we can use fast output

I'm in. I'm too green.

I accidentally understood the proof of solution by YocyCraft while answering one of the comments, but I couldn't solve it myself. I guess practise makes perfect. At least you got the idea to use functional graphs

I did not solve it during contest, but I did after the contest without looking at any hint/solution.

$$$a_{l_i}$$$ to $$$l_{(i\%k)+1}$$$ looks like a complicated formula, maybe there is some special meaning behind it, so we should try to understand it better. It should be obvious that $$$(i\%k)+1$$$ means the next element, so for thinking's sake let's just assume it is $$$i+1$$$. Then $$$a[l[i]]=l[i+1]$$$ is the code equivalent of the formula. We also have $$$a[l[i+1]]=l[i+2]$$$, and if you substitute back you get $$$a[a[l[i]]]=l[i+2]$$$. Hopefully at this point it looks enough like a linked list and $$$a$$$ represents the next array.

Knowing properties of successor (functional) graphs may help, more specifically that in each component of a successor graph there is one and only one cycle (I completely forgot about that one during the contest).

It only takes a few simulations of the operation on the sketchpad to discover the cyclic.

Hints:

Consider the indices $$$i=1,2,\dots,\big\lfloor\frac{N}{2}\big\rfloor$$$.

If $$$s_i=s_{n+1-i}$$$, then we must use either $$$0$$$ or $$$2$$$ ones at these indices.

If $$$s_i\ne s_{n+1-i}$$$, then we must use exactly $$$1$$$ one to flip one of these two bits.

Furthermore, if $$$N$$$ is odd, then we can flip the bit in the middle if we want to.

Because C++ > Java

UnfairForces

bashkort ace5

Accepted solution using Java

Problem C has either too big T or too tight time limit. For example, it could have a limit of T like 10000 instead of 100000. As a result, the problem would be more effective to accept Java solution with the right idea and algorithm. The way it is requires low level IO hacks to squeeze the last IO efficiency to possibly and barely meet the time limit, and as a result the IO code is messy and has poor readability etc, which is NOT the purpose no should be the focus of the problem.

IMHO:

2*n+1 is Alice's last move, after this Bob replies with -1 (which goes to your "n" in the outer loop).

2*n+2 reads "-1" and moves to the next test case.

Because author studies in 57th school

The constraint does not have to be at the tight lower bound. 51 might serve as a big hint; author might have other legit ideas to solve the problem etc.

did you find that there're a lot of 57 in the problem set?

It seems PyPy struggles more with IO: 223000606

alwayss use FAST I/O with python , add this to your code and it will get AC :

import sys

input = lambda: sys.stdin.buffer.readline().decode().rstrip()

t = int(input()) .........

Your code currently spend most time reading in data. What you need is a faster input:

import sys

input = sys.stdin.readline

This is a must for all python/pypy coders, otherwise you will TLE a lot. Just copy the faster input into your template.

Thanks for the help guys!

Congrats on reaching cyan!

Dammn Bro, A Big Yes, in fact after solving E1, E2 was kinda obvious. I should have attempted these questions 1st before D :(