ch_egor's blog

By ch_egor, 4 years ago, translation,

Hello everybody!

Tomorrow in unusual time round will be held using problemset of Moscow programming competition for school students of grades from 6 to 9. Do not be tricked by the age range of the participants, Moscow jury always tries its best to select interesting problems of various topics. Problems were developed by halin.george, Sehnsucht, cdkrot, vintage_Vlad_Makeev and ch_egor.

Thanks to MikeMirzayanov for an excellent platform Codeforces for contests and an excellent platform Polygon, which greatly simplifies the preparation of contests.

Thanks to V--o_o--V for reducing the statements and translating them into english.

Hope to see you in the standings!

UPD1: Scoring 500-1250-1250-1500-2000-2750

UPD2: Our problemsetters are tired because of olympiad, so editorial will be a bit later. We apologize for it.

Winners:

Division 2:

Division 1 + 2 (unofficial):

UPD3: Editorial

• +253

 » 4 years ago, # |   +29 What a lovely weekend heading up!! :)Codeforces round 466 and Codechef lunchtime on Saturday and Codeforces round 467 on Sunday.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +3 Atcoder grand contest too on Saturday!
•  » » » 4 years ago, # ^ |   0 And USACO!
•  » » 4 years ago, # ^ |   +29 Will there be any editorials published for this contest ?
 » 4 years ago, # |   +42 Perfect time for Chinese users!
•  » » 4 years ago, # ^ | ← Rev. 2 →   -29 Round #464 and #466 are both perfect time for Chinese users!
 » 4 years ago, # | ← Rev. 2 →   +19 Hope the problems statements are as short as the announcement ! :D
 » 4 years ago, # |   -99 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
•  » » 4 years ago, # ^ |   +77 We need intersection between official contest and round because we want to prevent cheating from onsite participants.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +45 And if all contests was at the usual time, some programmers from various countries will never be able to participate
•  » » » » 4 years ago, # ^ |   +1 Like the case of AtCoder
•  » » » 4 years ago, # ^ | ← Rev. 2 →   -10 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.
•  » » 4 years ago, # ^ |   +25 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.
•  » » 4 years ago, # ^ |   +22 You do understand why there aren't so many American algorithmists on this site, right? :))
•  » » » 4 years ago, # ^ |   0 Because they have a different motivation system?
•  » » » » 4 years ago, # ^ |   0 no it's cause 70% of contest are at 3 am
 » 4 years ago, # |   +8 Chinese users will like it because of the time of the contest~
 » 4 years ago, # | ← Rev. 2 →   +13 Why it's not on the main page?UPD Now it's ok
 » 4 years ago, # |   -20 What a short announcement it is!
 » 4 years ago, # |   -19 Does anyone feel like when there are lot of Chinese participants the round gets harder, because Chinese coders are good?
•  » » 4 years ago, # ^ |   +4 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. :))
•  » » » 4 years ago, # ^ |   +5 I think you mean < -100 :P
 » 4 years ago, # |   +9 How many tasks will be given?
 » 4 years ago, # | ← Rev. 2 →   0 What's the main character of this contest?
•  » » 4 years ago, # ^ |   0 You mean "character"?
 » 4 years ago, # |   +15 Perfect time setting for Chinese. Especially just after I finished my Chinese New Year :)
•  » » 4 years ago, # ^ |   +10 its so early for hunting but take care Rengar may attend the round :D
•  » » 4 years ago, # ^ |   +2 I thought I am the only Jhin-main in Codeforces :D
 » 4 years ago, # | ← Rev. 2 →   0 I was a little bit nervous about next contest after completing DIV2 465. but codeforces is always best... 2 in a row...
 » 4 years ago, # |   0 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 ;)
 » 4 years ago, # |   -24 I hope many hacks and high rating
 » 4 years ago, # |   +24 I hope this contest will make me green !
•  » » 4 years ago, # ^ |   +3 wish you luck, mate :) all the best.
 » 4 years ago, # | ← Rev. 2 →   +4 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?
 » 4 years ago, # | ← Rev. 2 →   -6 Is this round a replacement of VK Cup Qualification round?
 » 4 years ago, # |   +3 Scoring distribution?
 » 4 years ago, # |   0 Is this round rated?
•  » » 4 years ago, # ^ |   +3 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
•  » » 4 years ago, # ^ |   +4 I guess it's Rated , See the Calendar !!
 » 4 years ago, # | ← Rev. 2 →   +7 Scoring distribution and Number of problems yet not revealed! Time left to start of contest is 2 hours
 » 4 years ago, # |   +48 I found this on a market
 » 4 years ago, # | ← Rev. 2 →   -20 Would it be rated for contestants having rating below 1900? As the rating has not been mentioned in the announcement.
•  » » 4 years ago, # ^ |   +7 Did you read the blog title? Since it mentions Div.2 so yes, it should be rated for Div.2
•  » » » 4 years ago, # ^ |   -18 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 :)
 » 4 years ago, # |   +9 This time isn't so bad for south asian I think ...
 » 4 years ago, # |   +10 Here in the U.S. ;)
•  » » 4 years ago, # ^ |   +1 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.
•  » » » 4 years ago, # ^ |   +3 Codeforces contests needs clear mind so you should sleep good to participate. but how can you do both?
•  » » » » 4 years ago, # ^ |   0 Sometimes I can't do both so I guess it just depends on the night (tonight was not one of the good nights lol).
•  » » 4 years ago, # ^ |   +1
 » 4 years ago, # |   +2 scoring distribution?
 » 4 years ago, # |   0 It's on my mind since yesterday the contest is today at 12:00Today 11:15 on codeforces solving some problems while waiting for the contest to begin..At 11:44 accidentally see:"Contest is running Codeforces Round #466 (Div. 2)"The contest is at 11:30 not 12:00 -_____-
 » 4 years ago, # |   +11 Currently something is going not so right with the Codeforces server...Let's hope that everything will be okay soon...
•  » » 4 years ago, # ^ |   +12 on again ... off again ...
•  » » » 4 years ago, # ^ |   +15 Like a switch. Not totally unreachable, but performing a task (hacking/submitting) is more struggling than usual...
•  » » » » 4 years ago, # ^ |   +19 It's so frustrating in the last 15 minutes.
•  » » » » » 4 years ago, # ^ |   +1 I couldn't submit a solution Because it showed "The requested url couldn't be retrieved" everytime.
 » 4 years ago, # |   +22 10 minutes with Internal Server Error :(
•  » » 4 years ago, # ^ |   0 lots of times I tried to submit. The server was not responding. Even commenting on this gets a server error. ?
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +3 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.
•  » » 4 years ago, # ^ |   0 I even hadn't submited a problem that should have to be Accepted:(
 » 4 years ago, # |   +14 Hack page not loading :/
 » 4 years ago, # | ← Rev. 5 →   +21 There's issue with hacking page.UPD: Round should be declared as Semi-rated so that it is fair enough for all.
•  » » 4 years ago, # ^ |   +10 they can extend the round for like 10 minutes and it will be better than making it unrated .
•  » » » 4 years ago, # ^ |   +12 I don't guess 10 minutes can compensate.
•  » » 4 years ago, # ^ |   +3 I agree. The hacking page wasted me at least 20 min....
•  » » » 4 years ago, # ^ |   +19 Even server was not responding when trying to submit.
 » 4 years ago, # |   +51 Please Don't make the contest unrated.
•  » » 4 years ago, # ^ |   0 Lol bro lol.
 » 4 years ago, # |   +26 Will you make this round unrated?
 » 4 years ago, # |   0 How to solve D ?
•  » » 4 years ago, # ^ |   +1 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
•  » » 4 years ago, # ^ |   +7 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
 » 4 years ago, # |   0 What's wrong with my code? Why TL? http://codeforces.com/contest/940/submission/35642398
•  » » 4 years ago, # ^ | ← Rev. 2 →   +1 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
•  » » » 4 years ago, # ^ |   0 Thank you so much
 » 4 years ago, # |   +3 I only have a solution for E when n % c <= sqrt(n). What's the full solution?
 » 4 years ago, # |   0 How to solve E?
•  » » 4 years ago, # ^ |   +3 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)
•  » » » 4 years ago, # ^ |   0 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?
•  » » » » 4 years ago, # ^ |   +3 Yes, you just have to know this min fast enough, has many ways to do this :DA pre process of costs is welcome too
•  » » » » » 4 years ago, # ^ |   +11 I used multiset to get min in log(n) time. Much easier than implementing sparse tables or segment tree.
•  » » » 4 years ago, # ^ |   0 But if there are many multiples of c in the range
•  » » » » 4 years ago, # ^ |   0 Is ever better dividing by c. Try to understand the why, but is not too hard
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +1 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]).
 » 4 years ago, # |   0 Usual 'connection was reset' and 'try again' later when the contest time will be over.
 » 4 years ago, # |   +24 Is it rated? :-p
•  » » 4 years ago, # ^ |   0 How to Solve F?
•  » » 4 years ago, # ^ |   +1 Here for upvotes?
•  » » » 4 years ago, # ^ |   +11 use Mo's algorithm with modification
•  » » » » 4 years ago, # ^ |   +5 SO complexity is O(n^(5/3) logn)?? Or can be logn be got rid of?
•  » » » » » 4 years ago, # ^ | ← Rev. 3 →   +9 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
•  » » 4 years ago, # ^ |   +3 This is the only time "is it rated ?" question didn't get down voted.
 » 4 years ago, # |   0 cf server dropped harder than hardbass beat in my headphones
 » 4 years ago, # |   0 Semi-rated contest time?
 » 4 years ago, # |   -35 make this contest unrated. In may case, the codeforces server keeps reseting up to 30min.
 » 4 years ago, # |   0 Really?! not even extending?
 » 4 years ago, # |   -9 To be fair, Those who their rating change is positive their contest should be rated, and the other's contest should be unrated .
 » 4 years ago, # |   +34 Come on. Would those last 10 min change that much?
•  » » 4 years ago, # ^ |   0 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 !
•  » » 4 years ago, # ^ |   +6 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...
•  » » 4 years ago, # ^ |   0 I coudn't submit my solution to D, but, probably, it would have failed.
•  » » 4 years ago, # ^ |   0 what if someone had the solution at 1.50hrs and his solution was ac solution... instead of getting +20 he/she will get -90 ... 10 mins won't change that much...sure... -_-
 » 4 years ago, # |   +4 fast system testing but during the contest codeforces broke down much ):
 » 4 years ago, # |   +3 Couldn't submit D in the last 3-4 mins. Server issues...
 » 4 years ago, # | ← Rev. 2 →   0 I did not understand problem (statement) E. Can someone please explain it to me?
•  » » 4 years ago, # ^ |   +5 statement is quite confusing, but examples are highly helpful to get into it
•  » » 4 years ago, # ^ | ← Rev. 5 →   +7 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).
•  » » » 4 years ago, # ^ |   +6 Since range is a sliding window you can do it using multi set.
•  » » » » 4 years ago, # ^ |   +5 Thanks for the suggestion :DAfter 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 ;)
•  » » » 4 years ago, # ^ |   +2 How do you prove ur soln works?
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 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).
•  » » » 4 years ago, # ^ |   +6 I think you probably meant
•  » » » » 4 years ago, # ^ |   0 Oops, a fatal mistake while typing. Thank you! :D
 » 4 years ago, # |   +3 If I didn't get fst on C, I would be purple......so sad
•  » » 4 years ago, # ^ |   +3 If this round would be rated :/
•  » » 4 years ago, # ^ |   +5 You will be purple. https://cf-predictor-frontend.herokuapp.com/roundResults.jsp
 » 4 years ago, # |   +15 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.
 » 4 years ago, # |   +1 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??
•  » » 4 years ago, # ^ |   +1 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.
•  » » 4 years ago, # ^ |   +1 Had around 3 mins to submit the D which I had corrected. Still couldn't submit it. And it turned out to be correct
•  » » 4 years ago, # ^ |   0 Same with my D :")
 » 4 years ago, # | ← Rev. 2 →   +24 why isn't there any announcement whether it is rated or not ?
•  » » 4 years ago, # ^ |   0 It is not easy to take a decision for headquarters.. The fate of 3377 participiants depends on them :)
 » 4 years ago, # |   0 I faced some problems submitting my solution during contest... was it because of some problem with codeforces ??
 » 4 years ago, # |   0 can someone please help me! my submission for C (on ideone)submission of codeforces is going runtime error on case 26!!! why?? can someone tellthe case is7 5000qqqqqqqit 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!
•  » » 4 years ago, # ^ |   +16 I think with k > n, you are trying to access out-of-range element."for(ll i=0;i
•  » » 4 years ago, # ^ | ← Rev. 2 →   +12 You have UB (if k > n) in lines 28-29 for(ll i=0;i
•  » » 4 years ago, # ^ |   +8 thanks a lot!! Snowfl4ke and StarCuriosity guess im still a poor coder!
 » 4 years ago, # | ← Rev. 2 →   0 When I handle 'same number' case in D it fails for some reason. Help me to understand why.AC: http://codeforces.com/contest/940/submission/35644516WA: http://codeforces.com/contest/940/submission/35645618diff: http://www.mergely.com/sf680QoI/I understand that I can only decrease r and increase l, but anyway how is it possible that i got WA with those additional checks...
•  » » 4 years ago, # ^ |   0 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://codeforces.com/contest/940/submission/35630470
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 This will not help. If you add all the required logic for b[i] == b[i - 1] just for fun it would help.
•  » » 4 years ago, # ^ |   0 can you guys give me full input of test 6 for D?
 » 4 years ago, # |   +183 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.
•  » » 4 years ago, # ^ |   +60 I think that it was ok. I had some difficulties but not the end of the world. It should be rated. :)
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +10 I also think so, because the complexities were, but for a minute trying to solve a task, I solved it. Sorry for my english =)
•  » » 4 years ago, # ^ |   0 Everyone was affected, so it should be rated I think. Tho I didnt participate
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 The server difficulties didn't impact so much on the ranklist. I think it should be rated, but the rest depends on you! :)
•  » » 4 years ago, # ^ |   -71 I agree, but I don't remember when was the last normal round(without lags and server crashings) =(
•  » » » 4 years ago, # ^ |   +145 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.
•  » » 4 years ago, # ^ |   0 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.
•  » » 4 years ago, # ^ |   0 it should be rateddd
•  » » 4 years ago, # ^ |   +1 It should be rated
•  » » » 4 years ago, # ^ |   +17 it should be pi rated
•  » » 4 years ago, # ^ |   +9 It should be rated
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Hello, MikeMirzayanov. Can you explain the compiler issue? Thanks in advance.
•  » » 4 years ago, # ^ |   0 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.
•  » » 4 years ago, # ^ |   0 Would you please exam the register system?I can not receive the Email confirmation by anyway.MikeMirzayanov
•  » » 4 years ago, # ^ |   0
•  » » 4 years ago, # ^ |   0 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. :/
•  » » » 4 years ago, # ^ |   0 Not enough to make it unrated.
•  » » 4 years ago, # ^ |   +7 New way to improve rating: If you're having a bad contest, ddos the site and hope for unrated.
 » 4 years ago, # |   +24 Woh! It was a great contest! All problems were interesting to solve! :D
 » 4 years ago, # | ← Rev. 2 →   0 i don't know why i wa http://codeforces.com/contest/940/submission/35646284 who can give me the data?
•  » » 4 years ago, # ^ |   0 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"
•  » » » 4 years ago, # ^ |   0 thank you!i have found my bug!
 » 4 years ago, # |   0 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 AcceptedCan someone tell me why?
•  » » 4 years ago, # ^ |   0 I see you get an Compilation time limit exceeded. I think you should contact MikeMirzayanov for more information.
•  » » » 4 years ago, # ^ |   +14
•  » » » » 4 years ago, # ^ |   +3 Got that, thanks. What a coincidence!
 » 4 years ago, # | ← Rev. 7 →   -21 It seems to me that some of inputs for D were generated in invalid way AC: http://codeforces.com/contest/940/submission/35649388If I add some validation into my submission it failsRE: http://codeforces.com/contest/940/submission/35649409What I'm validating:condition ai, ai - 1, ai - 2, ai - 3, ai - 4 > r must be false if current number in b' is 1 and previous 4 numbers were also 1.condition ai, ai - 1, ai - 2, ai - 3, ai - 4 < l must be false if current number in b' is 0 and previous 4 numbers were also 0. If at some point we have to increase r or decrease l to hold conditions above, it means that there is a conflict, because on each step we calculate lowest possible r and highest possible l. Is there a mistake in my logic?halin.george, Sehnsucht, vintage_Vlad_Makeev, cdkrot, vintage_Vlad_Makeev, ch_egor guys take a look
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 I think you should not use the Deque. For this example: 10 1 2 3 4 -1 -2 -3 -4 -5 -6 0000111110 The answer should be: 5 -7 I mean, this sequence is not in descending order or ascending order.
•  » » » 4 years ago, # ^ | ← Rev. 3 →   0 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/
•  » » » » 4 years ago, # ^ |   0 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.
•  » » » » » 4 years ago, # ^ |   0 size doesn't matter. please check AC link and try to understand sliding window approach
•  » » » » 4 years ago, # ^ |   0 I am a user of C++. I can't handle your problem about Java. :)
•  » » » » » 4 years ago, # ^ |   0 sliding window is not related to language. check C++ variant on geekforces, link is above
•  » » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » » » 4 years ago, # ^ |   0 sliding window can be used to maintain min/max of subarrays. don't reply
•  » » » » » » » » 4 years ago, # ^ |   0 Although it does help but since window size is just 5 linear checking is good enough
•  » » » » » » » » » 4 years ago, # ^ |   0 agree. i did it just for practice. did you check the main point of my post btw? everyone ignores me =(
•  » » 4 years ago, # ^ | ← Rev. 2 →   +60 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.
•  » » » 4 years ago, # ^ | ← Rev. 12 →   0 i finally got it. thanks. sorry xDmy 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)
•  » » » 4 years ago, # ^ |   +5 99% is actually an underestimation I'd say.
 » 4 years ago, # |   +10 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!
•  » » 4 years ago, # ^ |   +4 you may try this site which can predict your rate changes https://cf-predictor-frontend.herokuapp.com/
•  » » » 4 years ago, # ^ |   0 Oh, thank you so much! You save a lot of my nerves!
•  » » 4 years ago, # ^ |   0 Same feeling here, it is going to be fine. :)
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Why be so nervous, your rating will guaranteed not go up or down?
 » 4 years ago, # |   +3 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.
•  » » 4 years ago, # ^ |   +1 size of vector dp seem to be the problem
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 Thank you very much :((( I'm still not getting why it doesn't RE on some tests, but fixed and ACed nowThat was a silly mistake
•  » » » » 4 years ago, # ^ |   +3 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 !!
•  » » » » » 4 years ago, # ^ |   0 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. HereThe dp in problem 940E is actually the well-known "house robber" problem. You can try looking it up.
 » 4 years ago, # | ← Rev. 2 →   0 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.
•  » » 4 years ago, # ^ |   0 Can you please explain your logic behind E. I cannot understand the dp part. Thanks
 » 4 years ago, # | ← Rev. 8 →   0 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.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +3 Oops I made a serious mistake, sorry for the disturbance.EDIT: Yet there still exist problems I cannot explain :(
•  » » » 4 years ago, # ^ | ← Rev. 6 →   0 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 0Since 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)
•  » » » » 4 years ago, # ^ |   +8 Are you talking about test case #5?Then you might have miscounted indexes in b: <23 times 0><15 times 1>...
•  » » » » 4 years ago, # ^ |   +5 Since b[33] = 1, we have r >= -80 Also while proving/disproving, dont forget it can continue to be 1 without even satifying condition 1b[i] = b[i-1] part
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 Yes, 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. 35665198Thank you guys anyway.
 » 4 years ago, # |   +3 Why still no rating update yet?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Ratings got updated, nevermind
 » 4 years ago, # |   +3 Is this unrated ???
 » 4 years ago, # |   0 ****Ratings please!****
 » 4 years ago, # |   +7 we want rating we want rating we want rating ho ho ho ho
•  » » 4 years ago, # ^ |   -13 yaayayayaya thank you MikeMirzayanov
 » 4 years ago, # |   0 By when will we have the editorial?
 » 4 years ago, # |   +1 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.
•  » » 4 years ago, # ^ | ← Rev. 4 →   0 length of array, k = 5c = 2[k/c] = 2so , sum of array without considering "2" smallest values is 3+6+5 = 14PS: comment has been edited
•  » » » 4 years ago, # ^ |   +1 what about 1 ? it should be 3+1+6+5 no ?
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 two smallest -> 1 and 2second smallest -> 2
•  » » » » » 4 years ago, # ^ |   0 Thank you it makes sense now ^^.
•  » » » » » » 4 years ago, # ^ | ← Rev. 3 →   0 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 10Here, [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
•  » » » » » » » 4 years ago, # ^ |   0 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
•  » » » » » » » » 4 years ago, # ^ |   0 Thanks a lot. Understood now!
 » 4 years ago, # | ← Rev. 3 →   0 Can anyone explain, why this output is bad? 35663077 I think is it ok.
•  » » 4 years ago, # ^ |   0 Check i = 88 i: 84 85 86 87 88 a: 33 34 34 42 32 b: 1 1 1 1 0b[88] = 0 so r < 32. Be careful with '<' and '<=' 。
•  » » » 4 years ago, # ^ |   0 Thanks. I dont understand how works min_element (it works on half-open interval), so there was the problem. Then it AC me. 35678006.
 » 4 years ago, # |   0 How to solve F?
•  » » 4 years ago, # ^ |   +5 Check the Editorial.
 » 4 years ago, # |   0 Greedy, brute force, implementation all in one!
 » 4 years ago, # |   0 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://codeforces.com/contest/940/standings Many of the Black name's grade are canceled.
•  » » 4 years ago, # ^ |   +3 The top rated guys are Div 1 contestants and this contest was for div2 partcipants that's why they are not rated.
 » 4 years ago, # |   -6 Please publish the editorial ASAP !
 » 4 years ago, # |   0 Problem difficulty of this contest : A
 » 4 years ago, # | ← Rev. 2 →   0 What's the approach for problem C?
 » 4 years ago, # |   0 TY for short statements