jucason_xu's blog

A Hacking atempt to 1107G
By jucason_xu, history, 2 years ago, In English

Today I am doing 1107G, I find there is something wrong with my st-table, so I change the st-table into brute force and submit it only to check if my main algorithm is correct.

But to my surprise, the brute force got an "Accepted" verdict in "233ms".(the time limit is 3.5s) https://mirror.codeforces.com/contest/1107/submission/180935577

I am very confused and check the time complexity of my code.

Then I find that:

The st-table code is $$$O(n\log n)$$$.

If I change the <= on the 61-th line into <,it's also right though it seems to be $$$O(n^2)$$$. Because under the constraint of $$$d_{i}<d_{i+1}$$$, it's impossible to construct a testcase with more than 40000 positions with a increasing $$$(d_{i}-d_{i+1})^2$$$.(if the limit of $$$d_i$$$ is $$$10^{18}$$$,it will be TLE as well.

But the original code is totally wrong. It will be TLE on a test constructed in this way:

int cur=100;
cout<<300000<<" "<<300000<<endl;
cout<<1<<" "<<100000<<endl;
rp(i,299999)cout<<cur+i<<" "<<1<<endl;

It takes around 25s for the original code to run, much more than 3.5s.

The Custom Invocation of Codeforces can input only 255KB test, so I test it on another OJ (luogu). You can take a look at https://www.luogu.com.cn/problem/U261730 and submit #180935577 into it to see if it has a correct complexity.

And all the correct codes runs well on the only Hacking data.

I know Codeforces has very good testing computer, but it can't change 25s into 3.5s.(If it can...)

I don't know what to do to hack or add testcases to a 5-year-ago edu contest.

I also don't know how many people got "Accepted" in this problem with totally wrong code.(maybe only me?)

If there's some ways to submit hacks or add testcases, please tell me.

If it is unnessesary in Codeforces rules, please ignore this blog or tell me under the blog.

And please tolerate my poor English :)

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

Comments Comments (8)
| Write comment?
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
2 years ago, # |
  Vote: I like it -92 Vote: I do not like it

I think this is not valueable just like you.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it -76 Vote: I do not like it

    You are stupid,And I think you are mad.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it -76 Vote: I do not like it

      Emm..Are you the same people as jucason_xu？Because jucason in Chinese is xjc.

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

I won't tell you the three unrated guys above me are all the same people's Alt-account, he is just in a same classroom with me.

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it -55 Vote: I do not like it

The comment is hidden because of too negative feedback, click here to view it

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

UPD: After apply some constant optimization to the wrong code, it easily become one of the best solutions submitted to 1107G. It is so funny that a solution with a complexity of $$$O(n^2)$$$ spends only 62ms to pass a problem with $$$n=300000$$$.

→ Reply