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
Can some give a rough idea on how to still reduce space ( if at all we can ).
Thanks.
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?
p.s. why does n^2 gets time limit ?
I used usual polynomial hash,
H(S) = (s1 + s2 * p + ... + sn * pn - 1) modQ, where
p = 31, Q = 263 - 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.
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;