Привет, Codeforces!
В 17.09.2018 11:05 (Московское время) состоится Codeforces Round 510 (Div. 2) для участников из второго дивизиона (участников с рейтингом до 2100). Участники первого дивизиона традиционно могут участвовать вне конкурса.
Раунд будет рейтинговый для участников второго дивизиона (с рейтингом менее 2100). Условия будут доступны как на русском, так и на английском языках.
Этот раунд проводится по задачам школьного этапа Всероссийской олимпиады школьников по информатике 2018/2019 года г. Саратова. Задачи для вас готовили awoo, fcspartakm, Neon, BledDest, Roms и vovuh. Огромное спасибо нашему координатору cdkrot за помощь в подготовке раунда! Также спасибо тестерам DavidDenisov, PrianishnikovaRina, Decibit и Vshining.
Участникам будет предложено 6 задач и 2 часа на их решение. Разбалловка будет традиционно объявлена ближе к началу раунда. :)
UPD: Разбалловка 500-1000-1500-2000-2250-2750.
UPD2: Разбор
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.
В 11:05 у меня начинается пара...
Писать контестик или идти на пару?
писать контест на паре
Мдэ я ноутбук дома забыл , придётся в уме решать
Ну, я завтра кстати из-за этого контеста тоже пару пропускаю :)
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://codeforces.me/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.
Я вот помню, как на школьном этапе писал что-то уровня A+B. Человек, сдавший больше половины на таком школьном этапе, должен на области набирать 400+ с закрытыми глазами.
На школьной Д с раунда была самой сложной задачей. Часть более простых мы в раунд не взяли.
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 ?