Всем привет!
Уже сегодня, 4 марта 2018 года пройдет финальный раунд олимпиады для школьников Технокубок! Участники, которые стали лучшими на четырех отборочных раундах, сегодня поборются за первые места сразу на нескольких площадках. Финальный раунд стартует в 11:30 по московскому времени.
Окончательные результаты финального раунда.
Для тех, кто хочет посоревноваться на тех же задачах, будет проведено два обычных раунда Codeforces: один для первого, другой для второго дивизиона. Раунды начнутся в 18:35 по московскому времени, не пропустите!
Конечно, если вы участвуете в финальном раунде Технокубка, то вы не можете участвовать в раунде вечером.
Задачи раунда готовили Endagorion, komendart, rationalex, AndreySergunin, fcspartakm, MikeMirzayanov и я. Также спасибо за тестировании demon1999, Belonogov, vintage_Vlad_Makeev, adedalic, budalnik, GreenGrape, Neon. Отдельная благодарность vintage_Vlad_Makeev за помощь в проведении раунда на Codeforces!
P.S. По причине проведения соревнования некоторая функциональность на Codeforces может быть отключена.
Удачи!
UPD: Поздравляем победителей Технокубка!
Поздравляем победителей раундов Codeforces:
Первый дивизион:
Второй дивизион:
is it rated?
Yes.
Firstly, You had better ask "Is it DATED?" then you didn't get many down votes!
"Is it RATED?", not "Is it DATED?".
So why”Codeforces Round #468”disappeared now?In”Contests”
Its still there.
Hope the problem statements are as short as the announcement.
I don't know why your comment get down voted ?
I think the reason is that he copied the comment from another contest blog.(#467)
It is actually commented everywhere
I don't know.
Hope to see some quality problems A & B for <1200 contestants like me
В технокубке уже прошли систесты?
The contest overlaps with Barcelona's match
The contest overlaps with Arsenal's match
Wenger Out
not that Arsenal, dude
No...the Barcelona match overlaps with the contest
*Forgets to thank Mike and Polygon*
*Mike TRIGGERED*
That would be Mike thanking Mike.
Because of the Olympiad, some Codeforces features may be disabled today. ??
I wish GOOD HACKS for all!
I think Problems Scoring is not important nowadays :|
Clashes with IEM Katowice finals.
Will #468 be rated ?
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!
I am following your advice. Let's see how it goes !
The one who wrote problem Div-2 D has very bad English skills (hardly understood what the problem setter had in mind).
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)
Well maybe. As you can see from my rating I haven't even approached that problem.
what do you want to say in D not able to understand bad english.
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).
Div-1 A has a pretty good statement. I think you meant Div-1 B, which fits well your description.
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.
It's not the best English, but everything seemed pretty clear even if you had to reread once
When it comes to languages, my definition of pretty clear never coincides with German speakers' xD
I'm a native english speaker and I thought it was unclear, especially for C
RIP rating...
Why can't I see any hacks? Were pretests particularly thorough?
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.
How did NotSoStupid manage to solve B in 20 seconds?
By knowing it in advance?
I guess so
Maybe because he is not stupid :?
Funny
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))
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.
That is how it is in Div 2? how about stop crying?
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?
Longest increasing subsequence with segtree is n log n
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)
just find for a position pos longest increasing that ends there, and longest decreasing that starts there
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.
Can be done in an even easier way using only vector+lower_bound.
Refer here
still only one solution failed :(
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).
What is the hack for B?
My hack was 8 4 5
Answer should be final
Thanks :)
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.
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.
I dont understand you if the first letter is "a" and you choose third letter then you have for example: aabaabbbbb aabbbbbaab
which both have "a" in 1st position and "b" in 2nd position so the cycle is not uniquely determined.
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
All the possible shifts were
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:
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.
Thank you! I finally understood.
a a b a a b b b b b
a b a a b b b b b a
a a b b b b b a a b
a b b b b b a a b a
Here 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 :)
seriously horrible long statements.
Could someone explain what problem Div1C is asking for :3
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.
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?
yes, you want to find combination of longest nondecreasing subsequence to a point + longest nonincreasing subsequence after the point
ohh! yeah!! i forgot that non increasing part!!!!!! shit!!
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?
How to solve task D (div 2)?
Count the number of tree levels with odd number of nodes.
answer is the number of heights such that the number of apples on that height is odd
But then in testcase #3, shouldn't answer be 8?
no because there's only 4 heights
draw the tree and you will see (p_i is the parent of i+1)
How to prove that?
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
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
I get it now, and feel terribly stupid :P btw thanks :)
how the answer for teoder is not lying for 2nd case is 5
Hack for B: 8 4 5
You meant B?
Yes, edited!. Thanks
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 -_-
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
6 1 2 2 2 2 3
yours -> 4, 222222 answer -> 2, 111333
Try with:
Answer should be:
Div-2 D description was totally weird.. I couldn't tell what it says. ;(
does the writer of the problem D statement even speak english? that text is totally weird...
I think The problem description should be more concise >.<
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
Div1C has the most confusing statement I've ever seen. Setters should really be careful when translating.
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![](/predownloaded/c0/ce/c0ce792eaea95ee0a1755dcc498d5eb35836b5e4.jpg)
That's when you stop reading and look at the tests and explanations.
Please help me with this.
Div 2, problem C, test 3: Input:
7
-10 -9 -10 -8 -10 -9 -9
my output was:
5
-8 -8 -8 -9 -9 -9 -10
I think this should be right but I am getting wrong answer.
The sum of the two sequences are different, so their averages are different, which violates the first constraint.
the sum of your numbers is -61 but it should be -65
so, the total number of equal measurements in your answer is 6 not 5.
В Div1D разбил все фишки на две части, в зависимости от четности (x + y). И решал задачу неазвисимо для двух частей, сделав преобразование ((x + y) / 2, (x - y) / 2). Я перебираю вертикали и для каждой вертикали прибавляю к ответу число min(HiLeft, HiRight) - max(LoLeft, LoRight) — где HiLeft, HiRight, LoLeft, LoRight — самая высокая и самая низкая точки справа и слева от вертикали соответственно. Валится на ВА6, подскажите в чем ошибка?
UPD: Разобрался! Как всегда невнимательность :( Вот AC код http://codeforces.com/contest/930/submission/35949982 Кстати мне кажется, что это решение даже проще чем те, что видел у многих, хотя идея та же.
Too UNCLEAR problems
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.
well they have the same score.
Problem A on div1 was actually div2D, and div1 has only 5 problems
Well C is just implementation, but for D you need to know some tree traversal algorithm, i think that's why it was chosen.
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.
No, it wouldn't. I was so glad when I read Div2C and realized that it's not in Div1.
Too unlucky contest for both Contribution and Rating!
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.
same here
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...
Ouch, heck....
Oh, and Div1C, after reading a few first lines, knowing I had only 10 minutes left, I instantly gave up.
Can someone explain why 2nd example's output of Div2 E is 0,333333? I thought it should be 0,5.
Why do you think it's 0.5?
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
The probability that you get 'a' or 'c' however is 4/12, as explained in Renaats' comment below.
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 победителя, 56 призеров и победителей вместе.
why div2c should be so harder than div2d? and have the same point can anyone explain this to me?! :|
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.
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.
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
For those who still wonder what inflorescence is :D
Definition:
a : the mode of development and arrangement of flowers on an axis
b : a floral axis with its appendages; also : a flower cluster
I think is better to use plain English for description when you are not good at it.
Too amazing submission... for C problems, because he inserted all elements into set and got them to vector afterwards sorted the vector!
http://codeforces.com/contest/931/submission/35943874 got the wrong answer on Laboratory problem (C)...... what is the best way to solve this que.
6 1 2 2 2 2 3
Answer:
2 1 1 1 3 3 3
but its already mentioned in the question that it's guaranteed that the difference between max and min is 2.
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.
He meant
Input
6
1 2 2 2 2 3
Output
2
1 1 1 3 3 3
Can anybody explain div2 F
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
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.
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.
Thanks. I misinterpreted what the question was asking.
Thanks! Your explanation and submission were really helpful
can someone plz tell me what is wrong in my code for E https://ide.geeksforgeeks.org/yLo7pWenjV
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 :)
Heck, look on the bright side, if that was a WA on Div2B, it would be truly ironic for you :-P
wow i have 211 rating now
Onwards to get 212. How hard can it be, right?
Impossible
Don't tell tourist!
That was not funny :)
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?
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.
Ah my bad, I get it now.
The confusing language didn't help either :(
I made the same error and wasted thirty minutes on that. The zeroes can count for the same reason yassin described.
The problems didn't really have unique Ideas. Add "Bad Grammar" to it. It was really hard to understand the problems' english.
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
Editorial?
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
How to solve Div.1 D ?
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.
Thanks a lot, I've understand the algorithm.
Can you share the reasoning for your first statement?
Problem E is just straightforward segment tree.
It can be solved even without segment tree, but with queues ))0)0
Can you explain your approach? Did you use coordinate compression?
Triple cheating. Ali_Pi , .Ali. , best.code
Someone was using 3 accounts(!!!!) during the contest
Problem A:
http://codeforces.com/contest/930/submission/35929332
http://codeforces.com/contest/930/submission/35929703
http://codeforces.com/contest/930/submission/35930793
Problem B:
http://codeforces.com/contest/930/submission/35935457
http://codeforces.com/contest/930/submission/35934946
http://codeforces.com/contest/930/submission/35935823
Problem C
http://codeforces.com/contest/930/submission/35937257
http://codeforces.com/contest/930/submission/35937558
http://codeforces.com/contest/930/submission/35937842
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?
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?
When will the tutorial be available?
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_log
Also 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 :)
I think that the main difficulty of this problem is realizing that answer is longest increasing-decrasing sequence, not implementing it.
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.
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.
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.
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 :)
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
what about replace 2 numbers
min+1
withmin
andmax
?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
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
Please add editorial. It is very much needed now
Is there any idea about div1 E? Thank you.
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.
Thank you very much! I'm reading your post right now.
For me it is much easier than div1 D
"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".
Can you describe your question in more details
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!
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)
"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. ^_^
I guess that the part in purple color is processed by segment before, also by ers(), but can't make it very clear.
Eventually, that purple color situation do not need to concern about, they just won't exist.
and there is still situation that q.front().first is right to the left point of processing segment.
And for this situation, just ignore it as well, as your ers() won't process anything too.
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!
And I'm studying this code http://codeforces.com/contest/930/submission/35970918. It seems he doesn't use structures similar to queues.
At first, I spent a very long time in thinking about Inclusion Exclusion Principle and Probability Theory, and wasted a very long time.
When will the editorial be published ?
Tutorial is up. Link
Can't understand the problem.. Descriptions are so suck.