Hi all,

Today we would like to invite you to take part in round #86. Round is prepared by Andrew Malevich (aka Kenny_HORROR) and me, Taras Brzezinsky. We are students of Belarusian State University. We would like to thank MikeMirzayanov , it4.kp , RAD , Gerald и Fefer_Ivan for helping and advice in preparing round and Delinur for translation.

While participating, you will get known with boy Peter and remember some of his school days to help him to solve some problems

The points for the problems in Div 1 & 2 will be: 500-1000-1500-2000-2500.

**New service "Virtual contest" will be unavailable during the round due to possible instability.**

Good luck to everyone!

**UPD**

The contest is finished, ratings are updated.

Congrats to winners:

DIV1:

1) hos.lyric

2) KADR

3) yaro

4) tourist

5) Egor

DIV2:

2) kelvinlau

3) igor_kz

4) lxn

5) StelZ40494

Editorial is currently available, the whole problem set analysis will be added in few hours.

"You may resubmit the solution at any moment, but it may reduce your score. It happens if resubmission is successful (i.e. passes

all the pretests+ previous hacking attempts). In this case, the previous successful attempt would be considered as a reason for penalty"So has this rule changed?

All prime numbers of the form 4n+1 qualify for it(and 2 also) .But I was getting Time limit exceeded!!!

bool is_prime(int n)

{ for(int c=2;c*c<=n;c++) if(n%c==0) return false; return true; }

If yes, it's slower than calculate alls numbers prime, no?

vector<int> list_prims;

void precompute(int n)

{

list_prims.push_back(2);

for(int c=3;c<=n;c+=2)

{

for(int c2=0;c2<list_prims.size();c2++)

if(c%list_prims[c2]==0) goto end;

list_prims.push_back(c);

end:;

}

}

I don't know if what I said it's stupid, I have not calculated the complexity of the second fonction. But more we have a big number n, more there is space between two number prime...

Ps: I have Time limit Error for the pretest 4, so it seems to not be the good solution.

I guess my opinion right now can't be really true, as I did really bad :-/

So, a sentence with just one word which is a verb should give "NO", isn't ? I'm missing something from statement. Could some one point out that. Thanks.

•"... :(Hope, proper steps will be taken :)

What do you think about Prob C DIV1. ?

I see some people hard-coded primes in the intervals of 10^6 or so .

My AC code from practice http://ideone.com/hMmmm

Edit: hmmmm :p

^{L}) am I right? Maybe it can be implemented in another way?Can some give a rough idea on how to still reduce space ( if at all we can ).

Thanks.

Easy looking problemscausedlots of problems.Case (heh) in point:

Test: #10, time: 4510 ms., memory: 96140 KB, exit code: 0, checker exit code: 0, verdict: OK

Input

100 152262461

Output

4281819

Answer

4281819

Test: #11, time: 4720 ms., memory: 96140 KB, exit code: 0, checker exit code: 0, verdict: OK

Input

200 299399868

Output

8110312

Answer

8110312

Test: #12, time: 5000 ms., memory: 96140 KB, exit code: 0, checker exit code: 0, verdict: TIME_LIMIT_EXCEEDED

Input

300 99050033

Output

2854733

Answer

I would not go that far but, to be honest, I haven't seen a code optimization problem in a contest in a while (meaning, there hasn't been a need to reduce the constant factor).

I did remember seeing Yarin's Sieve a while ago, but I never really had use for it - this time I googled for it and implemented it in Java. For other's benefit, here it is (my code passes if I inline the calls to isPrime(), which is a shame):

[code]

/*

* Convert Yarin's Sieve to Java... bleh :)

*/

private static final int MAXSIEVE = 300000000;

private static final int MAXSIEVEHALF = MAXSIEVE / 2;

private static final int MAXSQRT = (int) (Math.sqrt(MAXSIEVE) / 2);

private byte[] a = new byte[MAXSIEVE / 16 + 2];

private void init() {

Arrays.fill(a, (byte) 0xFF);

a[0] = (byte) 0xFE;

for (int i = 1; i < MAXSQRT; i++)

if ((a[i >> 3] & (1 << (i & 7))) != 0)

for (int j = i + i + i + 1; j < MAXSIEVEHALF; j += i + i + 1)

a[j >> 3] &= ~(1 << (j & 7));

}

private boolean isPrime(int n) {

return (a[n >> 4] & (1 << ((n >> 1) & 7))) != 0;

}

[/code]

waiting for editorial to see the non-hashing solution for Petr#.

I thought to myself..at 1:30(hh:mm) before end of contest."ahh..sieve...surely it will TLE " ......

Again at 1:00(hh:mm) ..."yeah..sieve must TLE ...the limits are very high ... "

Again at 0:30 ..." n^(1+k) must time out [0 < k < 1]" ...

But when I see AC solutions they used sieve only... :(

Just optimizing the sieve can also do the trick.

I get Time Limit on test 21 !!! and my solution is O(n^2) !!

Did anybody has this problem too?

O(NlogN) solutionp.s. why does n^2 gets time limit ?

I used usual polynomial hash,

H(S) = (s_{1}+s_{2}*p+ ... +s_{n}*p^{n - 1})modQ, wherep= 31,Q= 2^{63}- 1.~~It seems that I discovered a serious bug in Codeforces. . . . .~~

~~Submission judged with~~MLE:~~const int N = 3e8+5;~~

~~Submission judged with~~AC:~~const int N = 3e8+5;~~

~~I suppose the authors intend not to accept a solution with O(N) memory. . . . right?~~May you please explain a bit more on why the memory of a bool vector can be less than a vector of bool? Just wanna learn something.

With bool [] , 148000kb.

and with vector<bool> the memory usage shows 2700 kb.

The difference is more than 8 times.

Can u explain the memory difference please.

A sentence is either exactly one valid language word or exactly one statement.

note like this in A-Div1 , C-Div2 very important it should be in bold font. too many Div1 and Div2 coders get WA @pretest 4.

my code for problem A:

#include<iostream>

#include<math.h>

using namespace std;

int main()

{

// freopen("sam.txt","r",stdin);

int k,l,i;

cin>>k>>l;

for(i=1;;i++){

int temp=pow(k,i);

if(temp==l){

cout<<"YES"<<endl<<i-1<<endl;

return 0;

}

if(temp>l)break;

}

cout<<"NO"<<endl;

return 0;

}

long long temp=pow(k,i)+0.5;

you should have tried abs(n-floor(n)) < eps || abs(n-ceil(n)) < eps just to be sure.

but for problems like this i always follow KISS rule! Keep It Simple Stupid.

i just used this:

while(n%k==0) n/=k;