asdfghjl's blog

841B
By asdfghjl, history, 7 years ago, In English

For my first solution I was expecting WA because of integer overflow (int sum) but I got TLE instead which is odd because my time complexity is O(n) and it should work for the maximum value of n(10^6)!! Then I just tried the same code with scanf/printf and got AC :| I also changed the type of sum to long long and used cin/cout like the first time and got AC! Can someone tell me WHYYYY?

link to my second solution

link to my third solution

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

Comments Comments (9)
| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Your third solution passed with 1981 ms, the first one was also close to the time limit probably, so it's just pure randomness.

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

The gist is, that above and close to orders of 10^6,the way you handle input(scanf/cin) and output(printf/cout) also starts to matter i.e adds up in your total time complexity whereas it is generally considered to be a negligible constant for smaller orders.Hence,many of us got TLE in the 429 Div2B.There are ways to take fast inputs,this link may help :) Have a look. http://mirror.codeforces.com/blog/entry/925. Also both of your solutions were judged at different times,one during the system testing when there was heavy load on CF servers,and the other relatively low load after the sys test. :)

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

    I know about this but look at my third solution I used cin/cout and changed sum's type to long long to avoid the integer overflow and got AC. It shouldn't have reduced time complexity!

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

It's a common mistake. Nearly everyone has done it when starting out. Just use scanf by default and you won't run into similar issues, or if you prefer cin set sync to false. Fast I/O is important for Competitive Programming.

Another tip, don't use unordered_map unless you are sure you need it over map. Sometimes there are anti-hash tests which will make unordered_map TLE while map will pass. Here is an example of this : http://mirror.codeforces.com/contest/670/problem/C

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

It got AC because if there is at least one odd number answer is "First" and you used OR operation, so variable "sum" doesn't changes answer for any test. Note that if flag is false so sum should be even number and overflowed even number is also even number.

P.S. This comment is about second submmission.

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

    yes,you are right the sum is overflowed in the first submission.

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

      It doesn't matter, just see second submission, "sum" is integer and it overflowed, however, it got AC. I was explaining why this happened.

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

lalalalalalalalalalala

→ Reply