endless-chase's blog

Help me!
By endless-chase, history, 5 years ago, In English

Last contest,I failed system test on D,that I didn't become an IGM.

But I don't know why my D failed system test,I submitted the same code $$$3$$$ times today,they all get Accepted.See 72380842 72380904 72381047

I think it's the problem of randomized integers,but I don't know why.Please help me!

Here's my solution to D: Let's Maintain candidate roots,at the beginning,every vertex is a candidate root.In each query,we randomly choose two candidate roots that are not adjacent and not equal.Let's denote them $$$x,y$$$,then we ask $$$x,y's$$$ lca,denote it $$$w$$$，then for every $$$w$$$'s subtree that contains $$$x$$$ or $$$y$$$,all of the vertex in it can be removed from candidate root.It can be shown that in each query,we remove at least two candidate roots.All the vertices left form a subtree of the original tree.There's a special case on $$$n=2$$$,just ask these two vertices.

Here's my submission:72324004

Sorry for my poor English.

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

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

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

→ Reply
»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Maybe there is something different between c++14 and c++17 (Your contest submission is c++17 but after it you choose c++14) But I don't know what's the difference.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +27 Vote: I do not like it

I have never seen this verdict before O_o. To me at least, it seems to be related to Codeforces itself, not about your algo.

→ Reply
»
5 years ago, # |
  Vote: I like it +31 Vote: I do not like it

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

    I had the same output format "bug" occur to me a few days ago while solving some old problem for practice. I asked around and everyone seemed to agree it was a very rare Codeforces bug. Link to said submission. You can see the error code in my submission is the exact same as in nick's submission ("output.fd0138e687.txt").

    I think endless-chase deserves to have this case looked at by Mike or some staff member, and hopefully this can be investigated and fixed to prevent future problems.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

rand() returns value between 0 and RAND_MAX. On my machine it is:

//The largest number rand will return (same as INT_MAX).
#define RAND_MAX        2147483647

So Get function can sometimes return negative values due to overflow with << 10.

I run your solution and passed 2 as seed to srand. And Get returns -3. So it's clearly UB.

→ Reply