Discussion @ 1494. Monobilliards @ Timus Online Judge

Angelwarrior What does "Crash(acces violation)" mean? // Problem 1494. Monobilliards 13 May 2009 21:09

FreezingCool TLE test 28??? [1] // Problem 1494. Monobilliards 7 Jan 2009 21:46

(中山一中) What is the problem mean? [1] // Problem 1494. Monobilliards 3 Jan 2009 12:37

Fyodor Menshikov Weak tests [7] // Problem 1494. Monobilliards 19 Nov 2008 00:37

I know AC solution to this problem, that uses O(1) memory. It is wrong, and answers "Not a proof" for test
4
3
1
4
2

Alex Tolstov Re: Weak tests // Problem 1494. Monobilliards 19 Nov 2008 00:46

Yes, it's my solution with ID = 2350964
http://acm.timus.ru/status.aspx?space=1&num=1494&author=52345

Fyodor Menshikov Re: Weak tests [5] // Problem 1494. Monobilliards 19 Nov 2008 01:09

I think that there is no correct solution with memory complexity less than O(N). N or at least N/2 integers may be required to be stored at some moment on hard test. On page
http://acm.timus.ru/rating.aspx?space=1&num=1494&count=100
there are many solutions that use too little memory to be correct.

Sandro (USU) Re: Weak tests [4] // Problem 1494. Monobilliards 20 Nov 2008 12:06

Your test and some others were added. 50 authors lost AC.

By the way, it is possible to store N bools to solve this problem, and AC solutions with memory about 200K are OK.

Edited by author 20.11.2008 13:52

Fyodor Menshikov Re: Weak tests [3] // Problem 1494. Monobilliards 22 Nov 2008 00:49

Sandro (USU) wrote 20 November 2008 12:06

By the way, it is possible to store N bools to solve this problem, and AC solutions with memory about 200K are OK.

Is it _really_ possible to solve this problem using only N _booleans_? I mean it seems good enough to keep all necessary information, but not enough to search the information _fast_, so solutions with N booleans should probably get TL on a good test.

Could you send such solution to e-mail, associated with my account?

Fyodor Menshikov Re: Weak tests // Problem 1494. Monobilliards 22 Nov 2008 01:04

Test generated by the following program may be hard for some solutions storing only booleans.

const
   n = 100000;
var
   low, high : integer;
begin
   assert(n mod 3 = 1);
   low := n div 3 + 1;
   high := low + 2;
   writeln(n);
   writeln(low);
   low := low - 1;
   while low > 0 do begin
      writeln(high);
      writeln(high - 1);
      high := high + 2;
      writeln(low);
      low := low - 1;
   end;
end.

Edited by author 22.11.2008 01:05

Fyodor Menshikov Re: Weak tests [1] // Problem 1494. Monobilliards 22 Nov 2008 02:30

I can imagine a correct solution using N bits packed in integers. It uses O(N^2) time but with very good constant. But I think that solution using N booleans cannot pass TL.

Sandro (USU) Re: Weak tests // Problem 1494. Monobilliards 22 Nov 2008 03:07

And you are right! Thank you. I added your test and some other tests of similar structure, and 85 authors got TL and WA.

Den It is really? // Problem 1494. Monobilliards 4 Aug 2008 15:55

Farhad Ghasemi why WA on 7 ??!?! here is my code [1] // Problem 1494. Monobilliards 30 Jun 2008 19:40

Alexey What is the algo? I have almost O(n). But TLE#16. Help, please. (-) [11] // Problem 1494. Monobilliards 2 Nov 2006 18:48

Samsonov Alex [USU] Re: What is the algo? I have almost O(n). But TLE#16. Help, please. (-) [9] // Problem 1494. Monobilliards 3 Nov 2006 18:13

What do you mean by "ALMOST O(n)"?

Alexey Re: What is the algo? I have almost O(n). But TLE#16. Help, please. (-) [8] // Problem 1494. Monobilliards 4 Nov 2006 11:19

I mean that I have a loop to read data. It is O(n).
But in it I have a loop for checking.
In most cases it is about some iterations,
but there are some tests that make my algo O(n^2).
How to make it faster?

svr Re: What is the algo? I have almost O(n). But TLE#16. Help, please. (-) [7] // Problem 1494. Monobilliards 4 Nov 2006 12:34

I think that next sketch is O(N)

Let x[1]...x[N]- revisor sequence

k- Current number of an element of x under consideration

NN- number of balls in billiard pocket now +last ball x[k]

xx[]- aray of balls now in billiard pocket for moment k + last ball x[k]

S-number of operations

//Begining

k=1 ;NN=x[1]; xx[]=[1..NN];//array assignment- x[1]- operations

S:=x[1];

// Loop

aa:

j:=0;

while (x[k+j]==xx[NN-j]) j++ //revisor takes seguental balls

//from Billiard pocket;S:=S+j;

k=k+j- next position

if (k==N+1) "«Not a proof». END

NN=NN-j; //number of balls in pocket after Session of taking; S:=S+1;

m1=xx[k1]- next ball after timeout

If (m1<=m) -"Cheater"//meet number smallet than taken

xx[NN+1..NN+m1-m]:=[m+1..m1];// new sequence in billiard pocket

//under ptevious rest S+=m1-m operations

NN:=NN+m1-m;//renew S=S+1;

goto aa

//Loop

The resume: S<=2*N -- O(N)

Alexey Re: What is the algo? I have almost O(n). But TLE#16. Help, please. (-) [5] // Problem 1494. Monobilliards 4 Nov 2006 16:06

I have such algo:
a[0..100000]. a[i] means minimal number that can be taken
after i not to be a cheater.
during reading datas i have to cerrect the massive.
but there are some tests that
I must correct more than one element. I takes me a loop.
So, TLE.

P. S. I don't understand your algo )
Can you mail me "_magistr.90@mail.ru" ?
We can speak Russian (or Ukrainian ;) )

UdSU: Ajtkulov, Kotegov, Saitov Re: What is the algo? I have almost O(n). But TLE#16. Help, please. (-) [4] // Problem 1494. Monobilliards 5 Nov 2006 11:16

It's just a stack modelling. You should suppose player not to be a cheater. Then he just puts balls into the pocket one by one: 1, 2, 3... until the last ball is the next ball to be checked. So, this ball should be removed. And so on. When the process is finished just check if the pocket is empty.

svr Re: What is the algo? I have almost O(n). But TLE#16. Help, please. (-) [3] // Problem 1494. Monobilliards 5 Nov 2006 12:13

Yes! And in my algoritnm xx[]- stac;
NN- it's capacity;

Alexey Re: What is the algo? I have almost O(n). But TLE#16. Help, please. (-) [2] // Problem 1494. Monobilliards 5 Nov 2006 15:12

ANW, TLE#14 (((

Olzhas2dy Re: What is the algo? I have almost O(n). But TLE#16. Help, please. (-) [1] // Problem 1494. Monobilliards 30 Jun 2007 16:05

For everyone who has TLE, use priority_queue. It is probably not the best solution, but it takes up only few lines.

Dusan Re: What is the algo? I have almost O(n). But TLE#16. Help, please. (-) // Problem 1494. Monobilliards 13 May 2008 03:50

can you give me link where I can find algo or code for priority_queue?

Neizvestnii Re: What is the algo? I have almost O(n). But TLE#16. Help, please. (-) // Problem 1494. Monobilliards 30 Jun 2007 18:28

to svr: I don't know 2 things in you algoritm:
->m1=xx[k1]- next ball after timeout
What is k1?
->If (m1<=m) -"Cheater"//meet number smallet than taken
What is m?

Please help me

Брэнд O(n^2) // Problem 1494. Monobilliards 21 Mar 2008 19:28

O(N^2) works! Time - 0.984 seconds)))

Edited by author 21.03.2008 19:29

Aleksandar94 Help... I dont get it... // Problem 1494. Monobilliards 9 May 2008 03:55

Lion ? [3] // Problem 1494. Monobilliards 4 Nov 2006 11:24

Nebojsa Wa #7 [2] // Problem 1494. Monobilliards 2 May 2008 03:00

Can somebody gives me some tests

Nebojsa Re: Wa #7 [1] // Problem 1494. Monobilliards 5 May 2008 02:56

Help please!
Here is my code
#include <iostream>
using namespace std;

long a[100000];
long b[100000];
long c[100000];

int main()
{
    long n,k=1,s,s1,l;

    cin>>n;
    if(n==2)
    {
    cout<<"Not a proof";
    goto tu;
}
for(int i=n;i>0;i--)
{
        cin>>a[i];
        }

        while(a[k]<a[k+1])
        {
                          b[k]=a[k];
                          l=k;
                          k++;
                          }
                    if(n-k==0)
                    {
    cout<<"Not a proof";
    goto tu;
}

                    for(int i=k;i<=n;i++)
                    {
                            c[i]=a[i];
                            }
      n-=k;
   for(int i=k;i<=n;i++)
   {
           if(c[i]>=c[i+1])
           {
    cout<<"Cheater";
    goto tu;
}}
     cout<<"Not a proof";
     tu: ;
     system("pause");
     return 0;
     }

Edited by author 05.05.2008 02:57

Nebojsa Re: Wa #7 // Problem 1494. Monobilliards 5 May 2008 03:00

And this my other solution
#include <iostream>
using namespace std;
long a[1000000];
long u[1000000];
int main()
{
    long n,b=0;
    cin>>n;
    int s=0,br=0,s1=0,x=1;

    for(int i=1;i<=n;i++)
    {
            cin>>a[i];
            }
             for(int i=n;i>0;i--)
            { b=a[i];
                u[x]=b;
                x++;
                    }
            for(int i=1;i<=n;i++)
            {
                  s1=u[i+1]-u[i];
                    if((u[i]<u[i+1]) && (s1>1))br++;
                    }
                    for(int i=1;i<=n;i++)
                    {s=u[i+1]-u[i];
                    if(s>1)
                    {
                    if(s==a[br]) br--;
                    else
                    {cout<<"Cheater";
                    goto tu;
                    }
                    if(s<0 && br==0)
                    {cout<<"Cheater";
                    goto tu;
                    }
                    }
                    }
                    cout<<"Not a proof";

                    tu :;
                    system("pause");
                    return 0;
                    }

Edited by author 05.05.2008 03:00

¥@§@® Δδδ@$☺√ I have new one. WA # 14. // Problem 1494. Monobilliards 17 Dec 2007 02:30

LIKIA HELP!!! WA on test #6 // Problem 1494. Monobilliards 16 Aug 2007 21:13

H*J_ZHUJ WA 7 // Problem 1494. Monobilliards 3 Nov 2006 17:01

lamot wa#7 // Problem 1494. Monobilliards 15 Oct 2006 18:48

Discussion of Problem 1494. Monobilliards