Problem 11245

Adrian Kuegel · Post by **Adrian Kuegel** » Sun Jul 29, 2007 12:13 am

It seems there are inputs with n > 2 * 10^9
I used assert to check this; I got Accepted after I also handled n upto 2^50.

Jan · Post by **Jan** » Sun Jul 29, 2007 12:18 am

I have another question. What if p is not a prime? It seems there are no such inputs. Was it a mistake or a trick? And if it's a trick then what can I say!!!

emotional blind · Post by **emotional blind** » Sun Jul 29, 2007 8:03 am

This must not be a trick. It forces us to think about not prime also.
In onsite contest we got the sample right.. but failed to figure out the input when p=4 and waste a lot of time. and cant submit.

I don't know what about the other teams. May be lot more team faces the same problem.

MIB · Post by **MIB** » Sun Jul 29, 2007 8:35 am

My team also suffered with the same problem in the on-site contest...
I think the same input set is used in both contests (online & onsite).

In that case, I'm really surprised how 2 teams (even one team without any penalty

) managed to solve the problem in the onsite contest... with lacking of so much info

http://daffodilvarsity.edu.bd/dipc07/wrapper2.html

ardiankp · Post by **ardiankp** » Sun Jul 29, 2007 8:52 am

??? So p is prime?

emotional blind · Post by **emotional blind** » Sun Jul 29, 2007 8:54 am

yes..
two teams in onsite can solve this problem, i think this was common to them..

ardiankp · Post by **ardiankp** » Sun Jul 29, 2007 9:28 am

LOL, yesterday I spent almost 2 hours on this problem until fell down asleep....

after knowing p is prime I can figure out the way in < 30 mins :S

Robert Gerbicz · Post by **Robert Gerbicz** » Sun Jul 29, 2007 12:23 pm

Adrian Kuegel wrote:It seems there are inputs with n > 2 * 10^9
I used assert to check this; I got Accepted after I also handled n upto 2^50.

Yes, using long long int for n value instead of int I've got AC. But WHY? In the problem statement: 1<=n<=2*10^9, so they've stealen one problem solution from me on the contest.

Thanks to:

Problemsetter: Abdullah al Mahmood
Special Thanks: Derek Kisman

Jan · Post by **Jan** » Sun Jul 29, 2007 2:40 pm

I can only say, the problem setter should be more careful while writing the statement. However in the onsite contest two teams solved the problem. I have two questions..

1. How did they know p is prime?
2. How did they know n cant be fit into normal int?

shahriar_manzoor · Post by **shahriar_manzoor** » Sun Jul 29, 2007 5:41 pm

This problem unfortunately had two mistakes. One it was not mentioned that p is a prime and another one the range was not specified.

However, none of the mistakes are due to Derek Kisman or Abdullah al Mahmud. When derek wrote solutions n>2000000000 then the problem setter made it less than 2000000000. I thought I replaced the file but later I found I did not.

I placed assert() in all solution but now I find I did not do it only for problem B. I have not explanation and I have no excuse. Like my previous errors it is version conflict.

The teams who solved it onsite somehow found the error or were lucky. But they did not inform us (which is logical) about the mistake.

I am extremely sorry for the mistake. If the submissions of the onsite contest are still available I will rejudge the solutions and change the ranklist if there is any changes and if the chief judge agrees. While changing the ranklist I will follow the rules followed in 2000 World Finals (No team loses his rank for the rejudgement). But probably I will not be able to do anything about prize money

. It would have been logical that I pay the teams from my pocket but I assume that the teams won't accept that.

Shahriar Manzoor
Judging Director of the Onsite Contest

emotional blind · Post by **emotional blind** » Sun Jul 29, 2007 5:41 pm

Jan wrote: 1. How did they know p is prime?
2. How did they know n cant be fit into normal int?

I have the same questions..
Do they know magic??

emotional blind · Post by **emotional blind** » Sun Jul 29, 2007 5:45 pm

shahriar_manzoor wrote:
I am extremely sorry for the mistake. If the submissions of the onsite contest are still available I will rejudge the solutions and change the ranklist if there is any changes and if the chief judge agrees. While changing the ranklist I will follow the rules followed in 2000 World Finals (No team loses his rank for the rejudgement). But probably I will not be able to do anything about prize money . It would have been logical that I pay the teams from my pocket but I assume that the teams won't accept that.

Shahriar Manzoor
Judging Director of the Onsite Contest

What will be rejudge strategy.. I think all submissions should get WA. isn't it?

emotional blind · Post by **emotional blind** » Sun Jul 29, 2007 5:51 pm

All solution should get WA in that sense that some teams were trying to find out the solutions when p is not prime.. those ACCEPTED solutions surely do not work for non-prime p.

but this re-judgement will not recover our damage. Because when we see that some teams solve this problem and then we put a lot of our effort on this problem because we thought that the problem is solvable even for p is not prime. and waste our time without any success.

tanaeem · Post by **tanaeem** » Sun Jul 29, 2007 6:38 pm

I have solved this problem onsite.
My answer to the question follows

1. How did they know p is prime?

I didn't even know. And why p being prime necessary is not still clear to me.

2. How did they know n cant be fit into normal int?

Whenever I see there is the result will not fit in normal integer I usually replace all int by all 64 bit int. So I got acc.

But they did not inform us (which is logical) about the mistake.

If I understood there was problem like this I would have informed the judge.

Jan · Post by **Jan** » Sun Jul 29, 2007 6:43 pm

Please check your sequence for p=4.

OJ Board

Problem 11245

Problem 11245

Re: Problem 11245

hmm

Re: hmm

I have solved this onsite