### danilka.pro's blog

By danilka.pro, history, 5 years ago, translation,

Hello, Codeforces!

Today, 17th of October at 17:35 MSK Codeforces Round #377 for second division participants will take place. As usual, first division participants are able to participate out of rating.

The round problems are taken from the problemset of regional stage of the All-Russian school team programming olympiad which was taking place yesterday in Saratov. The problemset for onsite competition was invented and prepared by Mike MikeMirzayanov Mirzayanov, Ilya IlyaLos Los, Danil danilka.pro Sagunov, Vladimir vovuh Petrov and Roman Roms Glazov. We are thankful for pre-solving competition problems to many of Saratov State U teams' participants. One problem in the round will have a bit harder version than at the competition.

Nikolay KAN Kalinin and Tatyana Tatiana_S Semenova helped us preparing problems and translating for the round — thank you! Thanks to Mike MikeMirzayanov Mirzayanov for the Codeforces and Polygon systems.

There will be 6 problems and 2 and a half hours to solve them at the round. We wish you the best luck!

If you are a participant of the yesterday competition in Saratov, please, do not register for the round and do not participate in it, also do not discuss the problems before the round ends.

UPD Scoring: 500-1000-1500-2000-2000-2500

UPD2

Congratulations to the winners!

Div.2

Div.1

As soon as the time of registration to the round was a bit early, there may be some first division participants taking part in a line with a second division participants. There are not many of them, so (and due to technical problems) this will be left as is.

Due to NEERC subregionals in Saratov, rating will be updated tomorrow.

UPD3 Editorial

• +146

 » 5 years ago, # |   +9 A fibonacci number Round... 377 is 14th fibonacci number.
•  » » 5 years ago, # ^ |   +111 It's also:sum of squares of first 5 prime numbers,25-th semiprime number,7-th centered octahedral number,47-th Sophie Germain semiprime, and thousands more on oeis :)
•  » » » 5 years ago, # ^ |   0 And a whole number round as well.Bracing myself. Downvotes are coming
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   -39 Please don't comment inept things.
•  » » » » » 5 years ago, # ^ |   +35 Ejemmm... Not really...
•  » » » » » » 5 years ago, # ^ |   +17
•  » » » » » » » 5 years ago, # ^ |   0 It was floor(pi) round.
•  » » » » » » » » 5 years ago, # ^ |   +7 It was floor(pi * 100)
•  » » » » » 5 years ago, # ^ |   0 My contribution points are too high. I need to bring them down.
•  » » » » 5 years ago, # ^ |   +2 ROFL
•  » » » » 5 years ago, # ^ |   0 :D :D
•  » » 5 years ago, # ^ |   -8 is it rated!?
•  » » » 5 years ago, # ^ |   0 yes.
•  » » 5 years ago, # ^ |   0 :)
 » 5 years ago, # |   +67 In the registrants list I see a few Div. 1 participants that are registered officially (there is no "*" before their handle).Here's an example.
•  » » 5 years ago, # ^ |   +48 I think they weren't in div1 when they registered for the contest (before yesterday's rating changes) :D
•  » » » 5 years ago, # ^ |   +8 I wonder if their ratings would change today :P
•  » » 5 years ago, # ^ |   +4 Daniar LOL
•  » » 5 years ago, # ^ | ← Rev. 2 →   +19 Oh, wait, I AM SUPERSTAR NOW
•  » » » 5 years ago, # ^ |   0 me too
 » 5 years ago, # |   +21 Today I will leave grey for good. ..... Or not XD
•  » » 5 years ago, # ^ |   -7 Commenting here will not help you to leave gray.Try to give focus on problem solving. That will help you to leave gray. wish you to be green :)
•  » » » 5 years ago, # ^ | ← Rev. 3 →   -12 indeed.
•  » » » » 5 years ago, # ^ |   +5 good luck Bro
•  » » » » » 5 years ago, # ^ |   0 He seems he's a green coder now ☺ congrats man
•  » » 5 years ago, # ^ |   0 mission accomplished
•  » » » 5 years ago, # ^ |   0 congrats
 » 5 years ago, # |   -49 Please shift the contest timing by 10-15 minutes..
 » 5 years ago, # |   -22 3 Rated contest in 3 days (Round 375,376 and 377 ) and (15,16,17).375-15376-16377-17.it's a record of codeforces 3days in a row reated contest and also interesting 5-5,6-6,7-7;
 » 5 years ago, # |   +8 The Graduation Year field in the application form only accepts numbers under 2010.
•  » » 5 years ago, # ^ |   +11 Fixed, thanks!
•  » » » 5 years ago, # ^ |   +6 The platform doesn't allow me select my country. Please resolve this issue. Thanks.
•  » » » » 5 years ago, # ^ |   0 Nigeria existed, why do you want to create a new Nigeria?
•  » » » » » 5 years ago, # ^ |   0 After updating my country to Nigeria (in settings > social) and clicked "Save changes", that's the dialog that appears. If Nigeria already existed, then why pop out that dialog identifying Nigeria as a new country? Then since it is identified as a new country, I go ahead and fill in its 2-letter code and click "Save", then I get "Code is already in use". How does that tally? Hope you see my point.
•  » » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 Change your country to "Нигерия"(copy this, its Nigeria in russian). It will help
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 Why there is not rating update for Techno cup round for some Div 2 users who registered late?
 » 5 years ago, # | ← Rev. 2 →   -9 Score distribution ? Expecting this time before the contest unlike previous contest.
 » 5 years ago, # | ← Rev. 2 →   0 One problem in the round will have a bit harder version than at the competition.There will be 6 problems*Grabs popcorn and get ready for a hell level Div2F.
•  » » 5 years ago, # ^ |   -13 It's not necessary problems to be from A to F, it could be dobule D (as it was before (D1), (D2)) or any other problem can be doubled
 » 5 years ago, # |   -9 Pay attention, Problems may be not sorted by difficulty.
•  » » 5 years ago, # ^ |   0 Not a problem at all. In this case, wait; the number of acceptance/pretest-passed will indicate the easier one :p :D !
 » 5 years ago, # |   +2 Let is delay 10 minute as usual :)
 » 5 years ago, # | ← Rev. 3 →   -22 The comment removed because of Codeforces rules violation
 » 5 years ago, # | ← Rev. 2 →   -19 The comment removed because of Codeforces rules violation
 » 5 years ago, # |   0 Its showing i'm an official participant in this contest !i had registered yesterday when i was still blue :pBug in CF ?
•  » » 5 years ago, # ^ |   +5
 » 5 years ago, # |   +30 he could have had a breakfast and a supper, but a dinner, or, probably what??
•  » » 5 years ago, # ^ |   0 Here the "but" refers negative.Such as: I will go anywhere but there.
•  » » 5 years ago, # ^ |   +7 Not an old issue, but there should be more efforts on translating into English statements.
 » 5 years ago, # |   0 Round is very nice !I only didn't realized that in second task case n=1 answer is always 0 :( Actually I thought it is special case and add one extra if :D You could put n>=2, that wasn't very clear.
•  » » 5 years ago, # ^ | ← Rev. 3 →   +1 Same with me , got hacked , lost around 400 points -_-Anyway problem set were good this time
 » 5 years ago, # |   +14 RIP all C submissions with initialization of ans < 2e18, and then taking minimum.
•  » » 5 years ago, # ^ |   0 How do you solve C?
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 CodeLet M = max(b, d, s)If M = 1, answer would be 0.Now I considered all 9 cases, whether he enters before B, before L, before S and leaves after B, after L, after S. For each case, find what should the exact number of meals should be, and subtract the current value of (b, d, s) and take minimum.
•  » » » » 5 years ago, # ^ |   0 Not sure if my code is correct, but i take max(b,d,s) — 1, which is the number of days of maximum full 3 meals. From there just minus the rest if the number of meals is smaller than that
•  » » » 5 years ago, # ^ |   0 Number of days is max(a, b, c), so you can calculate answer easily.
•  » » » 5 years ago, # ^ | ← Rev. 4 →   +1 take input in an arry and sort it.make 3 cases : 1. when all are equal 2. when only last 2 elements are equal 3. else and proceed. happy coding. :)
•  » » » 5 years ago, # ^ |   0 This passed pretests. Not sure if it'll pass the full tests. http://ideone.com/EgztAG
•  » » » 5 years ago, # ^ |   +10 If there are numbers b , d , sthen if mx = max(b , max(d,s)); then, answer = max(0 , mx-1-b) + max(0 , mx-1-d) + max(0, mx-1-d) :)
•  » » 5 years ago, # ^ |   0 I initialized ans=-1 :'(
 » 5 years ago, # |   0 In B, what is the answer for the following testcase?n=1, k=5 and a[1]=1
•  » » 5 years ago, # ^ |   +1 should be zero as it was mentioned arr[0] and arr[n + 1] = K
•  » » » 5 years ago, # ^ |   0 Missed that part. :(I will get a wa for handling the case n=1 separately.
•  » » 5 years ago, # ^ |   +5 Almost all Hacks for B is n=1 ! :) The answer should be 0...
 » 5 years ago, # |   0 For task C, why is 3 1 2 = 1?
•  » » 5 years ago, # ^ |   0 the extra breakfast is from the last day. you have 2 days of full 3 meals, and 1 day with only breakfast
•  » » » 5 years ago, # ^ |   0 But if you have 2 days of three full meals, won't you miss dinner twice?
•  » » » » 5 years ago, # ^ |   0 For 3 1 2 Come before breakfast today and go after breakfast on 3rd day(day after tomorrow ) ,In this way only one lunch is missed.
•  » » » » » 5 years ago, # ^ |   0 Oh, I see. Thank you!
•  » » » » 5 years ago, # ^ |   0 so it looks like this day 1 : b d s day 2 : b d s day 3 : bsum up 3b 2d 2s, so you miss dinner once
 » 5 years ago, # | ← Rev. 2 →   0 Hack case for C ?
•  » » 5 years ago, # ^ |   +1 I hacked one with 0 3 1 ans: 3
•  » » 5 years ago, # ^ |   0 0 1000000000000000000 0
•  » » 5 years ago, # ^ |   +1 n=1 , ans =0 while some people printed k-a[0].eg:- 1 10 2
 » 5 years ago, # |   0 can someone help me understanding the output of 4th sample case of problem C ?input1000000000000000000 0 1000000000000000000output999999999999999999
•  » » 5 years ago, # ^ |   +1 You can go into the sanitorium just before the supper and leave just after breakfast.. This case is similar for cases like N M N where N > M.
•  » » » 5 years ago, # ^ |   0 okay.. I guess I was moving in the wrong direction I guess.thanks for the explanation.
 » 5 years ago, # |   +6 Approach for problem E?
•  » » 5 years ago, # ^ | ← Rev. 3 →   +3 I am pretty sure greedily finding matches for the next smallest adapter works. Keep computers in a set/dictionary that you can do O(1) lookup on, and remove them when an adapter matches with them.
•  » » 5 years ago, # ^ | ← Rev. 5 →   +14 My solution goes as follows:Sort all the computers and sockets. Then, find all the pairs where socket power is the same as computer power. Because of the sorting, this can be done in O(n+m) time with two indices. (By moving an index forward when its power is smaller than the other's, and skipping if the socket/computer is already in use). Then I add adapters to all of the sockets and repeat, finding all the matches. You only need to do this around 31 times until all socket powers will become 1.My code was the 5th fastest overall.Edit: An identical solution is proposed in the editorial.
•  » » » 5 years ago, # ^ |   0 Can you prove this greedy solution please?
•  » » » » 5 years ago, # ^ | ← Rev. 3 →   +11 Sure, I'll try.Because one socket can only be used once, and a computer only requires one socket, there is no situation where we shouldn't join a socket and a computer if we can.The task description also defines that we should use as few adapters as possible. This is accomplished by checking smaller amounts of adapters (starting with 0) before trying more. It is always better to connect a socket to a computer earlier, when there are fewer adapters, than later. So a socket with a smaller power will be connected to a computer before trying a socket with more power and therefore more adapters in between.
•  » » » » » 5 years ago, # ^ |   0 Thanks a lot, I don't know why I found that hard to prove that during the contest (Maybe due to pressure).
 » 5 years ago, # |   0 How to solve C ?
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 let n=max(a,b,c)now depending on his arrival and leave time, there can be seven possiblities for number of breakfast, dinner and supper available. they are:b=n,d=n,s=n b=n,d=n,s=n-1 b=n,d=n-1,s=n b=n-1,d=n,s=n b=n,d=n-1,s=n-1 b=n-1,d=n,s=n-1 b=n-1,d=n-1,s=nfor each of these cases , find the minimum number of foods he can miss
•  » » 5 years ago, # ^ |   0 Number of days in sanatorium = max(a, b, c).Then you have 3 case: 1. max = a, it means that you came in morning, also it means that you leave morning (you miss dinner and supper in last day because it's optimal)Then easy to calculate answer = max(0, (a — b) + (a — c) — 2)The same logick for other case.Sorry for poor english.
•  » » » 5 years ago, # ^ |   0 Thank you
•  » » 5 years ago, # ^ | ← Rev. 4 →   +3 Suppose the given values are a[0], a[1], a[2]. Sort a and subtract a[0] from all the elements. Now the answer is This is because any triple b, d, s where difference of any pair is at most 1, is valid.
 » 5 years ago, # |   -10 I tried F using Bridge Tree + Euler Tour got MLEI saw people getting AC using the same ! can someone help ? here's the link to my codehttp://codeforces.com/contest/732/submission/21541116
•  » » 5 years ago, # ^ | ← Rev. 2 →   +8 Hi,I am guessing that the issue might be because of the implementation of bridge tree mentioned in my blog. It is not very memory efficient because of the global queue used. I realized that once when i got an MLE in a bridge tree problem. You can try changing it with a more memory efficient implementation. For eg, I wrote this better implementation. You can have a look at this:http://pastebin.com/c7hMLzVw Edit : Updated the blog as well.https://tanujkhattar.wordpress.com/2016/01/10/the-bridge-tree-of-a-graph/
•  » » » 5 years ago, # ^ |   +3 Yes, your blog was surely helpful !! Thanks for the update :)
 » 5 years ago, # |   +9 Problems difficulty is perfect.
 » 5 years ago, # |   0 What's the idea for solving F ?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +5 if u remove all the bridge edges, u'll get different connected forests. Choose the forest with maximum number of nodes as the center and direct all other forests towards this since there is only one way to orient the bridge edges. So choosing the largest forest will maximiize the minimum sum required.Then Do a euler tour to give the orientation by adding edges between nodes that have odd degree. Nodes having odd degree are always even.similar concept was use here : http://codeforces.com/contest/723/problem/EThe overall complexity is of the order O(n+m).
•  » » 5 years ago, # ^ | ← Rev. 2 →   +12 My idea on F.We can see that it is optimal to let every biconnected component to form a directed cycle as this won't affect it's potential on other biconnected component. So we should always try to form a cycle for every biconnected component first.Then we contract all biconnected component and this would form a tree. Now we can do binary search for answer.Every cities's ri will have at least x. As every node in tree represent a biconnected component in the graph, ri will initially be no. of cities in biconnected component i. Lets consider node u, if it's ru is more or equal to x, it should let the edge between u and its parent and direct it to u. So its parent's r value will be increased by ru. Else, the edge should direct its parent.Now dfs again and for every edge that are directed to its child, we can increase its r value.So if every ri is >= x, x can be obtained.edit : lol I failed system test because I read the problem wrongly and thought ri is the number that cities can go to city i. But the idea is still the same for the problem.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 Well I passed the system testing with a pretty simple solution. First of all we should notice that the answer of the problen is the maximum size of a bicconected component. Then to get how the edges will be directed, first you convert each bicconected component into a strongly connected one and you are left with the edges between the strongl/bi-connected components. It's simple to see that the compressed by strongly connected component s graph is a tree. So you make the component with the maximum size as a root of the tree. Then you make all edges between the components to go to their parents so that you can reach the root from each one of them. In this way you get alogN (N+M) solution.PS: I wrote an O(N+M)logN one because I used a map to easily access edges but this can be done in O(N+M) too.
•  » » 5 years ago, # ^ |   0 I am surprised that no one mentioned tarjan algorithm, I think that's the most straight forward way to solve it as you may have already a template coded.All you have to do is to find the minimum among the most compressed node in each connected component, and memorize them as roots. Initialize them as the root and reverse all the edges, there's your answer.
 » 5 years ago, # |   0 For E, why is a solution, that iterates through the number of adapters on all of the sockets at once, assigning greedily to each socket whenever a PC with the same power exists, wrong?I can't find a bug in my code so I guess it's in my approach.
•  » » 5 years ago, # ^ |   +8 When you sort pc[], you lose the ordering of the computers. There is no way to output the computers in the right order in line 3 of your output.
•  » » » 5 years ago, # ^ |   +3 Thank you so much, I'm an idiot xD
 » 5 years ago, # |   +4 Can anyone explain how to do D? Was it dp?
•  » » 5 years ago, # ^ |   +3 Binary search
•  » » » 5 years ago, # ^ |   0 Oh ok thanks!
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 Binary search. It's easy to verify if the first x days works by choosing the last test day for each exam in those x days and seeing if there are enough days to study before them.
•  » » » 5 years ago, # ^ |   0 How did you check? Did you use a priority queue?
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   +3 Just sort by latest exam day <= x, and do exams in this order.
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 I went through the first x days backwards to get the days I would take the test. Then I went through the test days forwards. If it was a test day kept track of how much time would be used for that test. If there is not enough time to prepare, l = mid and try with bigger x.
•  » » » » » 5 years ago, # ^ |   0 Can you give me your code?
•  » » » » » » 5 years ago, # ^ |   0 Not accepted yet: http://codeforces.com/contest/732/submission/21539380
•  » » 5 years ago, # ^ | ← Rev. 2 →   +1 Do a binary search over the number of days starting from day one to day XTo ace M exams you need at least M days + the required days to prepare, i.e. lower bound L = M + sum of required timesNow, to check if it's possible to do so in X days, start from the last day and do the following:tests = 0days_needed = 0if it's a day off OR we took the test already: decrement days_needed by one if they were > 0else: increment tests increment days_needed by the days you need to prepare for current subjectAfter last (which is the actually the first) day, check if tests is equal to number of subjects AND days_needed == 0
•  » » 5 years ago, # ^ |   0 You can binary search the answer. To check if a particular number N of days works, we can assume we take every test at the latest possible opportunity (within the first N days). If not all the tests can be taken in that time, or we don't have time to study for all of them (and this is pretty easy to determine), then N is too small.
 » 5 years ago, # |   0 Have any bruteforce solution of D(without binary_search).
•  » » 5 years ago, # ^ | ← Rev. 4 →   0 Here's my bit complicated approach : Iterate on the exams, and maintain count of total free days available till now, which are not assigned. When an exam comes that has not been taken, if its required days are <= count, then mark this exam as done(for now), otherwise, we have two choices, either forcibly take this exam on this day by marking some of the previously done exams as false and adding (their preparation days + 1 exam taking day) to count , or just not assign this exam for now. We will try to do the first choice if its possible by cancelling some previous assigned exams first. And also take care that any exam that we are cancelling, its next occurrence exists and is before next occurrence of our current exam, otherwise we can just wait to assign current exam on its next occurrence.To get next smallest occurences of previously done exams, i have used a set. As we are cancelling exams, we remove them from the set. Also, when assigning an exam, insert its next occurence in the set.Code
•  » » » 5 years ago, # ^ | ← Rev. 5 →   0 The same approach can be taken to linear complexity:In the binary search idea, we first guess the answer (the earliest day when we can pass). Similarly, in this approach, we guess the first day we can pass, except we guess sequentially.Suppose day D is the first day in which all subjects have appeared. Then to check if we can pass everything by day D, for each subject, we take note of its last exam date. (It can be proven that it does not hurt to take any exam late) For each day G (for guess), we check whether we can pass every exam we sit for up to that day. Specifically, the number of days required to pass every exam before a fixed day is the number of exams before the day + the number of days required to study for those exams. If we are able to pass every exam up to day D, then we output D. Otherwise, there is a certain earliest day, say D2, for which we are unable to pass every subject before that.The problem at D2 may be resolved if G increases: since we always sit for the latest possible exam, we might shift an earlier exam to after D2, hence solving the problem at D2. Specifically, for each exam we shift to after D2, we are reducing the number of days required at D2 by the number of days required to prepare for the exam + 1.Whenever D2 is no longer a problem, we can check in constant time whether D2+1 is problematic (if we maintain, for the current G, when the exam for each subject is). When D2 is G+1 (i.e. D2=G is not a problem), then it means we have found the smallest G in which we can pass all exams.Since every increment of G also takes constant time, this algorithm is linear.Submission no. 21537091. I think this is supposed to link: submission:21537091
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 That's my solution: 1) Let's create deque[m + 1] byExam, where byExam[i] contains days (in asc order) where we can pass exam number i 2) Check whether byExam[1..m] has at least one exam (otherwise it's unable to pass everything) 3) Create array exam[] where exam[i] = 0 if we don't wanna pass exam at day i, otherwise it contains exam number. At first, iterate over all exams in byExam array, poll last day for each exam and set exam[last_day] = exam_number 4) Create partial sums on exam array. ps[i] = ps[i-1] + (is_exam_at_day_i ? -exam_cost[exam[i]] : 1); We add one to ps if we are free, otherwise we spent exam_cost[exam[i]] at this day 5) Iterate over days in reversed order. 5.1) if (exam[day] == 0) just continue 5.2) if we have an exam at this day (exam[cur_day] is not 0), do the following: 5.2.1) check, whether we can try to take this exam earlier. Just check whether byExam[exam[day]] has elements. If it has, set exam[day] = 0, exam[prev_possible_day] = exam_number, otherwise print day number and exit 5.2.2) Iterate from prev_possible_day to cur_day, do ps[day] -= (1 + exam_cost[selected_exam]). If we have on any iteration ps[day] < 0, it's unable to take current exam earlier, so the answer is cur_day, print it and exit In other words, at first we choose the safest variant. Then we greedy try to pass last exam earlier.You can see my solution here: 21584671Also, the same idea is used in 722D - Generating Sets
 » 5 years ago, # | ← Rev. 2 →   +34
•  » » 5 years ago, # ^ |   0 Failed in the system test though :pBut the feeling was awesome for sure.
•  » » » 5 years ago, # ^ |   0 Yeah, it was awesome, but this feeling is gone now :(
 » 5 years ago, # |   +3 How to solve DI first verified if it can be done in n days by taking last possible day for each test then iterating in reverse from nth day to 1st day and checking if ith day had an passed exam in my solution the can we pass that exam in any previous option i used segment tree + lazy for this can someone please tell me where am i going wrong
•  » » 5 years ago, # ^ |   +5 binary search on the number of days . If you want to check if its possible to pass all exams in X days , find last occurence of each subject in [1,X] and take exam of each subject on its last occurence .
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 Tried that approach wrong on pretest 4 .. any idea what the test case was ?
•  » » » » 5 years ago, # ^ |   0 If might have started search from x where d[x]=0.
•  » » 5 years ago, # ^ |   0 Binary search!
 » 5 years ago, # |   0 This is interesting. Eveng though problem D and E worth the same amount of points, each minute problem D decrease its score by 6 points and problem E by 8 points.
 » 5 years ago, # |   +3 I wonder how to write a checker for problem F???
•  » » 5 years ago, # ^ |   0 Build the directed acyclic graph of the strongly connected components and take the minimum size of a sink connected component.
•  » » 5 years ago, # ^ |   +3 Just finding all strongly-connected components having no outcoming edges to another SCCs, and determining minimum between their sizes.
 » 5 years ago, # |   0 in problem B, when n=1 : (input) 1 3 1can i get your guessing output?i believe : 2 3why system said? : 0 1i think some mistakes in problem B description ..
•  » » 5 years ago, # ^ |   +6 Empirically Polycarp learned that the dog needs at least k walks for any two consecutive days in order to feel good. There is no 2 consecutive days here.
•  » » » 5 years ago, # ^ |   0 i cant disagree your reply !objectively i didnt understand problem fully :D thx for your reply :)
 » 5 years ago, # |   +11 system test taking alot of time.
 » 5 years ago, # | ← Rev. 4 →   +6 Solved D using binary search in contest.But I guess O(n) should work.Let extra be a variable that stores how many days we have to spare. Traverse from 1 to n.If d[i] = 0 or vis[d[i]] = 1, extra+=1,otherwise extra -= a[d[i]] and mark vis[d[i]] = 1If at some i, extra ≥ 0 and we have visited all m subjects and d[i] ≠ 0, print i. AC
•  » » 5 years ago, # ^ |   0 Nice idea!
•  » » 5 years ago, # ^ |   +1 Can you please explain what the checking function is doing ?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +13 Wouldn't it fail on sth. like this? 5 2 0 2 1 0 2 2 1 
•  » » » 5 years ago, # ^ |   0 Woops, you are right.
•  » » » 5 years ago, # ^ |   0 No it won't. Answer by above method will be 5 which is correct.Print answer only when extra  ≥  0 and you have visited all subjects. So ans is 5.
•  » » » 5 years ago, # ^ |   +3 No it doesn't. Here's AC code. Hardly 20 lines.
•  » » » » 5 years ago, # ^ | ← Rev. 4 →   +1 I think the tests are lacking:10 30 3 2 1 0 0 0 0 0 12 2 2edit: Simpler case6 20 1 2 0 0 12 2
•  » » » » » 5 years ago, # ^ |   +4 True that. Test cases were weak and thank god I went with binary search. It was anyways nice to think this way. :D
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   +3 Tests are very lucky) I have solution O(n), which working incorrect but it's AC)
•  » » » 5 years ago, # ^ |   +5 I have submitted using above method and it got [AC]. see the solution over here. http://codeforces.com/contest/732/submission/21548517
•  » » 5 years ago, # ^ |   0 i also did this but failed on test 22. do u know what is special in test 22.
•  » » 5 years ago, # ^ |   +3 you are assuming that we need to do an exam whenever it is possible to do it. But this is wrong, be cause you could save those days for some other exam which has to be completed first. I hope you understand what i said.counter testcase: 10 3 0 0 1 2 3 0 2 0 1 2 1 1 4
•  » » 5 years ago, # ^ |   0 6 2 1 0 0 0 0 2 1 1 I think the answer should be -1 in this test (your code output 6)
 » 5 years ago, # |   -30 Simplest Solution for problem 'C':public class C { public static void main(String args[]) { Scanner sc = new Scanner(System.in);  long b=sc.nextLong(); long d=sc.nextLong(); long s=sc.nextLong(); long max=Math.max(b,d); max=Math.max(max,s); long ans=0; ans+=Math.max(max-b-1,0); ans+=Math.max(max-d-1,0); ans+=Math.max(max-s-1,0); System.out.println(ans); } }
•  » » 5 years ago, # ^ |   0 check this http://ideone.com/EgztAG
•  » » » 5 years ago, # ^ |   0 Still you have used sorting there which obviously won't matter. Though both solutions are good.
 » 5 years ago, # |   +4 Why am I hacked?It gives me right answer: http://codeforces.com/contest/732/submission/21523956
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 1 3 1 
•  » » » 5 years ago, # ^ | ← Rev. 3 →   +3
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 initial value of ans can be any number :)UPD: I'm wrong sorry
•  » » 5 years ago, # ^ |   0 ans wasn't given an initial value to 0 It outputs a random number if the program didn't enter your second loop
•  » » » 5 years ago, # ^ |   +3 It would give random number in any case, because ans=random ans=random+something Output:random+my_answer But it passed pretests
•  » » » 5 years ago, # ^ |   +1 :| ans is global, so it is initially 0.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +1 I ran your code on codeforces's custom test and it is answering currect to the hack!!!
•  » » » 5 years ago, # ^ |   0 Maybe they check only the last solution (this is not my last) ?
 » 5 years ago, # |   0 my D got failed on test 22. can someone please tell what is special in test 22
 » 5 years ago, # | ← Rev. 2 →   0 C had an O(1) solution : fr(i,0,3) cin >> a[i]; sort(a,a+3); Long ans = max(0LL,(a[2] — 1 — a[1])) + max(0LL,(a[2] — 1 — a[0]));
•  » » 5 years ago, # ^ |   0 Can you explain it?
•  » » » 5 years ago, # ^ |   0 lets denote t[0], t[1] and t[2] as total number of meals of type breakfast, supper and dinner that vasily was present at the Sanatorium and a[0], a[1] and a[2] as the number of meals he ate.My ans is (t[i] — a[i]) for i from 0 to 2.I claim that For any i,j : abs(t[i] — t[j]) <= 1 (convince yourself of this) Atleast one of breakfast, supper and dinner will not be skipped at all (Since we need to find the smallest bracket when vasily was present at the Sanatorium) So atleast there will be atleast one i such that t[i] == a[i] is truei set the t values for other two meals equal to t[i]-1 and found the difference with a[i].
•  » » » » 5 years ago, # ^ |   0 I am sorry, but I don't fully understand the meaning of t[i]. Shouldn't they all be the same?I meant[0] = t[1] = t[2] = max(a[0], max(a[1], a[2]));?
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   +1 Hey, Let me explain. First, the use of sorting is to find the maximum number of days, that are possible. Suppose, If the number of dinners are maximum, then we can enter just before dinner on a day and leave just after having maximum number of dinner. This leaves the possible consumption of other meals to be Total dinner — 1. If you think carefully, you'll see that the same would be for breakfasts and supper as all the things are circular. So, if m is maximum of (supper, breakfast, lunch), assuming all to be different, this leaves maximum of m — 1 days for other two types.
 » 5 years ago, # |   +9 Hey, my submission for D is wrong but Accepted.http://codeforces.com/contest/732/submission/21545380because in this test case, 5 2 0 2 1 0 0 1 1 the answer is -1 but my program out 4.What should I do?
•  » » 5 years ago, # ^ |   0 Your program actually gives -1 on the Codeforces Custom Invocation.
•  » » » 5 years ago, # ^ |   0 Oh..., true.I beg your pardon.So, is my program right? Hmm...
 » 5 years ago, # |   0 Any idea why this fails for Div2 B ?
•  » » 5 years ago, # ^ |   0 1 10 1 
•  » » 5 years ago, # ^ |   0 Because in your template: #define rep(i,x,y) for (__typeof(x) i=x;(x<=y?i<=y:i>=y);i=(x<=y?i+1:i-1)) It also loops from reverse to start incase x > y i.e. at pos 1 and 0
•  » » 5 years ago, # ^ |   0 your rep(i,x,y) is defined in such a way that in this case it runs from 1 to n-1 i.e from 1 to 0.
•  » » » 5 years ago, # ^ |   0 kill me now
•  » » 5 years ago, # ^ |   0 would be nice to be a specialist i guess :/
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +6 You can't get -140> rating change I guess.
•  » » » » 5 years ago, # ^ |   0 why not ?
 » 5 years ago, # | ← Rev. 2 →   +2 Can anybody help me plz? for problem D, i think my program isn't working right but it was accepted by main tests! here is the code :21544206
 » 5 years ago, # |   -55 worst problem set and description ever
•  » » 5 years ago, # ^ |   -48 one of the worst i think :)
•  » » 5 years ago, # ^ |   -38 you are enjoying your right to downvote right? Downvote me then. I have nothing to do with my contribution. You better tell your friends to upvote you.
•  » » 5 years ago, # ^ |   +15 C was the worst .
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +4 I am a native English speaker and this contest is the first time I realized dinner != supper. Had to look it up to confirm. (Problem was clearly stated though)
 » 5 years ago, # |   +4 Waiting For Rating Changes...
 » 5 years ago, # |   0 rated or not ??
•  » » 5 years ago, # ^ |   0 YES
 » 5 years ago, # |   -9 rated ???
 » 5 years ago, # | ← Rev. 2 →   0 Wow, my E got TLE on the largest casehttp://codeforces.com/contest/732/submission/21540600I was using cin/cout so i tried changing to fast i/o.. was not enough...Then I went back to the original submission and only changed stl::map for stl::unordered_map and it got AC...http://codeforces.com/contest/732/submission/21548475Seems that it is true that hash table are O(1)... I thought the hidden constant would not make it actually faster... sad to learn it this way, but better for next time!
 » 5 years ago, # |   +3 Does round is Rated ?
•  » » 5 years ago, # ^ |   +2 waiting for rating changes :/
•  » » » 5 years ago, # ^ |   +2 not waiting
•  » » » » 5 years ago, # ^ |   0 Chill, I also got "Wrong answer on test 43" in Problem B.
 » 5 years ago, # |   +1 Waiting for the RATINGS!!!!
 » 5 years ago, # |   +1 was it an unrated contest? 377(div-2)
 » 5 years ago, # |   0 !!! Waiting for the rating change....
 » 5 years ago, # |   +1 Is it rated contest or NOT?
•  » » 5 years ago, # ^ | ← Rev. 4 →   0 Nobody knows..UPD: except MikeMirzayanov
•  » » » 5 years ago, # ^ |   +13 MikeMirzayanov knows
•  » » » » 5 years ago, # ^ |   0 I think he doesn't know yet :D
•  » » » 5 years ago, # ^ |   0 Stil waiting :)
•  » » » 5 years ago, # ^ |   +7 F5 key is is saying .. plz stop... but still rating is not updating
•  » » 5 years ago, # ^ |   +7 For the first time, a specialist is asking this question, and gets upvoted.
 » 5 years ago, # |   +1 round rated or not ????
 » 5 years ago, # |   0 Not specify in blogs that round is rated or not ? even round taker was not online till last 5 hours.
•  » » 5 years ago, # ^ |   -14 regular CF round is always rated. foolish like you always makes it complicated
•  » » » 5 years ago, # ^ |   0 bro, one regular CF round of div-1 was declared unrated after contest end due to some problem in test cases of one proble.
•  » » » » 5 years ago, # ^ |   0 If a regular round is declared unrated, you will surely get an announcement then during the contest
•  » » 5 years ago, # ^ |   0 "As usual, first division participants are able to participate out of rating." If they say that div1 participants are out of rating, that means div2 participants are in rating :)
 » 5 years ago, # |   0 why new rating didn'y apply yet?!!
•  » » 5 years ago, # ^ |   +5 Some people say that tests in D are too weak
 » 5 years ago, # |   0 why new rating didn't apply yet?!!
 » 5 years ago, # |   -9 why it will be unrated? I think rating will be given quickly. Plz------give the rating as quick as possible. After a long time awake for rating.
 » 5 years ago, # | ← Rev. 2 →   +19 http://codeforces.com/contest/732/submission/21540134The two codes above got accepted on problem D, but in this case 8 30 0 1 2 0 0 0 32 2 1the first one answers : -1the second one answers: 8the correct solution is -1.Am i understand wrong the problem?
•  » » 5 years ago, # ^ |   -9 if problem D data set will normal,it will be rejudge.why it will be unrated? Hopefully judge panel will be fixed soon as possible.
•  » » » 5 years ago, # ^ |   +5 if it is unrated, it'll be pretty depressing :(
•  » » » » 5 years ago, # ^ |   +3 I know how you feel
•  » » » » 5 years ago, # ^ |   0 not for me xD
•  » » » 5 years ago, # ^ |   +3 I think he wants it to be rejudged, not unrated
•  » » » » 5 years ago, # ^ |   +1 Why they not share in social what happen exactly ?
•  » » » » 5 years ago, # ^ |   -6 If you rejudge it please as soon as possoble rejudge it.otherwise give rating.
•  » » 5 years ago, # ^ |   0
 » 5 years ago, # |   -24 some people just comments for up vote(contribution)
•  » » 5 years ago, # ^ |   +7 I think you too.....
•  » » 5 years ago, # ^ |   +7 You are one of them :)
 » 5 years ago, # |   0 Is it unrated contest?????
•  » » 5 years ago, # ^ |   0 The author of this contest is not announce it is unrated.So everybody waiting for their annouce.
•  » » 5 years ago, # ^ |   +1 8 30 0 1 2 0 0 0 32 2 1this test case gives different answers for different solutions. but the correct answer is -1
•  » » 5 years ago, # ^ |   +5 Due to NEERC subregionals in Saratov, rating will be updated tomorrow.
•  » » » 5 years ago, # ^ |   0 how did you came to know that ? is it confirmed? why they hadn't posted this? and last, what is relation between both(neerc and cf rting)?
•  » » » » 5 years ago, # ^ |   0 The blog text was updated
•  » » » » » 5 years ago, # ^ |   0 oh ! sorry
 » 5 years ago, # |   0 Maybe data set for problem D is weak.. Accepted output for the following test is -1. 16 3 0 0 0 1 2 3 0 0 0 0 0 0 0 0 0 1 3 3 3 But many accepted solutions are giving other outputs.
 » 5 years ago, # |   -8 Updating rates is very slow. About 3 hours have passed since the end of the contest and the rates are not updated yet.
 » 5 years ago, # |   +5 Due to NEERC subregionals in Saratov, rating will be updated tomorrow.
 » 5 years ago, # |   0 Can any body tell me why i took TLE in problem D :\ 21538484 it is n log n
•  » » 5 years ago, # ^ |   0 21538484 is a "compilation errored" code and it's on problem 732Eyours is : 21538383 :)and I'm kinda sure that the problem is your binary search.try to return your function when l==r.and in the last line of function I guess it should be bs(mid+1, r);I didn't read the whole code so I might be mistaken.
•  » » 5 years ago, # ^ |   0 I think it's better to implement binary search like this BS f(n) is a boolian function.
 » 5 years ago, # | ← Rev. 2 →   0 How to solve E? I see some greedy solutions but don't know how they work correctly. :/
 » 5 years ago, # |   +3 After the round was over i was going through the solutions of some of the people to problem D and found one of the solution inspite of being wrong is accepted. Solution number 21543232 is wrong. For the test case 10 3 2 2 2 2 2 2 2 2 2 2 1 1 1 The solution gives the answer as 6 but the answer should be -1. Sadly the test cases are not strong at all.
 » 5 years ago, # | ← Rev. 2 →   +4 I think that it is not fair to get a TLE in Problem D using Java , and an Accepted using C++14 with the same code.
 » 5 years ago, # |   0 Will it be rated for the 3-4 div1 participant that were considered as official participants ?I was trying F thinking i am an unofficial participant instead of trying E, making it rated for us (atleast for me) won't be a fair !
•  » » 5 years ago, # ^ |   +11 why they're not fixing your bug? really unfair for you
•  » » » 5 years ago, # ^ |   +5 I posted about it !! lets see if it gets resolved.
 » 5 years ago, # |   +22 i suggest that MikeMirzayanov should give every contestant +50 for nothing , thanks
 » 5 years ago, # |   +5 I think Codeforce should re-judge problem D. And if you do,please include the test case below:10 30 0 1 2 3 2 0 0 1 21 1 4Just a slight modification of first test case.
 » 5 years ago, # |   +1 Question. Problem B. _ if n=1 , Haven't I to satisfy the dog? I guessed, when I have input 1 10 1, I should walk 9 to satisfy the condition (to make total walk 10), but jury's answer is 0 1 Please let me know why..
•  » » 5 years ago, # ^ |   0 Read the statement: You can assume that on the day before the first day and on the day after the n-th day Polycarp will go for a walk with Cormen exactly k times. That means: 10 times on the day before and 10 times on the day after
•  » » » 5 years ago, # ^ |   0 Thank you for nice answer!
•  » » 5 years ago, # ^ | ← Rev. 2 →   +6 He says in the statement that: "You can assume that on the day before the first day and on the day after the n-th day Polycarp will go for a walk with Cormen exactly k times."Basically when N = 1, you can assume that the K times condition has already been satisfied so you don't really need to do any extra walk.I missed that during the contest too. Got a WA on test 43 and literally removed the part of my code that dealt with the n = 1 condition and got AC. Lol pretty frustrating, but it happens :P
•  » » » 5 years ago, # ^ |   +1 Thank you for nice answer!
 » 5 years ago, # |   0 On the last Intel contest i've done 1311 points and then i got more 31 rating points, on this contest i've got 1314 points but i've lost 75 rating points. Why?
•  » » 5 years ago, # ^ |   +4 Look what rank you got last time and now. There is a big difference between 1402 and 2874.
•  » » » 5 years ago, # ^ |   0 What about the fact that now may have more people which can be better than me? Instead of getting worse i just keep on the same level, but there are better people now. The rating should be about me not about the others.
•  » » » » 5 years ago, # ^ |   0 rating about you but hard level of problem about the other =))
 » 5 years ago, # |   0 Was Problem D Rejudged?
•  » » 5 years ago, # ^ |   0 NORating changed with all of wrong accepted solutions :(
 » 5 years ago, # |   +1 For problem E I got the right idea but forgot to sort the sockets by its value, so sad.
 » 5 years ago, # |   +3 I think in this round solutions don't checked with good tests, I found two accepted solutions in D problem, but solutions was wrong. Sorry for my poor english! My tests: 6 2 0 0 1 2 0 0 2 27 2 0 0 0 0 0 1 2 2 2
•  » » 5 years ago, # ^ | ← Rev. 4 →   +8 This comment is right. Why is my solution Accepted? My solution is wrong.
•  » » 5 years ago, # ^ |   +3 first solution is -1,second is 7,right ?
•  » » » 5 years ago, # ^ |   +8 My solution: in: 6 2 0 0 1 2 0 0 2 2 out: 6 //this is wrong in: 7 2 0 0 0 0 0 1 2 2 2 out: 7
•  » » » » 5 years ago, # ^ |   0 my is -1 in first and 7 in secondcode already AC
•  » » » » » 5 years ago, # ^ |   +8 My solution is AC to
•  » » » » » » 5 years ago, # ^ |   0 This set of data maybe not exist in the test data !
 » 5 years ago, # | ← Rev. 3 →   0 I want to aks what is the meanning of d[i] in the question D ?It is the number of subject or the sum of passed subject ?(eg: if d[1]==3, it says that 1st day could pass 3rd subject or 1st could pass three subjects no matter whatever the number of subject ?)plesase test this: 10 3 0 0 1 1 1 0 1 0 1 0 1 1 4
•  » » 5 years ago, # ^ |   0 The number of the subject which could be passed on day i.Answer is simply -1 since 2nd and 3rd subjects cannot be passed on any day.
 » 5 years ago, # |   +1 In B I was considering n=1 case separately and was printing k-a[0] if a[0]
 » 5 years ago, # |   +4 When I waked up and opened CodeForces website, I was so excited to find I turned purple :DIt's interesting and a pity that I have never got a 4/5 or 5/5 after 29 rounds, maybe I will jump back to div2 soon and get my first 4/5.
 » 5 years ago, # |   0 Can anyone explain to me the greedy approach of E and why does it work? and also F please :D
 » 5 years ago, # | ← Rev. 9 →   0 In problem E, I don't understand why my solution is using a lot a memory.My solution is simple, first I sort all sockets, so for each socket e reduce it (ceil(x/2)) trying match it with a free computer.to do it, I use a map > (vector of indices of PC's with power X). So, all memory that I use is O(n) in map + (n+m) of the input.Link of Code
 » 5 years ago, # |   +17 when will the editorial be posted?
 » 5 years ago, # |   +5 hello, I have participated in contest #377 Div. 2 I have One test for Problem D, many of codes can't pass this but they are still considered as right, please check it. 10 3 0 0 1 2 2 0 2 0 1 3 1 1 4 the answer is 10 but some codes that passed the testes are bringing 9 ^_^
•  » » 5 years ago, # ^ |   0 you make mistake 10 3 0 0 1 2 2 0 2 0 1 3 1 1 4day 1 preparation for first exam day 2 preparation for second exam day 3 participate in first exam day 4 participate in second exam day 5 to day 8 preparation for 3rd exam day 9 participate in 3rd exam.Now how you are true?
•  » » » 5 years ago, # ^ |   0 day 9 participate in 3rd exam. How?
•  » » » » 5 years ago, # ^ | ← Rev. 3 →   0 cause in day nine you can participate at least in one subject. if i ask you why he cannot take part? don't get me wrong. if you show me the point why he can't then it will be easy for me to explain. within first 4 days you can complete first two exam. then 5 to 8 (4 day) for preparation for third exam and day nine 3rd exam. 1 indexingUPD:" it is not necessary to prepare continuously during ai days for the exam number i. He can mix the order of preparation for exams in any way." from problem statement
•  » » » » » 5 years ago, # ^ |   0 first day you take preparation for first exam. since in day second you can't participate in exam; you can prepare for 2nd exam rather than rest.
•  » » » » » » 5 years ago, # ^ |   0 You can only take exam ai on day i.
•  » » » » » » » 5 years ago, # ^ |   0 yes. you are right. i was wrong. thank you.
•  » » » » » » » 5 years ago, # ^ |   0 http://codeforces.com/submissions/HOMIARA_RUBY# you see how lame code it was ! i wonder how it got ac!!
•  » » » 5 years ago, # ^ |   0 you can not participate in 3rd exam on day 9
•  » » 5 years ago, # ^ |   +3 I vote to extend testing package too. In the name of Truth, those coders must not sleep well. There are such solutions which are certainly wrong: for(i=m+sum_of_a;i<=n;i++) if(d[i]) {cout<
 » 5 years ago, # |   0 Does anyone know What happened to acm.sgu.ru?
 » 5 years ago, # |   +11 Where is the tutorial?
 » 5 years ago, # | ← Rev. 2 →   0 My solution for D is 21627006 which is not suited for input:5 20 0 0 1 21 1because it gives as output 4, I think it need to be 5 but still accepted....
 » 5 years ago, # |   +12 Am I the only one still waiting for the editorial?
•  » » 5 years ago, # ^ |   -10 hope this one can help you :) Your text to link here...
•  » » » 5 years ago, # ^ |   +10 The one you gave us is round 376 editorial. This is round 377.
 » 5 years ago, # |   0 Auto comment: topic has been updated by danilka.pro (previous revision, new revision, compare).
 » 4 years ago, # | ← Rev. 2 →   0 Hey guys!! I have found something very weird with Problem D!! For example, a solution like this : #includeusing namespace std;main(){long long int n,m,i,sum; `scanf("%I64d %I64d",&n,&m); long long int ar[n+1],br[m+1]; sum=m; for(i=0;i