Hi everyone!
I am pleased to announce that Codeforces Round #304 (Div.2), of which I am the author, will take place today. This will be my first round, so I hope that it will be cool and interesting. Traditionally Div.1 participants can take part out of the competition.
I want to thank znirzej, Dakurels and Zlobober for help with preparing the problems, thank Delinur for translating the problems, and thank to MikeMirzayanov and all who created polygon for this great system.
I wish you all good luck!
UPD Scoring will be 500-1000-1250-1500-2250.
UPD editorial
UPD Congratulations for winners in div.2:
And in div.1:
Thank You. :)
Hope to participate officially on your next contest :)
Hope next time you arranged problems for both division . thanks .
.
Wow, polish round!
"Scoring will be announced later." Hope it's not just a minute before the contest starts.
i am new here so plz help me how does knowing the score pattern help..?
Radewoosh fought a lot in yellow but at the end he is red congrats and all the best for next rounds.
I wish all participants of Div2 to reach Div1.;)
this can never happen because rating change depends on rank of participant
An only div2 round from a red.it will be interesting.
I hope this round will be not easy like last contest
Scoring : 500-1000-1250-1500-2250. Looks like that the problems are not hard except E
and E is an easy E
It seems that Div2 contests are becoming easy!
So, let's go to div 1?
The last contest had 2 problems with score 1750 but both were very easy. Let's just wait for the problems.
the two problems were with score 1750 , and i agree with you , they were very easy .
My first contest (:
Maybe you win this contest like Bell-sama in the last contest ;)
Too many unrated participants in top 20 -_-
farnasirim has
nbadges.Who are the
nlucky coders who want to receive badges ?No badges for those who use these kinds of names for innocent variables.
This was a joke, but please here is not write a bad word.
Admin please delete this message.
sorry for my poor English.
This is not a joke, this is a screenshot. I am sorry I should have set an age guard so it wouldn't teach bad words to 2 year olds. Also your age is not elligible for receiving a badge. So stop trying too hard :/
I'm not good in English but you can understand me... There are girls from our counry or other cultural countries in this site, so such messages aren't eligible to be written here. I think you are schoolboy who doesn't know how to behave!
Dick/Sperm (although not directly written by me) are facts that women from your country have to know about sooner or later :) No, I am a schoolboy who does not understand the way you think.
The hack checker for the problem B has some problem as it gives an "Invalid Input" result for a valid input. Please check.
Did you output "\n"?
The test file must be closed with '\n'
hack checker for problem B seems to be giving invalid input,have tried multiple times
It's a little bit strange... this round seems too easy. Look at the number of accepted solution.
And look at the number of successful hacks!!!
waiting for D solutions to fail main tests... ;)
Как решать D?
Сделаем решето Эратосфена,при этом когда во 2 цикле делает isPrime[j]=false подсчитываем степень i в факторизации j (за logn) и прибавим это к счетчику простых делителей числа haveDivisors[j]. Предподсчитаем массив частичных сумм на массиве haveDivisors. Тогда ответ — это ps[b]-ps[a]
Ответ на задачу — сумма количества делителей всех чисел от b+1 до a. Собственно, алгоритм: сначала вычисляем заранее количество делителей для всех чисел, считаем частичные суммы и отвечаем на запросы за O(1)
How to solve E ?
Its a maxflow problem. Make a 2*N + 2 vertices , 2 copies of each node and 1 source and 1 sink. Now you can find out the respective edges required to make the graph (think about it a little bit, if u know max flow , else u can read about it), that part is only left. Then find the max flow from source to sink and print it.
What were all the hacks on B and D?
I got hacked in D cause I used cin cout for input. Though I am pissed, I must say, that was a clever hack!
Me too, Failed system test case because of cin cout
I'm sorry but why would cin,cout fail?
cin cout streams are slower than scanf and printf.
We have to read in about 2 million integers from the input file and write another million as output. The overhead in cin cout is just too much (will take more than 3 seconds) and thus your solution will timeout. Morever, the "endl" command to add a newline character has another overhead, it adds a newline character AND empties all buffers.
It is advisable to use scanf printf for faster input/output operation.
Try it out yourself on some local files and see which is faster
you should've used scanf and printf instead of cin and cout I guess..
For B:
5
1 1 1 1 1
result is it 10?
My code is giving me 10 as result
Yea, it's 10.
B:
D: very long input and output
Well, I hacked D's that should obviously TLE, so the maximum tests weren't included in pretests. For B, there were a lot of incorrect solutions that had Passed Pretests.
See these first timers on codeforces. /\
also i hacked 1 ppl using this test:
3
3 3 3
Many did a brute force on D and didn't pre-calculate the values .
I've made 6 hacks with following test:
10
3 3 3 3 3 3 3 3 3 3
Most solutions used
if(a[i] > 1)instead ofwhile(a[i] > 1)Also, there was a case of 3000 times of 3000, which may cause overflow on some solutions, but I haven't tried that
So weak pretest on B. And I locked it ...
Не подскажет кто-нибудь почему в B некорректный такой к примеру тест:
3000
20 20 20 20 20...
Валидатор ругался, что нет переноса в конце второй строки.
В конце нужно добавить Enter.
перевод строки в конце есть? или может лишний пробел в конце.
спасибо, в конце пробел убирал, но перевода строки не делал, очень жаль, можно было пол комнаты хакать :(
перевод строки в конце надо ставить в этом тесте
Thank you for the contest. Though I did some really really stupid mistakes.
Тот самый момент, когда написал Диница в Е, но забыл проверить равенство сумм Ai и Bi [MegoGo-Fail]
Why my hacking test case for 2nd question is showing invalid input. I simply put n 3000 and write 3000 number of value 3000.
At the end need to add Enter.
I've tried to answer queries (in problem D) by using a prefix sum table of number of prime factors of numbers. But it's not fast enough. What's an efficient way to find number of prime factors of a number (not necessarily distinct)?
I don't know, is my solution correct, but I did it in such way:
1) Let's calc the Eratosphen Sieve and take all prime divisors for every number in [1..5*10^6]
2) For each number let's divide it while we can, by all prime numbers, that we calculated.
So, it works about 2,9 sec
I believe you only need to calculate primes up to sqrt(5000000) and if a number can't be divided by any of the primes you have, it must be a prime.
P.S. My solution is the same so my submission code can be used to understand the idea. http://mirror.codeforces.com/contest/546/submission/11220118 (not sure if it's already visible but it will be soon enough).
you just need to count sum of prime factors for each number,and then answer is d[a]-d[b](it't easy to show),for this precalculation you just need sieve of eratosthenes and for each prime p and number k; while (k | d) increase d[k],k=k/d
Can you explain why my code isn't fast enough then? I think I did the same thing. My Implementation
Apart that, it is quite similar to what I wrote. I think it's the 1st problem that is making your code too slow.
Thanks for help, but I think your solution doesn't work either. Editorial's solution is O(N).
You don't need to find the number of prime factors per se in this problem or even calculate prime numbers per se.
What I did in D was to calculate for each number the lowest number that divides it (it will be a prime). You can do it with a Sieve of Eratostenes by assigning to each number the first number that divides it and ignore other divisors.
Knowing the smallest divisor for each number you can use a O(n) dynamic programming solution where:
numDivisors[i] == 1 + numDivisors[i / smallestDivisor[i] ].
You are basically dividing the number by it's smallest divisor and then adding the already calculated result for the remaining number.
Then you calculate the accumulated number of divisors from 1 to 5 000 000 and then for each query you can calculate the result by subtracting accum[a] — accum[b] since a!/b! is the same as (b+1)*(b+2)*...*a
The highest complexity of the algorithm will be the either the sieve calculation or the number of queries.
Edit: Code
it can be done with linear complexity. Described at e-maxx
You can see it in my submission : 11225962
What about E ?
Max-Flow
but how? we can move soldiers from this city only to the neighbours:) ?
You can make a flow graph with 2 * N + 2 nodes. The last 2 are dummy source and sink. You also have N original soldier nodes and N final soldier nodes.
The edges are from the source to each original node, the original soldiers on each of such nodes. Then from the original nodes you connect to the final nodes where the soldiers can move, i.e, the neighbor nodes or the same node.
Finally the final nodes are connected to the sink with capacities equal to the number of soldiers that are expected for each of the nodes in the end.
If the flow is exactly equal to the sum of the soldiers and the if the final configuration has the same number of soldiers then it's a YES and you print the flows for each of the edges between original and final.
My code
I think, to hack is not honest. These contests are a test, but not a game "how to hack other people". I really hate hacks. Sorry for bad English)
Hack at least improve your understanding of other contestant code, and also finding a bug in their program. It really helps me creating some corner test case.
How to solve D? I thought segment tree might be useful but even if I use it, it still takes a lot of time to calculate each score of numbers...
Preprocessing is the key. Just count the amount of divisors for all the numbers in range 5000000, then create an array, i-th element of it contains a sum of divisors for all the elements in range (1..n) and then use it to calculate the answer — Arr[n]-Arr[k]
I guess counting the amount of divisors for all numbers up to 5000000 can take more than 3 sec?
the array of constant amounts, i guess. Just create it during the coding process of other problems and then use it in your program.
http://mirror.codeforces.com/blog/entry/18031?#comment-229101
Answer was obviously phi(A)-phi(B) where we define phi(N) as number of all prime factors of N . (Ex- phi(12)=3 as 2*2*3). to compute phi(N) we could precompute using Sieve .
Yes, you are right. I don't need to use segment tree in this problem.
I use ios::sync and cin.tie on problem D. Am I get TLE??
I guess you'll have to wait and see?
I can't wait anymore XD. OK :)
I know how you feel! :D
My solution passed system tests. YEEEEEES! XD
i too used cout,cin!!
How to solve problem E ? I was having almost 1 hour for this problem but not able to come up with any idea.
http://mirror.codeforces.com/blog/entry/18031?#comment-229104
All problems are very interesting. Thanks to author.
How to solve problem D?
http://mirror.codeforces.com/blog/entry/18031?#comment-229101
I know some people are claiming it was too easy; but I personally like being able to actually try out a couple problems in a competition for once. Feels nice to succeed for a change!
Will cin cout give TLE on D ?? Even if the query is answered in O(1) ??
yes,cout<<endl is tooooooooo slow,also may cout<<"\n" will pass :)
Thank God...
I have
#define nline printf("\n")and I have used
nlineI just hope it passes himanshujaju I have used int arrays..
Thanks
Got TLE with cin-cout
and AC with printf-scanf
disheartened :(
i guess yes. my solution was hacked. i changed all to int's and scanf printf. if you used int, it may pass easily.
I hate those expert programmers, who got problem D right, and just to earn a few more points started to hack other people's solutions by giving large number of test cases and large values of a and b. One guy in my room was just sitting with that intention, that whenever this person locks it, I have to hack it :(
I don't see anything bad in it. For example, I knew that my solution is incorrect before end of contests and had chance to resubmit...
Why did I get a message saying I should not use %lld in problem A? Is using it bad? I ignored it since I don't know another way to do it and I passed the pretest. Could someone please explain how to read long long in c++ without using it and why I should not use it?
It depends on the OS of the checking server. If it is linux than %lld is okay, but codeforces is using windows — so the right way is %I64d
oh no, I compiled it in my linux computer typing in %l64d and it didn't work. So for future occasions I just have to declare the variables as long long (as normal) and then when using printf and scanf substitute %lld with %l64d ?
Am I going to get it wrong because of that though?
If the online-judge system is CF — then yes, you should do it like that. I don't know about other online-judges like timus, topcoder etc.
Are there 2 pretests in problem D??? REALLY??????
because each test case contains number of games!
For D, I used a sieve to find the prime numbers which worked very fast. Then, for each number in range [1;5 000 000] I calculate the number of prime divisors using only prime numbers(that I put in vector) which don't exceed sqrt(cur number). Then, partial sums. Is it the correct solution? The slow part was the one with finding the divisors/
any trick I missed?
Fast IO ?
No, this not the problem because after calculate the divisors for each number I wrote cout<<"Ready!\n";return 0; and wait for 10-20 seconds and nothing happen. I saw people that used the same idea but they only calculate the least divisor for a number and then divide it by its least divisor until reaching 1. I think we have the same complexity but in practice their solutions beat my solution...
I don't understand your solution exactly. I solved it using Legendre's formula. (Although I don't know if it worked yet)
For problem C, I got a wrong answer on Pretest 3. I don't understand what was I missing. From the problem statement, I assumed that if N is odd, then print -1. Else do the usual queue and dequeue. Did I miss anything?
n = 3 1 1 2 2 3
Start upsolving, please!
Can you please explain how these test cases are invalid for B
5 1 1 1 1 1
6 1 1 1 1 3 4
These are valid test cases. If you are talking about hacking, u need to put a newline at the end.
No. of solutions passed : A B C D E
Pretests : 3591-2894-2383-1158-180
Final : 3516-1986-1578-557-137
4 out of 5 problems made for hacks! Great div2 contest!!
У меня во время контеста сайт регулярно перестает отвечать, иногда это длится несколько секунд, иногда пол минуты и больше. Это общая проблема?
У меня тоже такое было во время контеста.
Why cout why!!
For problem D, I just replaced "
cout<<ans<<"\n" to "printf("%d\n", ans)". And it passed in 2090 ms. I had even usedios_base::sync_with_stdio(false);. Submissions : 11219308 and 11224412mine passed in 1090sec with printf and scanf
always use scanf/printf when you have to input/output greater than 10^6 numbers. Learned the lesson in hard way.
use C++11, and write cin.tie(nullptr); 11225307
The problem is that you didn't use cin.tie(NULL). http://mirror.codeforces.com/contest/546/submission/11225554
I used it and still got TLE, but AC when using scanf printf. How is this fair? The problem should be rejudged.
it is really bad feeling when problem time limits because of cin cout :(((((((
Why? You should realize that the amount of input is huge, and it's going to take a while to read it using cin. Imo, it's only your fault. Using scanf and printf saves you a very big amount of time. I've learned it when I was upsolving. The solution, which used cin, got TL. But then I used scanf and the result was 140ms out of 1000. From that moment I'm using scanf and printf.
UPD: The submissions are: 10834692 and 10834765
i already know it. but i hate cin cout from this day :D i just didn't think about it today
But cin, cout with sync_with_stdio and cin.tie(null) should get accepted too. Mine didn't. It is the setter's fault man.
cout...
Time limit on Div2 D were too strict.
I got TLE when I submitted using cin,cout(using sync_with_stdio) in C++. And I got AC when I changed it to scanf,printf.
This is not good Mr. Radewoosh. Same algorithm should get accepted inspite of input output specifications.
Strongly agree!
You must also use cout << '\n', instead of cout << endl, it is significantly faster
It worked. Thanks!
Learnt something new today. :)
My solution passed in 608 ms using Java.
Probably your algorithm can be improved.
Here's my approach: http://mirror.codeforces.com/blog/entry/18031?#comment-229101
And code: http://mirror.codeforces.com/contest/546/submission/11220819
And the test case of D question was pathetic! scanf is getting accepted whereas cin doesn't!! Who is going to guess that in the contest! Shame!
cin is getting accepted . You had to write ios_base::sync_with_stdio(0) ; cin.tie(0) ; to get AC .
I used that and even then I got TLE on test 3. I had to change to scanf and printf to get AC. This is not fair.
How much I wish , div-2 E test case
were in the pretest. This test doesn't make sense anyway either. -_-
for problem C:
#define stack queueIn standing it is showing 3 solved problem but in contest I solved 4 problems and all 4 are accepted in the problem tab. P.S I have not resubmitted problem after contest.
You solved 3 problem I see, your problem D has a TLE .
how fair is it to award 0 to both , one who spent huge amount of time coding D correctly but forgets to put one line along with cin/cout & the one who had no idea about how to solve D & gave 0 time :P ? Disheartened :P
People who use Python like me, don't care about cin or scanf. LOL!
Lol, yes.
I'm curious is it possible at all to solve it in Python?
When do we get the editorial?
already)
Click here to the editorial :)
problem D where is case? 1000000 5000000 1 5000000 1 . . .
some AC code must be TLE
got TLE on problem D just because I used endl not \n fuck this kind of problems -_-
Guys, knowledge that cins/couts are very slow on big inputs/outputs is important on contests, and in this task this was one of the problems.
I guess people do know that! Just that they do not benchmark which input is too large for cin and cout to not work! Most of the times cin inputs upto 1000000 run fine on codeforces! Anyways apart from that the problems were good!!
I wonder, was this intended from the beginning. (Specifically, did Zlobober know about this?) This does not conform to the problem authors' guidelines that large tests should be included in pretests.
It's ok that you test for large inputs in easier problems but I doubt that is appropriate for a 1500 mark problem.
Don't get me wrong, I got AC. I am just curious.
I got TLE in problem D, and I still don't understand Could anyone tell me what wrong in my code? http://mirror.codeforces.com/contest/546/submission/11221079
fast output :D
your code 11229232
Thank you!
Немного об условиях.
"Для каждой пары солдат один из них должен получить значок, коэффициент которого строго выше второго." (546B - Солдат и значки). Долго вкуривал смысл этого предложения.
"Для каждой пары солдат один из них должен получить значок, коэффициент которого строго выше второго. Для солдат не важно, какие у них значения коэффициента, требуется лишь, чтобы их коэффициенты отличались друг от друга." Создается ощущение, что коэффициенты относятся к солдату, а не к значкам. Лично меня это изрядно сбило с толку.
"Исходно они делят между собой картны некоторым образом, возможно, не равным образом." (546C - Солдат и карты). Опечатка, плюс двойное повторение слова "образом".
"...обозначающее количество игр, в которые играют солдаты." (546D - Солдат и игра с числами). Солдаты все же играют в одну игру, а не в разные.
Также огорчает немного запутанное (до того, как были сделаны исправления) условие задачи Е, стоившее мне одной попытки.
Can someone please help and tell me what is wrong with my solution for 546D?
I am getting TLE but I implemented exactly what the editorial says:
http://mirror.codeforces.com/contest/546/submission/11232282
many people has this problem.using ll inplace of int & cin or cout inplace of scanf & printf caused TLE. It's not good...
Where is the editorial ?
http://mirror.codeforces.com/blog/entry/18034
Thank you Sunnat
deleted
I think it should be 3. The numbers will be
1 2 5 6 7you're right , thank you.
Very Good Contest! Thank you.