By KAN, 3 years ago, translation,

Hello everybody!

Today, on March 4th 2018 the final round of Technocup olympiad for Russian-speaking high school students is held. The round starts at 11:30 Moscow time.

After the round starts, you can watch the current results.

For those who want to compete on the same problems, we will host two Codeforces rounds: one for the first, and one for the second division. The rounds will start at 15:35 UTC, don't miss them!

If you compete in the Final Round today, you can't compete in the rounds at evening.

The problems are prepared by Endagorion, komendart, rationalex, AndreySergunin, fcspartakm, MikeMirzayanov and me. For testing the problems many thanks to demon1999, Belonogov, vintage_Vlad_Makeev, adedalic, Nebuchadnezzar, GreenGrape, Neon! Also many thanks to vintage_Vlad_Makeev for his help in hosting the round at Codeforces!

P.S. Because of the olympiad, some Codeforces features may be disabled today.

Good luck!

UPD: Congratulations to Technocup winners!

Congratulations to winners of Codeforces rounds!

First division:

Second division:

• +156

 » 3 years ago, # |   -65 is it rated?
•  » » 3 years ago, # ^ |   +91 Yes.
•  » » 3 years ago, # ^ | ← Rev. 2 →   -43 Firstly, You had better ask "Is it DATED?" then you didn't get many down votes!
•  » » » 3 years ago, # ^ |   -74 "Is it RATED?", not "Is it DATED?".
 » 3 years ago, # |   0 So why”Codeforces Round #468”disappeared now?In”Contests”
•  » » 3 years ago, # ^ |   +4 Its still there.
 » 3 years ago, # |   -43 Hope the problem statements are as short as the announcement.
•  » » 3 years ago, # ^ |   -10 I don't know why your comment get down voted ?
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +17 I think the reason is that he copied the comment from another contest blog.（#467）
•  » » » » 3 years ago, # ^ |   +32 It is actually commented everywhere
•  » » » 3 years ago, # ^ |   -21 I don't know.
 » 3 years ago, # |   +12 Hope to see some quality problems A & B for <1200 contestants like me
 » 3 years ago, # |   +41 The contest overlaps with Barcelona's match
•  » » 3 years ago, # ^ | ← Rev. 2 →   +15 The contest overlaps with Arsenal's match
•  » » » 3 years ago, # ^ |   +25 Wenger Out
•  » » » » 3 years ago, # ^ |   -10 not that Arsenal, dude
•  » » 3 years ago, # ^ |   +88 No...the Barcelona match overlaps with the contest
•  » » 3 years ago, # ^ |   0 the match started first
 » 3 years ago, # |   +16 *Forgets to thank Mike and Polygon**Mike TRIGGERED*
•  » » 3 years ago, # ^ |   +11 That would be Mike thanking Mike.
 » 3 years ago, # |   -9 Because of the Olympiad, some Codeforces features may be disabled today. ??
•  » » 3 years ago, # ^ |   0 they want to prevent cheating so they will disable features like view users submissions
 » 3 years ago, # |   +23 I think Problems Scoring is not important nowadays :|
 » 3 years ago, # |   +11 Clashes with IEM Katowice finals.
 » 3 years ago, # |   -22 Will #468 be rated ?
•  » » 3 years ago, # ^ |   0 Actually it'll be reverse rated! The problem setters decided that the person with the lowest rank in the contest will get the biggest positive rating change. So you should try your best to do as bad as possible! Good luck!
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +10 I am following your advice. Let's see how it goes !
 » 3 years ago, # | ← Rev. 2 →   +36 The one who wrote problem Div-2 D has very bad English skills (hardly understood what the problem setter had in mind).
•  » » 3 years ago, # ^ | ← Rev. 2 →   +50 Div1-C was even harder to understand for me, I spent 10 minutes trying to understand who would be lying about what.(Not like I managed to solve it after I understood the question)
•  » » » 3 years ago, # ^ |   +3 Well maybe. As you can see from my rating I haven't even approached that problem.
 » 3 years ago, # |   +70 Oh, how I missed this improvised English on Codeforces! Seriously, I understand some random amateur setter letting this happen, but given all those commonly mentioned names in the announcement, is this really what we get? It is also very funny how sometimes people with obviously bad grammar and limited vocabulary decide to throw in a few uncommon words, who knows why (Div-1 A).
•  » » 3 years ago, # ^ | ← Rev. 3 →   -8 Div-1 A has a pretty good statement. I think you meant Div-1 B, which fits well your description.
•  » » » 3 years ago, # ^ |   +5 The only problem with good statement I saw was Div-1 E. My last sentence from the previous comment was specific to Div-1 A.
•  » » 3 years ago, # ^ |   -14 It's not the best English, but everything seemed pretty clear even if you had to reread once
•  » » » 3 years ago, # ^ |   0 When it comes to languages, my definition of pretty clear never coincides with German speakers' xD
•  » » » 3 years ago, # ^ |   +32 I'm a native english speaker and I thought it was unclear, especially for C
 » 3 years ago, # |   +1 RIP rating...
 » 3 years ago, # |   0 Why can't I see any hacks? Were pretests particularly thorough?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +5 There were a few. I could have had a successful hack on C, had I seen it earlier since somebody in my room messed up N and M.
 » 3 years ago, # |   +9 How did NotSoStupid manage to solve B in 20 seconds?
•  » » 3 years ago, # ^ |   0 By knowing it in advance?
•  » » » 3 years ago, # ^ |   0 I guess so
•  » » 3 years ago, # ^ |   +14 Maybe because he is not stupid :?
•  » » » 3 years ago, # ^ |   +14 Funny
•  » » 3 years ago, # ^ | ← Rev. 2 →   -16 I don't think that he can read the problem and write the code and submit it in that time. He should be Flash (https://en.wikipedia.org/wiki/Flash_(comics))
 » 3 years ago, # | ← Rev. 2 →   +56 In my noob opinion, first 3 problems were way too easy, now ranks 70-350 of div1 are all decided by time.Now anyone who fail system testing basically goes back to div2.
•  » » 3 years ago, # ^ |   -34 That is how it is in Div 2? how about stop crying?
•  » » 3 years ago, # ^ |   +10 What was Div1C about ? For me the easiest way was to find the biggest subsequence whose cnt values are increasing then decreasing, but I could not find a way to do it in a reasonable complexity.I saw everybody solving it, did I miss something obvious?
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +20 Longest increasing subsequence with segtree is n log n
•  » » » 3 years ago, # ^ |   +15 Compute the longest increasing subsequence ending in each point and longest decreasing subsequence starting in each point (LIS on reverse array) in n logn each and then one linear pass. (passed pretests at least)
•  » » » 3 years ago, # ^ |   +10 just find for a position pos longest increasing that ends there, and longest decreasing that starts there
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +5 This problem is pretty standard. It can be easily solved using segment tree. In segment tree at position x we store longest increasing subsequence which ends at some position with height x. So longest increasing subsequence for every position i is maximum in range [0, height[i]] (for all values with smaller index j, j < i) + 1. The same can be done for longest decreasing subsequence.
•  » » » » 3 years ago, # ^ |   +12 Can be done in an even easier way using only vector+lower_bound.Refer here
•  » » 3 years ago, # ^ |   0 still only one solution failed :(
•  » » 3 years ago, # ^ |   +8 The segment tree actually isn't necessary. To identify the longest increasing subsequence we can maintain an array of the lowest value at the end of an increasing subsequence with length X we've discovered so far. Then we can binary search to find the longest increasing subsequence ending at the next index. We can do one pass forwards and another pass in reverse to get the longest increasing and decreasing subsequences ending/starting at each point. Then consider all of the possible values and find the maximal value of the sum of the increasing/decreasing subsequences for that value minus one (since that particular element will be double-counted).The complexity is O(N log N). https://en.wikipedia.org/wiki/Longest_increasing_subsequence A similar algorithm is outlined here (for longest increasing subsequence).
 » 3 years ago, # |   0 What is the hack for B?
•  » » 3 years ago, # ^ |   +4 My hack was 8 4 5Answer should be final
•  » » » 3 years ago, # ^ |   0 Thanks :)
 » 3 years ago, # |   +1 Can somebody explain to me the answer of 3rd sample of Div1-B, why is it 0.1 the probability? The statement wasnt clear for me either, that thing of open a letter I never really understand it.
•  » » 3 years ago, # ^ |   0 aabaabbbbb abaabbbbba aabbbbbaab abbbbbaaba . And bbaabaabbb baabaabbbb baabbbbbaa bbbbbaabaa bbbbaabaab bbbaabaabb. If the 1st letter is a, vasya can choose 3rd letter and say since it is the only letter containg a in 3rd pos and in 1st. so the ans is 1 / 10.
•  » » » 3 years ago, # ^ |   +1 I dont understand you if the first letter is "a" and you choose third letter then you have for example: aabaabbbbb aabbbbbaabwhich both have "a" in 1st position and "b" in 2nd position so the cycle is not uniquely determined.
•  » » 3 years ago, # ^ |   0 If the first letter shown is "a", you can ask to see the 5th letter of the resulting string. If it is another a, you know k=2.Thus, you can win iff k=2, which has a probability 0.1 of happening
•  » » 3 years ago, # ^ |   +10 All the possible shifts were bbaabaabbb baabaabbbb aabaabbbbb abaabbbbba baabbbbbaa aabbbbbaab abbbbbaaba bbbbbaabaa bbbbaabaab bbbaabaabb If he gets a b first, he cannot determine the shift. Otherwise, if the shift gets an a in the beginning, T can now be one of the following: aabaabbbbb abaabbbbba aabbbbbaab abbbbbaaba If Vasya opens the 5th letter, there is a 1/4 chance it would be an a. If he instead opened any other letter, he would not be able to determine the string. Because of this, there is a (4/10)*(1/4) = 1/10 = 0.1 probability of he winning.
•  » » » 3 years ago, # ^ |   0 Thank you! I finally understood.
•  » » » 3 years ago, # ^ | ← Rev. 4 →   0 a a b a a b b b b ba b a a b b b b b aa a b b b b b a a ba b b b b b a a b aHere only 4th one have 'a' in the 7th position(similarly, only 2nd string contains 'a' in the 3rd position). So, if he would have instead opened it then also he can uniquely determine the shift. so, isn't the probability of winning is 0.3? Please correct me where i am going wrong.UPD : sorry for this! I understood now. Thank you :)
 » 3 years ago, # | ← Rev. 2 →   +53 seriously horrible long statements.Could someone explain what problem Div1C is asking for :3
•  » » 3 years ago, # ^ |   +15 Took me a while to understand, but I think it asks for the most amount of points you can query without knowing if the opponent is lying. Problem statement is highly misleading. At least this understanding passed pretest.
•  » » » 3 years ago, # ^ |   0 Ohh!. this means after finding how many seg that each points belongs by an aux array and find the longest non decreasing subsequence in the result right?
•  » » » » 3 years ago, # ^ |   0 yes, you want to find combination of longest nondecreasing subsequence to a point + longest nonincreasing subsequence after the point
•  » » » » » 3 years ago, # ^ |   0 ohh! yeah!! i forgot that non increasing part!!!!!! shit!!
•  » » 3 years ago, # ^ |   +3 Let (c1, ..., cm) be the answers to the queries for every possible x. How many of these do we need to change, so that there exists a set of intervals S and an integer x, such that li ≤ x ≤ ri for all intervals in the set?
 » 3 years ago, # |   0 How to solve task D (div 2)?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +15 Count the number of tree levels with odd number of nodes.
•  » » 3 years ago, # ^ |   0 answer is the number of heights such that the number of apples on that height is odd
•  » » » 3 years ago, # ^ |   0 But then in testcase #3, shouldn't answer be 8?
•  » » » » 3 years ago, # ^ |   0 no because there's only 4 heights
•  » » » » 3 years ago, # ^ |   0 draw the tree and you will see (p_i is the parent of i+1)
•  » » » 3 years ago, # ^ |   0 How do you explain the 3rd example then? Input: 18 1 1 1 4 4 3 2 2 2 10 8 9 9 9 10 10 4 Output: 4
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 I think that we have 1, 3, 7, 7 nodes in each levels. That's why answer is 4.
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 Can you draw for me your tree?UPD: Don't draw, I get it.
•  » » » 3 years ago, # ^ |   0 How to prove that?
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   +3 Apples can annihilate only if they have equal tree level, so we can say that for each level all apples go to the first node and they annihilate there
•  » » » » » 3 years ago, # ^ |   0 Indeed this is so. Thank you for editorial.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +2 In the first second you are interested in the nodes that will fall into node 1, let's call these nodes D. In the second second you are interested in the nodes that will fall into D (because the next second (3rd second) D will fall into 1)... etc
•  » » » 3 years ago, # ^ |   +1 I get it now, and feel terribly stupid :P btw thanks :)
•  » » » » 3 years ago, # ^ |   0 It's okay, just upsolve the problems :)
 » 3 years ago, # |   0 how the answer for teoder is not lying for 2nd case is 5
 » 3 years ago, # | ← Rev. 2 →   0 Hack for B: 8 4 5
•  » » 3 years ago, # ^ |   0 You meant B?
•  » » » 3 years ago, # ^ |   0 Yes, edited!. Thanks
 » 3 years ago, # | ← Rev. 2 →   +4 Stuck at 11 pretest on C.... impossible, where did i go wrong? any hacks guys? 11 WA and for over an hour couldnn't find any test case to make my code return WA -_-
•  » » 3 years ago, # ^ |   +3 It was necessary to check examples of such a if 1 2 2 3 then you can send 2 2 2 2 or 1 3 1 3 I also understood when there were 2 minutes left) but did not have time
•  » » 3 years ago, # ^ |   0 6 1 2 2 2 2 3yours -> 4, 222222 answer -> 2, 111333
•  » » 3 years ago, # ^ |   0 Try with: 6 1 3 2 2 2 2 Answer should be: 2 1 1 1 3 3 3 
 » 3 years ago, # |   +7 Div-2 D description was totally weird.. I couldn't tell what it says. ;(
 » 3 years ago, # |   +22 does the writer of the problem D statement even speak english? that text is totally weird...
 » 3 years ago, # |   0 Div2B I solved it using simulation but I think there is a solution related to bits.. ?
•  » » 3 years ago, # ^ |   0 I used a binary tree here
•  » » » 3 years ago, # ^ |   0 Way long code ! (for this problem)
•  » » » » 3 years ago, # ^ |   0 yeah, it was the first way to solve that came to me
 » 3 years ago, # |   +11 I think The problem description should be more concise >.<
 » 3 years ago, # |   +18 Personally, I really liked the problems for this round, D has a very clever solution and E was pretty interesting too. C was difficult to understand for me, admittedly, but I don't think it was a bad problem. A and B for me I don't really care because I solve them quick, but they didn't seem bad
 » 3 years ago, # |   +66 Div1C has the most confusing statement I've ever seen. Setters should really be careful when translating.
 » 3 years ago, # | ← Rev. 3 →   +185 Inflorescence number 1 is situated near base of tree and any other inflorescence with number i (i > 1) is situated at the top of branch, which bottom is pi-th inflorescence and pi < i
•  » » 3 years ago, # ^ |   +43 That's when you stop reading and look at the tests and explanations.
 » 3 years ago, # |   0 Please help me with this.Div 2, problem C, test 3: Input:7-10 -9 -10 -8 -10 -9 -9my output was:5-8 -8 -8 -9 -9 -9 -10I think this should be right but I am getting wrong answer.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 The sum of the two sequences are different, so their averages are different, which violates the first constraint.
•  » » 3 years ago, # ^ |   0 the sum of your numbers is -61 but it should be -65
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 original measurements --> the output --> the minimum between them (number of equal measurements)  {-10,-10} --> {-10} --> 1  {-8} --> {-8,-8,-8} --> 1  {-9,-9,-9} --> {-9,-9,-9} --> 3 so, the total number of equal measurements in your answer is 6 not 5. EDIT: sorry i miscalculated, it is 5 lol :D 
 » 3 years ago, # |   +2 Too UNCLEAR problems
 » 3 years ago, # | ← Rev. 2 →   +16 I think this contest would've been better if div2 C and D were swapped, and each division has 6 problems. Div2C was really nice and actually has less solves than D.
•  » » 3 years ago, # ^ |   +3 well they have the same score.
•  » » » 3 years ago, # ^ |   0 Problem A on div1 was actually div2D, and div1 has only 5 problems
•  » » » » 3 years ago, # ^ |   0 Well C is just implementation, but for D you need to know some tree traversal algorithm, i think that's why it was chosen.
•  » » 3 years ago, # ^ |   0 I think Div2D was easier to read, so it was attempted/solved first by many. The solution was also pretty easy to implement when you get the trick. I don't think D was easier than C though.
•  » » 3 years ago, # ^ |   +5 I think this contest would've been better if div2 C and D were swapped, and each division has 6 problems. No, it wouldn't. I was so glad when I read Div2C and realized that it's not in Div1.
 » 3 years ago, # | ← Rev. 2 →   -40 Too unlucky contest for both Contribution and Rating!
 » 3 years ago, # | ← Rev. 2 →   +35 Not sure if my bad performance today is due to my bad forms, bad English translations, or both...One example for my latter point is Div1B.Vasya understands, that he can't guarantee that he will win, but he wants to know the probability of winning, if he plays optimally. He wants you to compute this probability.And I thought I have to calculate the possibility of him guessing the answer at circumstances that he has no certainty at all, wasting me at least 20 minutes in trying to understand pretest 2 of it.
•  » » 3 years ago, # ^ |   +8 same here
•  » » 3 years ago, # ^ |   0 That problem was clear once you read "Note that Vasya wants to know the value of k uniquely, it means, that if there are at least two cyclic shifts of s that fit the information Vasya knowns, Vasya loses. Of course, at any moment of the game Vasya wants to maximize the probability of his win."Div1C was another story...
•  » » » 3 years ago, # ^ |   +5 Ouch, heck....Oh, and Div1C, after reading a few first lines, knowing I had only 10 minutes left, I instantly gave up.
 » 3 years ago, # |   +1 Can someone explain why 2nd example's output of Div2 E is 0,333333? I thought it should be 0,5.
•  » » 3 years ago, # ^ |   +5 Why do you think it's 0.5?
•  » » » 3 years ago, # ^ |   +1 This was how i thought: If you the first letter you got was 't' or 'c', you lose cause you couldn't pick the next letter to make sure about k. If the first letter you got was 'a' or 'i', you win cause you can pick the next letter to guess the k. So the probality is 2/4 = 0.5
•  » » » » 3 years ago, # ^ |   0 The probability that you get 'a' or 'c' however is 4/12, as explained in Renaats' comment below.
•  » » 3 years ago, # ^ |   0 You have 4 letters "t", 4 "c", 2 "i", 2 "a". For each "i" and "a" you have a probability of 1, while for "t" and "c" it's 0. ((0*(4+4))+(1*(2+2)))/12=(0+4)/12=4/12=0,3333
 » 3 years ago, # |   -72 The comment is hidden because of too negative feedback, click here to view it
 » 3 years ago, # |   0 why div2c should be so harder than div2d? and have the same point can anyone explain this to me?! :|
•  » » 3 years ago, # ^ |   0 I personally found 2C pretty intuitive--just two important observations: that you should rescale so that you're working with zeroes, ones, and twos (or some other three values, but these work best with the array setup), and that you should either transform pairs of ones into a zero and a two or sets of zeroes and twos into pairs of ones, whichever is more advantageous. There might be some alternative solution you could come up with that doesn't work so well, though--I agree that D was quite a bit easier, but I don't think it's too unreasonable, especially considered they were worth the same amount of points.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 i used those observations but i got WA on testcase 119 (:D). but anyway I spend 2 time more than div2E on this problem maby it shows that the imlementation was a bit awkwark.
 » 3 years ago, # |   0 hey can someone plzz help me to find bug in my code for Div2(D) , i am getting wrong answer for 12th pretest. solution link : http://codeforces.com/contest/931/submission/35945047
 » 3 years ago, # |   +25 For those who still wonder what inflorescence is :DDefinition:a : the mode of development and arrangement of flowers on an axisb : a floral axis with its appendages; also : a flower cluster Picture
 » 3 years ago, # |   +14 I think is better to use plain English for description when you are not good at it.
 » 3 years ago, # | ← Rev. 2 →   0 Too amazing submission... for C problems, because he inserted all elements into set and got them to vector afterwards sorted the vector!
 » 3 years ago, # | ← Rev. 2 →   0 http://codeforces.com/contest/931/submission/35943874 got the wrong answer on Laboratory problem (C)...... what is the best way to solve this que.
•  » » 3 years ago, # ^ |   0 6 1 2 2 2 2 3Answer:2 1 1 1 3 3 3
•  » » » 3 years ago, # ^ | ← Rev. 3 →   0 but its already mentioned in the question that it's guaranteed that the difference between max and min is 2.
•  » » » » 3 years ago, # ^ |   0 6 in the first line is the number of numbers in the input. 2 in the 3rd line is the number of differences between the input and output.They should have been on different lines to be more clear.
•  » » » » 3 years ago, # ^ |   0 He meantInput61 2 2 2 2 3Output21 1 1 3 3 3
 » 3 years ago, # |   0 Can anybody explain div2 F
•  » » 3 years ago, # ^ | ← Rev. 2 →   +7 So other people have been saying that they've seen this problem before, but I haven't, so I'll try to explain it as if you haven't seen it before either.First thing's first, we notice that if a point is not in all segments, that is equivalent to saying that you can find two segments that are disjoint (draw a picture, you will see why this is true).Next thing, we notice that if the number of segments decreases and then increases, there must be a pair of disjoint intervals (that is, Sasha is sure Teodor isn't lying). Let's look at sample test 2 to see what I mean. If you were to query the number of segments at each point going from left to right, you would get 1 2 2 1 2 2. Because at points 3, 4, and 5, the queries are 2, 1, and 2, that is, they go down and then up, so we know that there is some interval that ends at 3 and some other interval that starts at 5, so we have two disjoint intervals, and Sasha is sure there is a point that is not in all intervals. HOWEVER, if we were to only query points 1, 2, 3, 5, and 6, Sasha's knowledge of the above array would be 1 2 2 _ 2 2. If the blank was filled in with a 2, he still could not tell whether Teodor was lying. If you play around with the numbers more, you'll see that this is the case for any non-increasing sequence, non-decreasing sequence, and unimodal sequence. For example, other arrays like [1 _ _ 3 _ 5 6], [8 _ 2 2 _ 1], or [1 2 4 _ 6 _ _ 2 1] would not give Sasha enough information to tell whether Teodor is lying.Thus, we can reformulate the question as follows: what is the longest unimodal subsequence of the array a, where a is the array such that ai is the number of intervals at index i.This is easily solvable if you know LIS algorithm, since we just find LIS at each index, and LDS at each index, and test each possible point to be the peak, which will be linear, making the whole thing . Also, constructing the array a is easily done in linear time, since we know all the segments in advance, so we can just increment left endpoints, decrement 1 past right endpoints, and calculate partial sums to get a.My code: 35953013
•  » » » 3 years ago, # ^ |   0 I still don't get why we can't tell Teodor is not lying if we see 1 2 2 _ 2. My reasoning is we know there is a point that is only contained in one interval and a point that is contained in two intervals. Therefore the point contained in one interval cannot be contained in all intervals.
•  » » » » 3 years ago, # ^ |   0 What you've shown is that there exists one point that does not belong to all intervals. What we're trying to show is that all points do not belong to all intervals.For 1 2 2 _ 2, this could be created by the intervals [1, 5], [2, 3], and [5, 5], or it could be created by [1, 5], [2, 5]. In the first case, Teodor is not lying, because all points do not belong to all intervals. In the second case, there are several points that belong to all intervals.
•  » » » » » 3 years ago, # ^ |   0 Thanks. I misinterpreted what the question was asking.
•  » » » 3 years ago, # ^ |   +3 Thanks! Your explanation and submission were really helpful
 » 3 years ago, # |   0 can someone plz tell me what is wrong in my code for E https://ide.geeksforgeeks.org/yLo7pWenjV
 » 3 years ago, # |   +10 Watching Messi's brilliant free kick while coding and making a stupid mistake in indices results in wrong answer on last test for Div2/E :)
•  » » 3 years ago, # ^ | ← Rev. 2 →   +4 Heck, look on the bright side, if that was a WA on Div2B, it would be truly ironic for you :-P
 » 3 years ago, # |   +26 wow i have 211 rating now
•  » » 3 years ago, # ^ |   +79 Onwards to get 212. How hard can it be, right?
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Impossible
•  » » » » 3 years ago, # ^ |   +10 Don't tell tourist!
•  » » » 3 years ago, # ^ |   -15 That was not funny :)
 » 3 years ago, # | ← Rev. 2 →   +3 For Div1-C Sasha should not be sure that an point exists that does not belong to all segments. So naturally I thought that if there are 0 segments at a point Sasha cannot know about it because then that point belongs to no segments so definitely it cannot belong to all segments. So I didn't include such points in the count and got a wrong answer. Am I interpreting the question wrongly?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +5 Yes, it asks for the max. number of queries such that you can't know that there is no point that is covered by all segments. Not whether there is one point that is not covered by all segments.
•  » » » 3 years ago, # ^ |   0 Ah my bad, I get it now.The confusing language didn't help either :(
•  » » 3 years ago, # ^ |   0 I made the same error and wasted thirty minutes on that. The zeroes can count for the same reason yassin described.
 » 3 years ago, # |   -18 The problems didn't really have unique Ideas. Add "Bad Grammar" to it. It was really hard to understand the problems' english.
 » 3 years ago, # |   -8 Here's a clarification for Div. 2 E if anyone else had trouble interpreting it: After being given the string and a character, we want to choose a shift in the index for each letter that gives us the highest probability of being able to uniquely determine what the k was. For example, in the third sample, if the randomly selected character was an 'a', then if we look at the character two spaces to the left and it is also an 'a', then we know that the first 'a' is in the 4th character in the original string. This turns out to be maximal, and if we get a 'b', then we cannot determine the shift. So, our strategy will basically work for 1 character out of 10, so the probability is 0.1. So, we look at all possible indices and for each distinct letter ('a', 'b', etc), we find the shift that gives us the highest number of letters that only appear once.35950009
 » 3 years ago, # |   +7 Editorial?
 » 3 years ago, # |   +1 Are there any other problems similar to Div 2 D? I think problem D is very tricky, so I want to practice more like that. Thanks
 » 3 years ago, # |   +5 How to solve Div.1 D ?
•  » » 3 years ago, # ^ |   +20 Firstly, if a black stone has the same parity as the white stone (in chessboard-style colouring), then it can never block the white stone. So the problem can be split into two separate subproblems by parity.A possible strategy for white is to always move to the right. So for black to win, there must be a black stone that can intercept white on the right i.e. for which xb — xw > abs(yb — yw). Similarly, there must be black stones which can intercept white on the left, top and bottom. It is then not too hard to prove that these four stones can keep white boxed in and block it in finite time. So one needs to count the number of places white could start that are boxed in on the four sides.This can be done by rotating the problem by 45° and then using a line sweep to count the number of position for each y value. With the right data structure (a multiset in my case) it takes O(N log N) time.
•  » » » 3 years ago, # ^ |   0 Thanks a lot, I've understand the algorithm.
•  » » » 3 years ago, # ^ |   0 Can you share the reasoning for your first statement?
 » 3 years ago, # |   +18 Problem E is just straightforward segment tree.
•  » » 3 years ago, # ^ |   0 It can be solved even without segment tree, but with queues ))0)0
•  » » 3 years ago, # ^ |   0 Can you explain your approach? Did you use coordinate compression?
 » 3 years ago, # |   +46
•  » » 3 years ago, # ^ |   0 This is the 2nd time I see you reporting this guy, and the 3rd time I've seen him being reported.Wondering if he just simply prevailed like that?
•  » » 3 years ago, # ^ |   +5 KAN, MikeMirzayanov what's going on with this? These guys stole rating from other participants, who placed behind them — for example me. It is also not the first time they were reported. Why is there no action from codeforces against them?
 » 3 years ago, # |   +14 When will the tutorial be available?
 » 3 years ago, # | ← Rev. 2 →   -53 Div2F / Div1C was easy to solve using google. Just search "longest increasing subseqence" and you will get ready code.Russians could open, for example, this site and get code from there (minor change and it it adapted for task): http://e-maxx.ru/algo/longest_increasing_subseq_logAlso task on this algorithm was on ACM semifinal 2014.P.S. More minuses, more.. Of course, I did not say something cool and did not posted any (stupid) funny picture, I should be punished :)
•  » » 3 years ago, # ^ |   +47 I think that the main difficulty of this problem is realizing that answer is longest increasing-decrasing sequence, not implementing it.
•  » » » 3 years ago, # ^ |   0 I realized it at once after I drew 2-nd example on the paper. Tried to code something on my own, then google this algorithm and get up with this task after I saw search results.Interesting task, I am not trying to prove that is was bad or boring, but authors could confuse it a bit more to make real F problem.
•  » » » » 3 years ago, # ^ |   0 I think you are professional. Because when I solved this problem, most of the time I spent on searching and substantiating the idea, and only 2-3 minutes on implementation of all of this. So, for me this problem is more difficult in understanding the idea than in implementing the solution.
•  » » » » » 3 years ago, # ^ | ← Rev. 3 →   0 That's why you are professional programmer, but not me.And that's actually why I wrote about it. Participiants who know about this algorithm implemented idea faster than others, who spent more time on making up logic/googling (or did not solve it at all, as me).But I really understood it fast.Do not ironize about it.
•  » » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 So, are you saying that people that knew how to implement algorithm implemented it faster than those who didn't? Like... really? I'm lost :)
 » 3 years ago, # |   0 Pls upload the editorial...
 » 3 years ago, # |   0 Please someone tell me what is wrong with this solution. My idea is that: if max-min==2, then for each pair of (max,min) i substitute both the elements of this pair by min+1. Here is my submission: link
•  » » 3 years ago, # ^ |   +5 what about replace 2 numbers min+1 with min and max?
•  » » » 3 years ago, # ^ |   0 Okay this case I was missing. But does this mean, for max-man==2 (max,min)->(min+1,min+1) ----case(1) (min+1,min+1)->(min,max) ----case(2) Do I handle case1 and case2 seprately and print the minimum one? After you point out the mistake I did it this way, but same I am getting error in 11 tc
•  » » » » 3 years ago, # ^ |   0 You should check what case will be better and apply it. With case 2 you should also check this: you can only apply this case if "max" is in the original array, because the bounds condition. Maybe my submission helps you
 » 3 years ago, # |   +3 Please add editorial. It is very much needed now
 » 3 years ago, # |   +5 Is there any idea about div1 E? Thank you.
•  » » 3 years ago, # ^ |   +11 let's imagine that one of sides of coin is 0, other is 1. First of all you need to compress coordinates. Then try to develop some kind of dynamic programming approach. All line will be divided to segments. dp[i][j] — equals to combinations for first i segments j — it is five states. There three types of segments "ones" — segments that consists of only 1; "zeros" — segments that consists of only 0; "zeroones" — segments that consists of 1 and 0. Let's describe our states. 0 state — it is state where last segments is "ones" and before some "ones" it have "zeros" segment. For example this combination is described with this state (...any segments... , "zeros", "ones", ..., "ones"). 1 state — where last is "zeros" and before some "zeros" it have "ones"; 2 state — last "ones" and before some "ones" it have "zeroones"; 3 state — last "zeros" and before some "zeros" it have "zeroones"; 4 state — last is "zeroones"; Transitions is obvious. Also you must store for 0 — 4 states coordinates where the last segment of second type was (for example for 0 state first type is "ones" second typed is "zeros", for 3 state first type is "zeros" second type is "zeroones". And when you have coordinate of end of some segment (from queries) that requires for example 1 you need to delete all combinations with states 1 and 3 that have coordinate of last segment of second type strictly less than L coordinate of current segment(from queries). For this purpose you can used four queues with pairs(last_coord_of_second_type, combinations). For details see my solution Sorry for my English.
•  » » » 3 years ago, # ^ |   0 Thank you very much! I'm reading your post right now.
•  » » 3 years ago, # ^ |   0 For me it is much easier than div1 D
•  » » » 3 years ago, # ^ |   0 "you need to delete all combinations with states 1 and 3 that have coordinate of last segment of second type strictly less than L coordinate of current segment(from queries). "I think that the hard part for this problem to me is how to manipulate any specific regions satisfying some states. I just want to make clear of "How to calculate any specific regions instead of regions from starting point".
•  » » » » 3 years ago, # ^ |   0 Can you describe your question in more details
•  » » » » » 3 years ago, # ^ |   0 I've understood the general idea in your code. It's the part "function ers()" in your code that is most tough for me to understand clearly and completely. For example, how can it be guaranteed that a queue will work correctly, not missing any part that need to subtract. For this part, I haven't got that clear. And another crucial point is, the idea to divide situations with "111.." at last into situations with "0111..", and it can be shown there's no aftereffect (for segment before 0, it's guaranteed by definition of dp[], for segment after 0, it's guaranteed by containing at least one '1' and one '0'). This part is something I haven't thought of, very nice idea!
•  » » » » » » 3 years ago, # ^ |   0 Ok, I will try to describe how things goes in function ers(). First of all purpose of this function is to delete some combinations from witch we can't update our future states. It happens because when we have segment L, R that requires "1" and we are going through coordinate R, in future steps we can't update our states with dp[0] where coordinate of last '0' is less than L because in this case we will get that all our segment [L, R] will be covered with "0" (it is invalid), therefore we subtract from dp[0] such values than responsible for dp[0] and their last "0" less than L. Why do we can use queue? Because we erase values that is less than something and add values that is bigger than every value in queue now (there "value" means coordinate of last secont type)
•  » » » » » » » 3 years ago, # ^ |   0 "to delete some combinations from witch we can't update our future states." I had stuck on this point a long time, not being aware of any ways to remove this aftereffect. "therefore we subtract from dp[0] such values than responsible for dp[0] and their last "0" less than L."And I wanted to solve this too. In your function ers(), you simply subtract dp[] with q.front().second, and pop it out, so why is that correct? /*I think that in your code, for any segment that has been processed, it's left point is left to the q.front().first, so to gaurantee the value is just invalid for the processed segment and valid for others processed before, and how to deal with segments before*/ Ok I'll try to use pictures instead, because I find that I can't explain my thought very well just by words. ^_^
•  » » » » » » » 3 years ago, # ^ |   0
•  » » » » » » » » 3 years ago, # ^ |   0 I guess that the part in purple color is processed by segment before, also by ers(), but can't make it very clear.
•  » » » » » » » » » 3 years ago, # ^ |   0 Eventually, that purple color situation do not need to concern about, they just won't exist.
•  » » » » » » » » 3 years ago, # ^ |   0 and there is still situation that q.front().first is right to the left point of processing segment.
•  » » » » » » » » » 3 years ago, # ^ |   0 And for this situation, just ignore it as well, as your ers() won't process anything too.
•  » » » » » » » 3 years ago, # ^ |   0 OK, I think I've make every situations clear! Oh it's fantastic to consider using queue, and indeed it can hold any of those complicate situations. Thank you!
•  » » » » » 3 years ago, # ^ |   0 And I'm studying this code http://codeforces.com/contest/930/submission/35970918. It seems he doesn't use structures similar to queues.
•  » » » 3 years ago, # ^ |   0 At first, I spent a very long time in thinking about Inclusion Exclusion Principle and Probability Theory, and wasted a very long time.
 » 3 years ago, # |   +8 When will the editorial be published ?
 » 3 years ago, # |   +11 Tutorial is up. Link
 » 3 years ago, # |   0 Can't understand the problem.. Descriptions are so suck.