Hello, Codeforces!
Codeforces Round 510 (Div. 2) will start at Sep/17/2018 11:05 (Moscow time). The round will be rated for Div. 2 contestants (participants with the rating below 2100). Div. 1 participants can take a part out of competition as usual.
The round will be rated for the Div. 2 participants (for everybody with rating less than 2100). The statements will be available in Russian and English languages.
This round is held on the tasks of the school stage All-Russian Olympiad of Informatics 2018/2019 year in city Saratov. The problems were prepared by awoo, fcspartakm, Neon, BledDest, Roms and vovuh. Great thanks to our coordinator cdkrot for the help with the round preparation! I also would like to thank our testers DavidDenisov, PrianishnikovaRina, Decibit and Vshining.
You will be given six problems and two hours to solve them. Scoring system will be announced traditionally closer to round start. :)
UPD: The scoring distribution is 500-1000-1500-2000-2250-2750.
UPD2: Editorial
Another wonderful time for Chinese users.
a bad time for Chinese students in fact
agree
If i'm not wrong in summer schools are closed :\
It's not summer already :)
but better than 00:35
thanks codeforce for another round.
Because this is codeforces.
Why so early?It's like choose what is more important some kind of study or cf.
Well, where is the thanks to MikeMirzayanov and polygon platform XD
A bad time for indian students :(
A bad time for Chinese student who need to study mathematics.
thank you for the back to back contest ...a contest in afternoon for Indian users after a long time ...will have to bunk class to give ....
Its very good to have variety in the hours that contests start so as everybody can find a time that fits to their standards. I hope that codeforces will continue this logic in the future as well.
For a moment I thought this was an educational round announcement
I thought it was announcement of Div.3 round.
Really?! 12:35 IRDT
Forgot to Thanks MikeMirzayanov for the wonderful codeforces and polygon platform.
Great time for Chinese CF users.
And real bad time for Bangladeshi participants.
that's sad,will you take part in this contest?
Yes. Lets hope for the best.
Wonderful time for Chinese users. So I am coming.
Hack for A.
3 1
1000 1 1
Answer 1000 1001.
You meant: "Answer
1000 1001"?P/s: Main comment edited, nevermind :D
you can simplify the problem C to this :
given a sequence of none negative numbers(n-th >= 0) get the maximum product.
so you will multiply the positive integers. then multiply the 0's and delete the last occurrence of the zeros
how to get this ?
if you have an odd number of negative numbers , convert the maximum negative number to zero , then take the absolute value for all the sequence.
could any one help me to understand the task D ? thanks in advance :)
Consider the sum of segment [i,j] less than t is equals to
prefix[i] - prefix[j-1] < t.For every
prefix[i](1<=i<=n)calculate the number ofj(0 <=j <i )which satisfyprefix[j] > prefix[i] - t, and this number is the numbers of segments which endpoint is i and satisfy sum less than t.You can use the BIT to calculate the number of
j (0<=j<i)which satisfyprefix[j]<=prefix[i]-teasily.Then what you need to calculate isi - the number of j. Sorry for my poor english.the editorial is just after contest end.
WoW!
Such Tight limit constraints in Que-3 ,making it almost impossible to pass in pypy2/python2
why TLE using dp in problem D?
For each i in [2..n] you iterate n - i times.
The number of operations is
Your solution is O(n2), that's why it gives TLE.
What is test 22 structure like on problem D?
P.S I found out the problem, try this test: 5 6 5 -5 10 -5 10
In problem C, there are no cases with only zeros and ones. This DP solution should fail: 42985876
~ B
~ N^3 (MAX_N = 1000)
~ ACCEPTED 1 SEC
~ Who can explain WHY???
42983122
this is weird !
i tried many tests to get the answer after 2s
but this is the maximum time i got on the custom test!
test case (long text)
1000 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ACB 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC 1000 ABC
:
my best : 1600ms, test : n = 1000 1 ABC, 1 ABC....
look at it :
yes, so is this the normal run time for 109 iterations ? or this code iterate less than 109 ?
it's even doesn't make any break / continue inside any loop ! it's exact O(n3)
Yes, stupid solve!
Yes, more 1e9 iterations!
So i wanted to hack him(((
Result = -100 points :)
BTW, what's the topic/idea of D ?
i want to study it and try to solve the problem, if stuck! i'll read the editorial
Solve this. It's the same problem
Nowadays computers are fast enough to run 10^9 iterations in around 1s. Look at my code which runs around N^3/6 iterations in 234ms. http://mirror.codeforces.com/contest/1042/submission/42975128
The following test case takes 2230ms on Codeforces (GNU G++14): 1000 AB and randomly appending C.
Random Cs make a worse case than 1000 strings of ABC, most probably because of branch prediction.
Here's the code with the case generated instead of being read: https://ideone.com/JRyp7j
Does CF Rating predictor gives completely wrong rating predictions for today's contest ? Because it seems to me it worked perfectly well in yesterdays contest
I'm getting the message "Ooops! Something has broken down in Codeforces" when I try to open problem C, does anyone else get this message? What's going on?
Edit: The editorial for problem C is also not loading, probably the problem's package is somehow broken.
Yes I am also facing this problem , But i can submit it through problem id .
I'm getting that too!!! What's going on?
No idea, to be honest. The package itself seems ok, I rebuilt it just to be sure, nothing got fixed. And the previous revision was created like 3-4 hours ago, something broke after that. Just wait a bit, sorry, I have no better advice for now.
It is better to put some difficult problems. This round is extremely easy for me.
Easy? Come to Codeforces Round #510 (Div. 1)!
in task E in Div 2, what is the answer on test: 1 3 1 1 2 1 3 ?