Discussion @ 1396. Maximum. Version 2 @ Timus Online Judge

NEW PROBLEM 1396 “Maximum. Version 2” has been added. (-) Vladimir Yakovlev (USU) 10 May 2006 19:33

This problem is the same as 1079 “Maximum” but with bigger limitations.

Edited by author 10.05.2006 19:37

I have a proposal (+) Dmitry 'Diman_YES' Kovalioff 11 May 2006 12:20

The problem is just added, so it may be easily modified. Let it be more than 10000 lines in input - so that the TL would be strict enough and my solution get TLE ;)

Edited by author 11.05.2006 12:21

Your solution is fast enough, don't tount at me (-) Vladimir Yakovlev (USU) 11 May 2006 12:58

:Ashamed: I did not mean to taunt. I just want this problem to become harder a bit (-) Dmitry 'Diman_YES' Kovalioff 11 May 2006 13:45

Oh! Limitations too weak indeed! I think that N < 10^18 would be better :) Vladimir Yakovlev (USU) 11 May 2006 15:27

Burunduk1, please, resubmit your solution for N < 10^18. I will use your solution to generate new tests ;-)

Edited by author 11.05.2006 15:31

I've resubmited it. (ID=1187372) Burunduk1 11 May 2006 19:02

Re: I've resubmited it. (ID=1187372) Vladimir Yakovlev (USU) 11 May 2006 19:30

This code will get WA with N < 10^18.
Guess why?

Re: This code will get WA with N < 10^18. Burunduk1 11 May 2006 20:10

And for N < 10^17 ?
Try to change "__int64" to "unsigned __int64".

Yes, for N < 10^17 too Vladimir Yakovlev (USU) 11 May 2006 20:24

Re: Yes, for N < 10^17 too Burunduk1 11 May 2006 20:28

Please, give me my AC solution!!! (to sk1@hotbox.ru)
I modified it (of course without backup) and now it
doesn't pass second test. (or you've already added new tests?)

PS: This ability (to view submitted solutions) is useful.

Sent (+) Vladimir Yakovlev (USU) 11 May 2006 20:37

And now there is only one test

Re: Sent (+) Burunduk1 11 May 2006 20:39

I see... (know the same solution gets WA 1)

Have you received my letter? Vladimir Yakovlev (USU) 11 May 2006 20:41

Re: Have you received my letter? Burunduk1 11 May 2006 20:42

AC ;)
!!!
:)

My congratulations! Vladimir Yakovlev (USU) 11 May 2006 20:43

Re: Have you received my letter? Burunduk1 11 May 2006 20:43

The bug was in this:
I calculated F[i] int 32-bit integer.

Re: Have you received my letter? Ilya Grebnov[Ivanovo SPU] 11 May 2006 22:04

Do you use any precalculations?

Re: Have you received my letter? Burunduk1 11 May 2006 23:19

My solution consists of only precalc.
I calculate all different maximums on [1..x]
where x is any integer between 1 and 10^18.

Oups... I need a new solution for 10^18 ;) (-) Dmitry 'Diman_YES' Kovalioff 11 May 2006 20:19

Limitations were changed, problem rejudged Vladimir Yakovlev (USU) 11 May 2006 20:32

Re: Limitations were changed, problem rejudged Burunduk1 11 May 2006 20:34

I see...
And why you haven't got AC?

My solution is bad :) It work for N < 10^11 only (-) Vladimir Yakovlev (USU) 11 May 2006 20:39

I wish I had a supercomputer ;) P.S. The problem seems to have only one test (-) Dmitry 'Diman_YES' Kovalioff 11 May 2006 20:54

Oh! You got AC! Where did you find supercomputer? Vladimir Yakovlev (USU) 12 May 2006 00:48

Re: Oh! You got AC! Where did you find supercomputer? Nika Jimsheleishvili (Tbilisi SU) 19 Sep 2006 19:06

I have found O(logN) solution in one book.
Very nice idea.

Re: Oh! You got AC! Where did you find supercomputer? Гладких Максим 22 Sep 2006 00:55

As far as I know solution of this problem in O(logN) can be found in Shens book...

Edited by author 22.09.2006 00:57

Edited by author 22.09.2006 00:57

Edited by author 22.09.2006 02:01

Discussion of Problem 1396. Maximum. Version 2