Всем привет!
Завтрашний раунд пройдёт в нестандартное время на наборе задач Московской олимпиады школьников по программированию для 6-9 классов. Пусть вас не смущает возраст участников, московская методическая комиссия постаралась отобрать для олимпиады разнообразные и интересные задачи. Непосредственной разработкой задач занимались halin.george, Sehnsucht, cdkrot, vintage_Vlad_Makeev и ch_egor.
Спасибо MikeMirzayanov за прекрасную платформу Codeforces для проведения контестов и замечательную платформу Polygon, значительно упрощающую подготовку задач.
Спасибо V--o_o--V за сокращение официальных легенд задач и перевод их на английский язык.
Надеемся увидеть вас завтра в таблице результатов!
UPD1: Разбалловка 500-1250-1250-1500-2000-2750
UPD2: Наши разработчики очень устали после вчерашней олимпиады, поэтому разбор будет позже. Приносим извинения.
Победители:
Division 2:
Division 1 + 2 (unofficial):
UPD3: Разбор
What a lovely weekend heading up!! :)
Codeforces round 466 and Codechef lunchtime on Saturday and Codeforces round 467 on Sunday.
Atcoder grand contest too on Saturday!
Will there be any editorials published for this contest ?
Perfect time for Chinese users!
Round #464 and #466 are both perfect time for Chinese users!
Hope the problems statements are as short as the announcement ! :D
this is such a bad time for egypt as it will be 11:30 AM
why don't you make it at the usual time as every other contest
We need intersection between official contest and round because we want to prevent cheating from onsite participants.
And if all contests was at the usual time, some programmers from various countries will never be able to participate
Like the case of AtCoder
How we could cheat? Access to Internet was blocked. BTW. On every Moscow olympiad (including RosOI regionals) lksh.ru and ejudge.ru weren't blocked. Is it some LKSH PR? UPD. Oh, I understood. We could cheat on Codeforces.
In my time zone, the usual contest is 10:30 or 11:30 am. This one is 4:30 am. You have no right to complain.
You do understand why there aren't so many American algorithmists on this site, right? :))
Because they have a different motivation system?
no it's cause 70% of contest are at 3 am
Редкая ситуация, когда я могу поставить плюс анонсу авансом :D
Chinese users will like it because of the time of the contest~
Why it's not on the main page?
UPD Now it's ok
What a short announcement it is!
Does anyone feel like when there are lot of Chinese participants the round gets harder, because Chinese coders are good?
Out of curiosity, are you trying to get the lowest contribution on codeforces right now? This is a seriously legit question, nobody has > -100 contribution by accident. :))
I think you mean < -100 :P
How many tasks will be given?
What's the main character of this contest?
You mean "character"?
Perfect time setting for Chinese. Especially just after I finished my Chinese New Year :)
its so early for hunting but take care Rengar may attend the round :D
I thought I am the only Jhin-main in Codeforces :D
I was a little bit nervous about next contest after completing DIV2 465. but codeforces is always best... 2 in a row...
Unique contests have unique times... :)) 100% this contest will be great like others. I hope questions judges have no problems and contest have beautifull questions ;)
I hope many hacks and high rating
I hope this contest will make me green !
wish you luck, mate :) all the best.
The time of this contest is very friendly for China :)
UPD: But seems like the connections is not so friendly,since I'm "500 ERROR" for at least 5 times during the contest... Am I the only one?
Is this round a replacement of VK Cup Qualification round?
Scoring distribution?
Scoring distribution?
Is this round rated?
They didn't announce if it rated or not but they explained the unusual time is for preventing onsite participants from cheating in codeforces so i guess its rated
I guess it's Rated , See the Calendar !!
Scoring distribution and Number of problems yet not revealed! Time left to start of contest is 2 hours
I found this on a market
Would it be rated for contestants having rating below 1900? As the rating has not been mentioned in the announcement.
Did you read the blog title? Since it mentions Div.2 so yes, it should be rated for Div.2
That doesn't imply about the rating I guess. Since in usual announcement or invitation mail it is clearly mentioned about the same, so I doubted. Anyway thanks :)
This time isn't so bad for south asian I think ...
Here in the U.S. ;)
We usually have about 8 hours for sleep every day. There isn't 8 hours worth of codeforces contests everyday though. This is my 4 am proof for why codeforces > sleep.
Codeforces contests needs clear mind so you should sleep good to participate. but how can you do both?
Sometimes I can't do both so I guess it just depends on the night (tonight was not one of the good nights lol).
scoring distribution?
Currently something is going not so right with the Codeforces server...
Let's hope that everything will be okay soon...
on again ... off again ...
Like a switch. Not totally unreachable, but performing a task (hacking/submitting) is more struggling than usual...
It's so frustrating in the last 15 minutes.
I couldn't submit a solution Because it showed "The requested url couldn't be retrieved" everytime.
10 minutes with Internal Server Error :(
lots of times I tried to submit. The server was not responding. Even commenting on this gets a server error.
?
I can't do anything during the last 30 minutes, including hacking or entering the standing page. All of the web pages in Codeforces were not available, I can't even enter my profile page. Hope it is not rated due to fairness, even if CF predictor told me that my rating will ascend a little.
I even hadn't submited a problem that should have to be Accepted:(
Hack page not loading :/
There's issue with hacking page.
UPD: Round should be declared as Semi-rated so that it is fair enough for all.
they can extend the round for like 10 minutes and it will be better than making it unrated .
I don't guess 10 minutes can compensate.
I agree. The hacking page wasted me at least 20 min....
Even server was not responding when trying to submit.
Please Don't make the contest unrated.
Lol bro lol.
Will you make this round unrated?
How to solve D ?
Initialize l = -1e9 and r = 1e9. Whenever one of two conditions(bi equal 1 and previous 4 values equal 0 or bi equal 0 and previous 4 values equal 1) occur then update l or r accordingly. This works because for other conditions array values will lie between l and r.
Code
The problem ensures that a solution exist, so each time that b[i]!=b[i-1] you just update l and r for a valid value that make this change
What's wrong with my code? Why TL? http://mirror.codeforces.com/contest/940/submission/35642398
if n < k, then you set n to 0 and 0 % k is always 0 so it repeats infinitely.
Try this case:
4 100 100 100
И так весь контест
Последние 20 минут только. Похоже у них что-то упало и до сих пор с хрипом дышит.
I only have a solution for E when n % c <= sqrt(n). What's the full solution?
How to solve E?
I'm not sure, but i think that is only good divide in subarrays of size multiple of c. So, u can do a dinamic programming using your current position and take the min in go to the pos+1 or pos+c(in this case you have to know the minimun element fast)
If that's correct then you can just use sparse tables to quickly grab the min in O(1) and then just do the dp right?
Yes, you just have to know this min fast enough, has many ways to do this :D
A pre process of costs is welcome too
I used multiset to get min in log(n) time. Much easier than implementing sparse tables or segment tree.
But if there are many multiples of c in the range <n in that case would you check every possible solutions of dividing the subarrays in multiples of c?If yes how would you do proceed then?
Is ever better dividing by c. Try to understand the why, but is not too hard
Denote the smallest value of first i as d[i]. Then consider the length of the last partition part(the one include the last element). If its length is smaller than c, then it's not better than d[i — 1] + a[i]. If its length is larger than or equal to c, then it's always better to cut another one at i — c. And in this case, the value is not better than d[i — c] + sum(i — c + 1 to i) — min(i — c + 1 to i). So in a word, we just have to calculate min(d[i — c] + sum(i — c + 1 to i) — min(i — c + 1 to i), d[i — 1] + a[i]).
Usual 'connection was reset' and 'try again' later when the contest time will be over.
Is it rated? :-p
Here for upvotes?
use Mo's algorithm with modification
SO complexity is O(n^(5/3) logn)??
Or can be logn be got rid of?
Use another sqrt decomposition to know the mex value, you do updates in constant time and query in
, since you make only N queries the overall complexity becomes 
This is the only time "is it rated ?" question didn't get down voted.
cf server dropped harder than hardbass beat in my headphones
To be fair, Those who their rating change is positive , their contest should be rated, and the other the contest for them should be unrated. :p
Semi-rated contest time?
Really?! not even extending?
To be fair, Those who their rating change is positive their contest should be rated, and the other's contest should be unrated .
Come on. Would those last 10 min change that much?
On the last minute , I was about submitting a solution for the problem D .. But, I hope that the contest is rated for those who their rating change is positive !
I spent time trying to submit, I had only a small change to make in one more solution... Perhaps my score would be better had the server been working ok...
I coudn't submit my solution to D, but, probably, it would have failed.
fast system testing but during the contest codeforces broke down much ):
Couldn't submit D in the last 3-4 mins. Server issues...
I did not understand problem (statement) E. Can someone please explain it to me?
statement is quite confusing, but examples are highly helpful to get into it
I approached this by dynamic programming.
Let's make dpi the minimum value of the i-length prefix of the array a (1-indexed).
Also, let's define sum(a, b) and min(a, b), respectively, the total values and the minimum values in the continuous segment [a, b] in the array.
Initially dpi = 0.
If i < c, dpi = dpi - 1 + ai.
Otherwise, dpi = min(dpi - 1 + ai, dpi - c + sum(i - c + 1, i) - min(i - c + 1, i)).
The sum and min-value of each segment can be calculated in O(logN) time complexity by RMQ-based approaches (I myself used segment trees).
Since range is a sliding window you can do it using multi set.
Thanks for the suggestion :D
After drafting out the approach, I coded without thinking, and make every calculation as formal (and also universal) as possible :D didn't even think about sliding window actually ;)
How do you prove ur soln works?
First of all, as the problem itself provides, we can see that no matter how we chose the segments, it will always turn out to be equivalent with a distribution, such as each element is either in a size-1 segment or a size-c segment.
Secondly, if we merge two adjacent size-c segments together, there may be two cases:
If the minimum values of both segments (before merging) are also the 2 minimums of the merged one, the total value of these 2 * c element will remain the same.
Otherwise, when one minimum value of one value is higher than an arbitrary element in the other segment (which is not the minimum of that), the 2 minimums now will have the total value lower than that when the segments were separated, therefore, increasing the total value.
In conclusion, there is no point in merging any adjacent size-c segments.
Therefore, during the DP process, each element has (at most) two choices: to stand in a size-1 segment, or in a size-c segment with c - 1 elements standing before it (provided there are enough elements).
I think you probably meant
Oops, a fatal mistake while typing. Thank you! :D
If I didn't get fst on C, I would be purple......so sad
If this round would be rated :/
You will be purple. https://cf-predictor-frontend.herokuapp.com/roundResults.jsp
There were glitches in server, but only for short time. I don't think for that round should be unrated. Well, it was first time I submitted all four correctly. I hope, it is rated.
In the last few minutes of the round submission page was not loading properly. So I could not submit the solution of the third one. Bad luck that the code I was goind to submit for C at last minute was correct indeed. Happened with anyone else??
Me too. My code for problem C was accepted the first time I submitted after system testing was over, and I was not able to submit that code during the last 5 minutes of the contest.
Had around 3 mins to submit the D which I had corrected. Still couldn't submit it. And it turned out to be correct
Same with my D :")
why isn't there any announcement whether it is rated or not ?
It is not easy to take a decision for headquarters.. The fate of 3377 participiants depends on them :)
can someone please help me! my submission for C (on ideone)
submission of codeforces is going runtime error on case 26!!! why?? can someone tell
the case is
7 5000
qqqqqqq
it works properly on ideone and other places!! i feel its unfair because i could not find anything wrong! please help me, atleast prove me wrong so that i can sleep in peace! thank you!
I think with k > n, you are trying to access out-of-range element.
"for(ll i=0;i<k;i++) ans+=s[i];"
You have UB (if k > n) in lines 28-29
thanks a lot!! EternalFire and StarCuriosity guess im still a poor coder!
When I handle 'same number' case in D it fails for some reason. Help me to understand why.
AC: http://mirror.codeforces.com/contest/940/submission/35644516
WA: http://mirror.codeforces.com/contest/940/submission/35645618
diff: http://www.mergely.com/sf680QoI/
I understand that I can only decrease
rand increasel, but anyway how is it possible that i got WA with those additional checks...You code is very long. I am not sure what was wrong.
Here is my code the main part without input just 5 lines, see if it will help to understand why your code works or not.
http://mirror.codeforces.com/contest/940/submission/35630470
This will not help. If you add all the required logic for
b[i] == b[i - 1]just for fun it would help.halin.george, Sehnsucht, vintage_Vlad_Makeev, cdkrot, vintage_Vlad_Makeev, ch_egor
can you guys give me full input of test 6 for D?
We encountered a ddos-attack, which affected the round. I'm investigating the impact. If the impact is not fatal, then the round should be rated. Currently I'm sticking to the decision to leave the round rated.
I apologize to the participants who encountered difficulties in submitting solutions. Sorry about it.
I think that it was ok. I had some difficulties but not the end of the world. It should be rated. :)
I also think so, because the complexities were, but for a minute trying to solve a task, I solved it. Sorry for my english =)
Everyone was affected, so it should be rated I think. Tho I didnt participate
The server difficulties didn't impact so much on the ranklist. I think it should be rated, but the rest depends on you! :)
I agree, but I don't remember when was the last normal round(without lags and server crashings) =(
I'm surprised. For me almost all rounds in 2018 happen without server-side issues. At least I didn't notice them, no notifications from monitoring systems and no massive comments about such cases from users. Can you clarify issues? BTW, I see that you didn't take part much in recent contests.
At the end I faced some difficulties when I tried to submit D. But the impact is not too much to make it unrated. It should be rated.
it should be rateddd
It should be rated
it should be pi rated
It should be rated
Hello, MikeMirzayanov. Can you explain the compiler issue? Thanks in advance.
In fact,most of us had solved the problem we can before the impact,because this round is a little easier.Therefore,it's ok to be rated.
Would you please exam the register system?I can not receive the Email confirmation by anyway.MikeMirzayanov
D U D O S E R
Consider the plea of participants who managed to solve the problem towards the end of the contest and were not able to submit it because of the issue.
I was also facing the issue while submitting solution for problem C, 30 mins before the end but luckily I was able to submit it. 5 mins before the end, I managed to solve problem D and due to the server crashes I couldn't submit it. :/
Not enough to make it unrated.
New way to improve rating: If you're having a bad contest, ddos the site and hope for unrated.
Woh! It was a great contest! All problems were interesting to solve! :D
i don't know why i wa http://mirror.codeforces.com/contest/940/submission/35646284 who can give me the data?
check diagnostics in the wrong answer test case "Diagnostics detected issues [cpp.clang++-diagnose]: p71.cpp:57:4: runtime error: index -1 out of bounds for type 'int [200005]' SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior p71.cpp:57:4 in"
thank you!i have found my bug!
Same code compiled with C++11 and C++14 made different result.
C++11: Code1 Compilation error (which cost more than 10 minutes)
C++14: Code2 Accepted
Can someone tell me why?
I see you get an Compilation time limit exceeded. I think you should contact MikeMirzayanov for more information.
Bug in g++: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68203
Got that, thanks. What a coincidence!
It seems to me that some of inputs for D were generated in invalid way
AC: http://mirror.codeforces.com/contest/940/submission/35649388
If I add some validation into my submission it fails
RE: http://mirror.codeforces.com/contest/940/submission/35649409
diff: http://www.mergely.com/diBmBHT8/
What I'm validating:
condition
ai, ai - 1, ai - 2, ai - 3, ai - 4 > rmust be false if current number inb'is 1 and previous 4 numbers were also 1.condition
ai, ai - 1, ai - 2, ai - 3, ai - 4 < lmust be false if current number inb'is 0 and previous 4 numbers were also 0.If at some point we have to increase
ror decreaselto hold conditions above, it means that there is a conflict, because on each step we calculate lowest possiblerand highest possiblel.Is there a mistake in my logic?
halin.george, Sehnsucht, vintage_Vlad_Makeev, cdkrot, vintage_Vlad_Makeev, ch_egor guys take a look
I think you should not use the Deque. For this example:
The answer should be:
I mean, this sequence is not in descending order or ascending order.
And my solution gives that answer :)
as i understand you didn't get the point of queue. it is used to maintain min/max of all current subarrays. check https://www.geeksforgeeks.org/sliding-window-maximum-maximum-of-all-subarrays-of-size-k/
The process of the program, I think the size of deque may less than 4 on test 6. I think you can simpliy use the Array instead of deque.
size doesn't matter. please check AC link and try to understand sliding window approach
I am a user of C++. I can't handle your problem about Java. :)
sliding window is not related to language. check C++ variant on geekforces, link is above
I don't think that this problem is a sliding window problem. The problem is to get some inflection points for array b, I think. It means that we should get the point which the point is 0, the previous point is 1 and vise versa.
sliding window can be used to maintain min/max of subarrays. don't reply
Although it does help but since window size is just 5 linear checking is good enough
agree. i did it just for practice. did you check the main point of my post btw? everyone ignores me =(
Your assertions are incorrect. You should swap minDec and maxDec in your assertions. Also it is generally a nice idea to take a good look at your code before posting something like "The tests are incorrect" and so on, because in 99% of the cases they are correct. I'm sure you could've found this mistake by yourself.
i finally got it. thanks. sorry xD
my mistake was wrong transformation of boolean expression.
correct one looks like that:
!(ai > r && ai - 1 > r)=>(ai <= r || ai - 1 <= r)and my mistake was to transform it as:
!(ai > r && ai - 1 > r)=>(ai <= r && ai - 1 <= r)99% is actually an underestimation I'd say.
Why rating changes is so long? I spent a lot of time and efforts to solve my first problems. I wrote it in train, where is no Wi-Fi or 4G, I submited it as soon as train arrived at rare stations. I so tired, I need to know what happens with my rating. So this silent expectation makes me crazy!
you may try this site which can predict your rate changes https://cf-predictor-frontend.herokuapp.com/
Oh, thank you so much! You save a lot of my nerves!
Why be so nervous, your rating will guaranteed not go up or down?
Can someone please help me with this on problem E?
I seem to be getting random REs with the same code. All of these codes I just declare some random variables, or increasing array size, so they're practically the same.
My latest submission.
size of vector dp seem to be the problem
Thank you very much :((( I'm still not getting why it doesn't RE on some tests, but fixed and ACed now
That was a silly mistake
Nice solution and excellent code style! I learned a lot from your code.
And may you share some problems similar to this, or some good dp problems? I want some practice. Thanks !!
Thanks :D I tend to get lost in my own code, so I have to keep it simple.
You can search for problems by tags in the problemset. Here
The dp in problem 940E is actually the well-known "house robber" problem. You can try looking it up.
My dp in E just missed a line
f[i] = max(f[i-1], f[i]);and I got WA.I actually ignored the truth that f[i] can be equal to f[i-1] which means the i position number is split as a single partition.
Very sad to review the mistake because I lost a quite good opportunity to increase my rating.
Can you please explain your logic behind E. I cannot understand the dp part. Thanks
Hi ch_egor!
I'd like to thank you for the exciting competition, but I think there's something wrong with the test case #5 of problem D.
I used
assert(minl <= maxl); assert(minr <= maxr); assert(minl <= maxr);to make sure my answer was legal. However, I got an RE at test case #5, see 35641797.Then I tried to delete those asserts and submitted it 35642151 again, but I was surprised. Not only it passed pretest, but also the system test. I didn't made any change except removing these asserts!
It's good for me that test case #5 is not large (n = 95) and I can copy it all. Finally I found out why.
Here's array a and b at i = 8 (counted from 0):
i:...4 5 6 7 8 ...
a:...94 96 91 98 95 ...
b:...0 0 0 0 0 ...
Now that b[8] = 0 and b[7] = 0, we have r >= 91.
And Here's array a and b at i = 38 (counted from 0):
i:...34 35 36 37 38 ...
a:...62 68 63 64 69 ...
b:...1 1 1 1 0 ...
Now that b[38] = 0 and b[37] = 1, we have r < 62.
So,
assert(minr <= maxr)was false and returned an RE. And in fact, this case has no solution.Oops I made a serious mistake, sorry for the disturbance.
EDIT: Yet there still exist problems I cannot explain :(
Hmmmm... I'm still confused. Here's another problem of this test case.
i:...29 30 31 32 33 34...
a:...-75 -80 -78 -74 -76 62...
b:...1 1 1 1 1 0
Since b[33] = 1, we have r >= -80 (otherwise b[33] should be 0 according to condition 1).
Since b[34] = 0, we have r < -80. Strange.
It's midnight here so I'll work on it tomorrow. By the way, forget about my solutions above, they make no sense. (I wonder how could they pass the system test...unbelievable)
Are you talking about test case #5?
Then you might have miscounted indexes in b: <23 times 0><15 times 1>...
Also while proving/disproving, dont forget it can continue to be 1 without even satifying condition 1
b[i] = b[i-1]partYes, dantrag is right, I happened to delete something in my input file. It's my fault.
Now everything makes sense. I get an AC after bug fixed. 35665198
Thank you guys anyway.
Why still no rating update yet?
Ratings got updated, nevermind
Is this unrated ????
Is this unrated ???
we want rating we want rating we want rating ho ho ho ho
yaayayayaya thank you MikeMirzayanov
By when will we have the editorial?
Can any one explain problem E to me, or explain the sample case in the statement please ?
The value of some array b of length k is the sum of its elements except for the [k/c] smallest. For example, the value of the array [3, 1, 6, 5, 2] with c = 2 is 3 + 6 + 5 = 14.
length of array, k = 5
c = 2
[k/c] = 2
so , sum of array without considering "2" smallest values is 3+6+5 = 14
PS: comment has been edited
what about 1 ? it should be 3+1+6+5 no ?
two smallest -> 1 and 2
second smallest -> 2
Thank you it makes sense now ^^.
Hi, Need help to understand it. The example is perfect that we should not consider [k/c] numbers. The second, third and fourth examples doesn't make sense to me.
Input : 12 10 1 1 10 10 10 10 10 10 9 10 10 10
Here, [k/c] is 2. In the second example one of the optimal partitions is [1, 1], [10, 10, 10, 10, 10, 10, 9, 10, 10, 10] with the values 2 and 90 respectively.
How did this happen. We shouldn't consider the least 2 right? so, 1 ,1 in shouldn't be considered right?
Please help, I'm unable to understand the examples
floor(k/c) numbers need to be considered. So in second example in partitions - [1 1] floor(2/10) i.e. 0 smallest numbers are removed. [10 10 10 10 10 10 9 10 10 10] floor(10/10) i.e. 1 smallest number is removed from sum. So total sum is 9*10+1+1 = 92
Can anyone explain, why this output is bad? 35663077 I think is it ok.
Check i = 88 i: 84 85 86 87 88 a: 33 34 34 42 32 b: 1 1 1 1 0
b[88] = 0 so r < 32. Be careful with '<' and '<=' 。
How to solve F?
Check the Editorial.
Greedy, brute force, implementation all in one!
What happened for the people get stared? I didn't realize what I have done bad and I found I was unrated(* Acvator). Also, I found many of the tops are unrated(By get a star in front of it). What happened? Can anybody explain this? http://mirror.codeforces.com/contest/940/standings Many of the Black name's grade are canceled.
The top rated guys are Div 1 contestants and this contest was for div2 partcipants that's why they are not rated.
Что-то в голос с отсылочки к Папичу.
Выйдет ли разбор или нужно самим в интернете искать олимпиаду с её разбором? ch_egor можете пожалуйста уточнить.
Сейчас есть разбор только на русском, как только переведем на английский, выложим на Codeforces.
UPD: Перевели
TY for short statements