newbie_to_cp's blog

By newbie_to_cp, history, 6 weeks ago, In English

Regarding Div3 D problem submission 1 submission 2 Here both the solution are same but the fact is one is hacked and other is not ,could u please suggest the input User Id link

 
 
 
 
  • Vote: I like it
  • -10
  • Vote: I do not like it

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

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

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

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

»
6 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

You don't need to worry. After the hacking stage is over, all solutions from all participants will be tested against all extra testcases discovered by hackers. If the second submission is still buggy, it will be rejected too.

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

    bro i asking about reason why so??

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

      The changes indeed seem to be just cosmetic:

               // db(x);
               if(x < 0){
      -            dp[abs(x)][1]++;
      -            ans += dp[abs(x)][1]-1;
      +            int r = -x;
      +            dp[r][1]++;
      +            ans += dp[r][1]-1;
               }
      

      But both are slow and very close to TLE. I suspect that memset of the dp array is killing performance. If t is very large, then the whole buffer gets cleared way too many times.

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

        Bro it got accepted in final testing

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

          It got accepted after completing the 11th testcase in 1981 ms, which was only 19 ms away from failing (the time limit is 2 seconds). With some minor runtime speed fluctuations, it could either get accepted or fail.

          What's your problem? Do you want to know why this solution takes almost 2 seconds? Or did you want it to get a TLE verdict very much?

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

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

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

Server load presumably the difference. Really, they both ought to fail — it's bad code. It is not good to do memset on dp[200005][2] for each of 10000 test cases — that's 4 billion operations.