Mikester's blog

Problem H from Goodbye 2015
By Mikester, history, 8 years ago, In English

Hey guys ! I kind of need your help to understand why I can't get past a test on this problem:

http://codeforces.com/contest/611/problem/H

It fails on test 3. I've extracted that test, ran it with my solution and to me it seems nothing is wrong. The checker reports "Graph is not connected", which is weird because if you check the output, it IS connected. Every node is connected to either node 1 or node 10, and nodes 1 and 10 are connected with each other.

My solution:

http://codeforces.com/contest/611/submission/15219155

Input of Test 3:

http://pastebin.com/F2CwiYdZ

My solution's output to Test 3:

http://pastebin.com/RbcpfP5e

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

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

You have undefined behavior. For me locally (on my computer) your program indeed prints a correct output, the same you uploaded in pastebin. But try to run your program using "Custom Invocation". There you print an edge 100 10 and you don't print anything with 110. Last lines of your output in CF:

99 10
100 10
101 10
102 10
103 10
104 10
105 10
106 10
107 10
108 10
109 10

"Custom invocation" shows only some number of first lines of the output. So, to see last lines you can change for (int i = 0; i < sol.size(); ++i) to for (int i = 80; i < sol.size(); ++i)

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

I've looked through your output using "custom invocation" tab, your solution prints edge "10 100" twice: on 2nd line and on 100th line. Looks like there is a bug somewhere.

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

Thanks a lot to both of you for that find. The problem was with the line (int)pow(10,x) which was my way of getting a power of 10. It can evaluate to 99.9999.. which rounds down to 99.

→ Reply