### MikeMirzayanov's blog

By MikeMirzayanov, 5 years ago, translation, ,

The contest has been moved to the Gym.

Today it will be ACM-ICPC, NEEERC, Southern Subregional Contest! As a head of judges I wish good luck to all the participants!

On Saturday (October, 25), 07:00 (UTC) it will be a internet-mirror: [contest:481]. Interesting problems are waiting for you. Judges tried to prepare problems of wide difficulty range: for newcomers and for expirienced teams.

For sure, it will be unrated contest. We recommend you to take part in teams. I think, the contest will be moved to Gym later.

Good luck!

##### P.S. Saratov Views:

• +353

 » 5 years ago, # |   +70 prizes are depicted at bottom right? (i thought alcohol i got 3 hrs ago lost its effect ;)
 » 5 years ago, # |   +35 Yeah, I like the last Saratov view. haha
•  » » 5 years ago, # ^ | ← Rev. 2 →   -59 The comment is hidden because of too negative feedback, click here to view it
•  » » 5 years ago, # ^ |   +6 This blog has 10 lines and 6 pictures. But all the comments are about the bottom right picture. Interesting :D
•  » » » 5 years ago, # ^ |   0 I don't know man, I find that "Saratov Approaching" pic quite creepy. Like where is NSFL tag? Scarred4lyf :(
 » 5 years ago, # |   +59 100 votes up for the bottom right Saratov view :D
•  » » 5 years ago, # ^ |   +124 sorry man. There's only one type of bra for me, it's Algebra
•  » » » 5 years ago, # ^ |   +22 So you are a girl and never wear bras? waiting for down vote online :)
•  » » » » 5 years ago, # ^ |   -43 hentai!!!
•  » » » » » 5 years ago, # ^ |   +1 @_@ me? never
•  » » » » 5 years ago, # ^ |   0 dude, I am a man -_-
 » 5 years ago, # |   +46 The last Saratov view is mesmerizing *_*
•  » » 5 years ago, # ^ |   +73 i know, the beach is beautiful, isn't it ? *_*
•  » » » 5 years ago, # ^ |   +87 Dude, there's a beach in that pic?! o.O
•  » » » » 5 years ago, # ^ |   0 Around 8 things in particular?
•  » » » » » 5 years ago, # ^ |   0 Don't think small man, think bigger :)
•  » » » » » 5 years ago, # ^ |   +30 Around 16 :P.
•  » » » » » » 5 years ago, # ^ |   0 Atleast 18 dude !! :D :P
 » 5 years ago, # |   +9 I love Saratov!!!
•  » » 5 years ago, # ^ |   +32 Anything in particular? :p
•  » » » 5 years ago, # ^ |   +33 Many things in particular. I'm sure you know. ;)
•  » » » » 5 years ago, # ^ |   +2 Don't we all? ;)
 » 5 years ago, # |   +88 Oh, dammit. Codeforces is gonna be filtered soon in Iran... :|
•  » » 5 years ago, # ^ |   +26 Ugly Truth!!
•  » » » 5 years ago, # ^ |   -29 the photo is not good for CF !!!you enjoy from this photo!!!
•  » » 5 years ago, # ^ |   +9 it got filtered in like 43 hours XD
•  » » 5 years ago, # ^ |   +57 Great prediction!
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 .
 » 5 years ago, # | ← Rev. 6 →   +141 I'm sorry to say that, but the "Saratov Girls" photo is taken at Sydney's Bondy Beach (Australia) for some Cosmopolitan Magazine event:Click the image below to follow the link and switch to the 2-nd picture to compare:And note Copyright 2012 News Group Newspapers Ltd and/or its licensors. No use without permission. Contact ... when right-clicking the image.However, I think other pictures may be more authentic :)And by the way I believe There are many more beautiful girls in Saratov — probably it would be easier to find them via social networks rather than from google...
•  » » 5 years ago, # ^ |   +102 Google lied to me, Sherlock.
•  » » » 5 years ago, # ^ |   +179 My bad, I thought that I've met the second girl from the left.
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 My bad, I thought that I've met the second girl from the left. Ah, nowadays the girls often are trying to follow the same "magazine-photo-model-standard" which leads to many of them be quite indistinguishable :(P.S. But it may happen that either you or this girl have travelled there some time ago...
•  » » » » » 5 years ago, # ^ |   0 Everyone in Saratov reads Cosmopolitan, that's why the last picture is pretty standard for them
•  » » » » 5 years ago, # ^ |   +42 zero-based indexes? :D
•  » » » » » 5 years ago, # ^ |   0 here the science tell us it doesn't matter :D but I believe many sorting algorithms will stuck on this problem :D
•  » » 5 years ago, # ^ |   +149 Thanks RodionGork for making image larger now everything is clear :D
•  » » » 5 years ago, # ^ |   +36 And I thought you got engaged only recently? :O
•  » » » » 5 years ago, # ^ |   +65 That's why I saw this image only once :D
 » 5 years ago, # |   +4 This contest overlaps with the following contest http://acm.timus.ru/contest.aspx?id=241Lets hope one of the contests will be shifted :)
•  » » 5 years ago, # ^ |   +4 Thanks for warning it! I totally forgot about the timus contest.
•  » » » 5 years ago, # ^ |   +9 you can use google calender , whenever you find a contest scheduled it and just check the calender every morning , it helps me a lot :)
 » 5 years ago, # |   0 i love saratov especially girls :P
 » 5 years ago, # | ← Rev. 2 →   +14 To be noted, there is this contest on UVa http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=12 and another one in Timus http://acm.timus.ru/contest.aspx?id=241 same day/time.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 The UVA contest will not take place,as far as I know (but not 100% sure). Still we have two contests at the same time on CF and Timus. Both contests are GREAT and both Russian,so,lets hope the personnel in charge will do something about the time clash :)
•  » » » 5 years ago, # ^ |   0 Contest on Timus is better for Div. 2, Southern Subregional — for Div. 1
 » 5 years ago, # |   -49 please change your photo this photo is not good for CF !! thanks
 » 5 years ago, # | ← Rev. 6 →   -71 I didn't know why, But since I was a kid, I had a feeling that I love Saratov. And now I know what was the reason of that feeling. :D
 » 5 years ago, # |   0 Saratov is beautiful !!
 » 5 years ago, # |   +8 that motivates to code :P
•  » » 5 years ago, # ^ |   +6 Or just gives you plain distraction. If you know what I mean ;)
 » 5 years ago, # | ← Rev. 2 →   0 I can't say anything:|ACM & girls ...
•  » » 5 years ago, # ^ |   +25 Then don't say anything , Just make sure that you don't flood the blogs with comments that don't mean anything.
 » 5 years ago, # | ← Rev. 2 →   +24 Let vote themI choose third one from left :D
•  » » 5 years ago, # ^ |   +3 I think all of them are good :x :D
 » 5 years ago, # |   0 Is it possible to keep rated contests for teams and give ratings to teams like you give ratings for individual users ?
 » 5 years ago, # |   +5 2012/2013: top 4 2013/2014: top 4 2014/2015: top 4 2015/2016: ?????
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 Saratov: SU1, SU22011/2012: top22012/2013: top22013/2014: top22014/2015: top22015/2016: ?????xD
•  » » » 5 years ago, # ^ |   0 Don't praise your teams unless they defeat Nizhny Novgorod SU.
•  » » 5 years ago, # ^ |   +16 Full version: 2009/2010 top 4 2010/2011 team with dalex 2011/2012 team with dalex 2012/2013 top 4 2013/2014 top 4 2014/2015 top 4 2015/2016 top 1 (as ez collections became java standard) 
 » 5 years ago, # |   0 This picture on the bottom right corner really has nothing to do with a programming website Always distract me when I open the site.
•  » » 5 years ago, # ^ |   +241 Why do you say it has nothing to do with programming? It's a well known programming task — eight queens. You need to place eight white queens on the chess board so that none of them can beat any other. The solution displayed on top is not a valid one though.
•  » » » 5 years ago, # ^ |   +7 wait. 8 queens..?holy macaroni, you certainly know how to think outside the box.
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   +55 He ain't RED for nothin' ;)
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +14 marat.snowbear if you look closely, then you'll find out that this is actually a variation of the eight queens problem — nine queens. It can be observed more clearly thanks to the image provided by RodionGork :)
•  » » » 5 years ago, # ^ |   +12 Yes but chess pieces are much harder and they are not physically attractive.
 » 5 years ago, # |   -9 Its repulsive
 » 5 years ago, # |   -34 Trust from the GOD!!! What is this picture??? Do you know hove many person will see that picture??? I GUESS NEXT TIME YOU WILL NOT PUT BAD THINGS IN THIS SIDE
 » 5 years ago, # | ← Rev. 3 →   -14 Really, can that picture be removed? In addition to different religious views, consider a high-school teacher recommending the website to his/her students. If this picture will be the first thing they will see, it might lead to some embarrassing situation and the teacher getting fired.
•  » » 5 years ago, # ^ |   +53 Life is pain...
 » 5 years ago, # | ← Rev. 2 →   0 Why can't I register a team ?? :\
•  » » 5 years ago, # ^ |   +3 It will be possible soon
 » 5 years ago, # |   0 It says in the post that teams are preferred. But how to register a team for an upcoming contest?
•  » » 5 years ago, # ^ |   0 It will be possible soon
 » 5 years ago, # |   -21 I think this contest is same with TIMUSDuration and starting time are same.
•  » » 5 years ago, # ^ |   -8 NO
 » 5 years ago, # |   +14 Ranklist is broken. My solved G disappeared from the ranklist after a while. WTF?
•  » » 5 years ago, # ^ | ← Rev. 3 →   +29 Why the negative rating? The above message was a legitimate bug report I typed during the contest. The ranklist was indeed broken for quite some time (30 minutes or so). My dashboard showed that I had 7 problems solved but one of them (and not the last one submitted) was missing from the scoreboard. It did, as I mentioned before, disappear -- immediately after I solved problem G it was shown in the scoreboard, but it stopped appearing after a while. I have no idea how such a thing is possible, but it is certainly a bug.
 » 5 years ago, # |   -17 Cant apply binary search on them(hot chicks) due to random distribution... :P
 » 5 years ago, # |   0 What was the 31st test for F?
•  » » 5 years ago, # ^ |   0 We've made about 15 WAs in that case too
•  » » 5 years ago, # ^ | ← Rev. 3 →   0 my error was a wrong algorithm...
•  » » » 5 years ago, # ^ |   +7 You are choosing the max cut, then choose the next max cut, but this is totally wrong, You have to try all possible cuts and select the maximum cut on the left or on the right.in case 31:9 315 15 15 30 1 30 15 15 15You select (10+1+30) which is 61, then you have only (15+15+15) on the left or the right,but if you try all cuts, you will get (15+15+30) + (30+15+15)something like this: 8410587
•  » » » » 5 years ago, # ^ |   0 Thank you!
•  » » » » 5 years ago, # ^ |   0 Thank you!
 » 5 years ago, # |   0 How to solve B?
•  » » 5 years ago, # ^ |   +16 make a count for each color ... and keep the "-1" blankets as a bonusNow repeat the following process while u have a color where count[color]%(k/n)!=0 : Pick the color with the minimum count and count[color]%(k/n)!=0 ... call it color1 Let's set v = color1%(k/n) Pick the color with the maximum count (other than the color1) .. call it color2 If u can't find possible colors in step2 ... pick the bonus blankets. Now color v blankets from color1 with color2 ... and (k/n-v) blankets from color2 with color1 if (k/n-v)>count[color2] ... use bonus blankets, and remove from them k/n — (v+count[color2]) if conut[bonus] < (k/n) — (v+count[color2]) ... then the answer is No After u finish this process, for any color i, it will achieve count[i] % (k/n) = 0Which can be easily matched with itself
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +11 Directly while loading the input you can color one side of each -1 blanket any color you like (e.g., add all of them to color 1), the solution always exists anyway, and the code gets simpler: you simply always take the color with the least (non-zero) number of blankets, and if it is not enough, you fill the rest from the color with the most blankets.(This is essentially the same algorithm as used in the Alias method)
•  » » » » 5 years ago, # ^ |   0 Strange, I'm doing the same, yet I can't get past test #2. I made random tester and checker just to find that my code easily passes a few million tests. It seems I am missing something, can somebody help me with tests/suggestions? The code is 8417893.
•  » » » » » 5 years ago, # ^ |   0 Test #2 is most likely the second example input. You are failing it because you are not outputting the blankets in the order in which they appear in the input. (Your third blanket is 3 4, but one of its sides should be 1.)I got one WA for this during the actual contest, I was also too careless in reading the statement :)
•  » » » » » » 5 years ago, # ^ |   0 Thank you very much, that was the problem!
•  » » » » 5 years ago, # ^ |   0 I've get AC using your instructions and read about Alias method but can't understand why is it the same algorithm ='(
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 Do you have a proof of why this works? (Or a link to a proof; I couldn't find an editorial.)We considered this greedy approach, but since we couldn't prove it, we didn't implement it.
•  » » » » 2 years ago, # ^ |   0 Here I am giving the proof of problem B. We know that we can easily solve the problem when n=2. Now if we have n=x then we can simple reduce it to n=x-1 using the technique described above,i.e.,take the color with smallest number of blankets and complete this set with any other set of color u want(above given is the set of color with maximum number of blankets). One thing should be kept in mind that the other chosen set must have blankets greater than required number.
 » 5 years ago, # |   +12 editorials?
 » 5 years ago, # |   +44 First time I see, a grandmaster wants to cheat with me! Cheers!
•  » » 5 years ago, # ^ |   +14 cheaters are everywhere!
 » 5 years ago, # |   0 How many comands go from NEERC Southern Subregional to 1/2 final NEERC Spb?
•  » » 5 years ago, # ^ |   0 13
•  » » 5 years ago, # ^ |   0 in final standings top14 without Saratov 5
 » 5 years ago, # | ← Rev. 3 →   0 D — Data Center. I dislike such "obfuscation" that LOW voltage is marked by bigger value (1) than HIGH voltage (0), why not ask to find minimum servers with HIGH voltage, which should be marked as 1? I misread (as usually) statement, made opposite, and gain WA #12 8408879.
 » 5 years ago, # |   +8 Is this Contest archived? I can't resubmit any problem!
•  » » 5 years ago, # ^ |   +16 For now, you need to enter it in virtual participation to be able to make submissions.
•  » » » 5 years ago, # ^ |   0 Oh, thanks!
•  » » » 5 years ago, # ^ |   0 My virtual participation has ended but I still want to make more submissions. What can I do?
•  » » » » 5 years ago, # ^ |   0 Start another virtual participation.
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 You can start a new virtual participation :v But after that, you can't submit any other contest ^^!
•  » » 5 years ago, # ^ |   0 Yes...
 » 5 years ago, # |   0 thank you for the contest it had some nice problems
 » 5 years ago, # | ← Rev. 3 →   0 This contest is no longer on the contest page. Why has it been removed ?EDIT: I now see it has been moved to the gym :)
•  » » 5 years ago, # ^ |   0 It was moved to the Gym.
 » 5 years ago, # |   +5 Can anyone give me some hints about prob. G and K?
•  » » 5 years ago, # ^ |   0 G: Find the leftmost interval that needs changing. Where should you change it? Clearly, the best option is to start from its right end -- this will also lower the most other intervals to the right of the current one. My solution runs in O(n) and uses a deque to store the non-minimal elements in the current length-K interval. Each time you move one step to the right, possibly pop_left once, push_right once, and then pop_right while needed.K: Obviously, you can connect each vertex to the second one in its list (i.e., the first one other than itself). This gives you at least n/2 edges, but not necessarily all n-1. How to generalize this? Suppose that you already have some components. If some component A and component B were connected via an edge a-b, what would you see? For each vertex of A, the first vertex of B in their list would be b, and vice versa. Notably, a and b are the first ones of A and B for each other. When can you be sure that you found a new edge? If you find two vertices a in A, b in B such that: b is the very first vertex in a's list that is not in A, and a is the very first vertex in b's list that is not in B. Does such a pair of vertices always have to exist?
 » 5 years ago, # | ← Rev. 2 →   -23 As if girls were the prize of ACM ICPC :-P and yeah, look at the hypocrites, if some non-'RED' coder comments they upvote it (oh look, how funny), but if same comment is made by some other coder, they all join hands to downvote it.
 » 5 years ago, # |   +12 I can's submit problems in the Gym. It goes to a link like this — http://codeforces.com/gym/100513/problem/C?csrf_token=a9770299g5h52c9hda3d7887h9h9313a and shows error code ERR_EMPTY_RESPONSE
•  » » 5 years ago, # ^ |   +3 Same here. Me too. I got "Network Error" every want to submit
 » 5 years ago, # | ← Rev. 3 →   -21 "Network error"! I can't submit! :(
 » 5 years ago, # |   0 When will the editorials be published?
 » 5 years ago, # |   0 Can someone kindly outline the idea for Problem K?My idea was to regard graph as a chain for every vertex to create distance matrix,then use floyd to compute shortest distance, finally union set to output n-1 edges 8417836 don't know where it is wrong and it keeps wrong answer for test 4
•  » » 5 years ago, # ^ |   +1 Your code does not make much sense to me. Why would you, for example, do "dis[u][v]=dis[v][u]=min(dis[u][v],j-1);"? If v is the j-th vertes in u's list, it can still be much closer than in distance j-1 -- for instance, even in distance 1. So at this point you only get some random upper bounds on the distance.Afterwards, you only process pairs that are in distance 1, but those had to be in distance 1 even before the Floyd-Warshall, so the Floyd-Warshall actually does nothing, and you only take the pairs of vertices you already know that are in distance 1.Here is a test case that breaks your solution: 4 1 2 3 4 2 1 3 4 3 4 2 1 4 3 2 1 You will only find the edges 1-2 and 3-4, but not the edge 2-3.(I already wrote a post with some hints for K, look above.)
 » 5 years ago, # |   0 Any idea about problem C ?
•  » » 5 years ago, # ^ |   +5 First of all, in order to ease your processing you might want to convert the tree such that each node has only one key/value pair. Then each "component" will be represented by a chain of k/v pair nodes, connected from the first one to its parent (unless it's the main component), and from the last one to all of its children in the component graph. Now your problem is simply reduced to finding the first occurrence of some key on the path from any node to the root. This can be done in O(log N) time per query using a technique known as Heavy-Light Decomposition (HLD) — a fairly simple transform that allows you to get from any node in a tree to the root in logarithmic time, by potentially skipping over entire chains.
•  » » » 5 years ago, # ^ |   0 Bruce also mentions heavy-light decomposition in his blog but I think that it is an overkill and that my solution is simpler to implement. Here it is:Preprocess the tree into a list of (key,value) pairs by running a simple DFS and maintaining a stack for the occurrences of each property. Here are the steps: Each time you enter a new vertex v, append all its properties to the list, push them into the corresponding stacks, and then store the current length of the list into L[v]. Each time you finish processing a vertex, pop all its properties from their stacks and append the new tops of those stacks to the list (these key,value pairs just became visible again). After this preprocessing, for any vertex v and any key k, we simply need to find the last occurrence of k in the first L[v] elements of our list. To do this quickly, just build an interval tree on top of the list, and in each node store the set of keys that occur at least once in its subtree.
•  » » » » 5 years ago, # ^ |   0 That is slightly simpler (although the heavy-light decomposition only takes about 25 lines of code). I suspect it could be simplified further to avoid the interval tree: just keep a separate list for each property, with a field for the position in the original combined list (which doesn't physically need to be constructed). Then the search just becomes a binary search on the right per-property list, and can use lower_bound.
•  » » » » » 5 years ago, # ^ | ← Rev. 3 →   +3 This is exactly how I solved it (8408659).For each property:Consider only nodes that contain it. Iterate these nodes in the dfs order (we can run a dfs beforehand to determine this). When you enter a node, push its value to the stack. When you exit from a node, pop its value. Since there might be missing nodes (not all of nodes have this property), we can add some extra spaces between the sequence of nodes to simplify the query process. Eventually, we just use lower_bound to find the relative position of the given node in the preprocessed sequences and return its value.
•  » » 5 years ago, # ^ |   0 Here is an easy segment tree based solution:First build a segment tree by traversing the tree in preorder, then each subtree forms a contiguous segment in the segment tree. Each node u in the segment tree has a map tree[u]. An update operation at node u takes a (key, value) pair and updates tree[u][key] with value if tree[u][key] is not set yet.Run a dfs to build the segment tree, index[node] is the index of component node in the segment tree. dfs (node, count) index[node] = count for each child u of node count = dfs(u, count + 1) for each (key, value) in property[node] // note that the segment (index[node], count) contains the subtree from node update (1, 1, n, index[node], count, key, value) return count The update operation: update (node, l, r, x, y, key, value) if x > y return if l == x and r == y tree[node][key] is not defined tree[node][key] = value return mid = (l + r) / 2 update (node * 2, l, mid, x, min(mid, y), key, value); update (node * 2 + 1, mid + 1, r, max(x, mid+1), y, key, value); Query operation: query (node, l, r, pos, key) if l == r if tree[node][key] is defined return tree[node][key] else return N/A else mid = (l + r) / 2 if pos <= mid and query (node * 2, l, mid, pos, key) is not N/A return query (node * 2, l, mid, pos, key) else if pos > mid and query (node * 2 + 1, mid + 1, r, pos, key) is not N/A return query (node * 2 + 1, mid + 1, r, pos, key) else if tree[node][key] is defined return tree[node][key] else return N/A Now for query (x, key) answer will be query (1, 1, n, index[x], key)
•  » » » 2 years ago, # ^ |   -8 Thank You. :)
•  » » » 2 years ago, # ^ |   0 This method is giving TLE.https://pastebin.com/zJTksZn1Can you please check out the code and give some suggestions.
•  » » 5 years ago, # ^ |   0 It's possible that offline solutions got AC in problem C ? I code a offline HLD and i don't know why i got "Idleness limit exceeded on test 1" . Should be because i run a offline algorithm ? My idea is very similar to many people , for every kind of key i activate all nodes with that key and then answer all queries of same kind of key.
•  » » » 5 years ago, # ^ |   +8 Yes, you should construct an online solution. This is an "interactive" problem: you can't read the next query until you print the answer to the previous one and call fflush(stdout).
•  » » » » 5 years ago, # ^ |   0 Ok i know it now , Thank you very much , it's first time that i try to solve an interactive problem :v.PS: How do you solve it with an online solution ?
 » 5 years ago, # |   +66 I've added analysis of all the problems except L to my blog.
 » 5 years ago, # |   0 Any idea what is causing the runtime error for problem D? I saw a couple of people get it (including me.) I got it on test 16.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 Was because I didn't use long for m. But now I am getting a wrong answer on #17. This is my algorithm:Sort servers with first comparator capacity and then voltage. That is for two servers A and B, A is greater than B iff A.capacity > B.capacity or A.capacity == B.capacity and A.voltage > B.voltageThen looping from the last server, If A.capacity >= m and A.voltage == 1: Take it and break the loop Else if A.capacity >= m and A.voltage == 0: Traverse ahead and check if there is an element C such that C.capacity >= m and C.voltage == 1. If such an element is found, break and take C. If at any point C.capacity < m break and take A. Else take C. Break the loop. Else (In this situation A.capacity < m so take it irrespective of voltage because we have sorted by voltage anyway. And then set m = m - A.capacity If someone wants my code please inbox me. I would appreciate any help. Thanks!
 » 5 years ago, # | ← Rev. 2 →   0 How to solve problem A? Как решать задачу А?
 » 5 years ago, # |   +12 could adminstor put the Ural Regional School Programming Contest 2014 contest into the gym to practice,it is also a very good contest,thanks
 » 5 years ago, # |   0 I am left with all these girls, you fall in love you want
 » 14 months ago, # | ← Rev. 4 →   0 I think I didn't understand problem 100513L - Useful Roads . Can someone provide me with the output for the following test case? 6 6 1 2 1 3 1 4 2 5 2 6 3 6 I think the useful edges are all, cause all of them can be used to go to some vertex.