ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1682. Crazy Professor

Ideas for #41
Posted by bstu_student 7 Aug 2018 10:59
Does anyon know, what is the longest test? I check a couple of numbers,with k= 99998 execution was the longest, but i'm not sure.

UPD: I check (write k=99998 instead a reading  number), and if WA#1 said truth, i reach the answere in 0,71. But this decision is still have TLE#41 :(

Maybe, there is a harder 'k' for this task?

Edited by author 07.08.2018 11:17

Edited by author 07.08.2018 11:17
Re: Ideas for #41
Posted by die_young 7 Aug 2018 13:50
You can try to binary search the test case.

Put somewhere in your program the following

if (clock() >= 0.9 * CLOCK_PER_SEC) {

You need to include <cassert> and <ctime> for these to work.

Now  (double)clock() / CLOCK_PER_SEC gives you program execution time in seconds.
clock() >= 0.9 * CLOCK_PER_SEC   checks that your program runs more than 0.9 seconds, in other words, approaching TL of 1s.  This 'if' allows to execute code that will probably work only on 41th test case.

assert( boolean expression ); exits with non-zero value if condition is not met.

You could also do
   exit(your favourite non-zero number);

So, you can start with assert(K <= 100000 / 2) and so on. If you program fails on 41th test with RE instead of TL you change the bin search value.
Re: Ideas for #41
Posted by bstu_student 7 Aug 2018 14:16
Great thanks!)