Yes.

Firstly, You had better ask "Is it DATED?" then you didn't get many down votes!

Its still there.

I don't know why your comment get down voted ?

The contest overlaps with Arsenal's match

No...the Barcelona match overlaps with the contest

That would be Mike thanking Mike.

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!

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)

Div-1 A has a pretty good statement. I think you meant Div-1 B, which fits well your description.

It's not the best English, but everything seemed pretty clear even if you had to reread once

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.

By knowing it in advance?

Maybe because he is not stupid :?

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))

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?

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).

My hack was 8 4 5

Answer should be final

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.

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

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.

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.

Let (c₁, ..., c_m) 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 l_i ≤ x ≤ r_i for all intervals in the set?

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

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

You meant B?

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:

6
1 3 2 2 2 2

Answer should be:

2
1 1 1 3 3 3

That's when you stop reading and look at the tests and explanations.

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

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 

well they have the same score.

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.

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.

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...

Why do you think it's 0.5?

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

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.

6 1 2 2 2 2 3

Answer:

2 1 1 1 3 3 3

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 a_i 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

Heck, look on the bright side, if that was a WA on Div2B, it would be truly ironic for you :-P

Onwards to get 2¹². How hard can it be, right?

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.

I made the same error and wasted thirty minutes on that. The zeroes can count for the same reason yassin described.

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.

It can be solved even without segment tree, but with queues ))0)0

Can you explain your approach? Did you use coordinate compression?

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?

I think that the main difficulty of this problem is realizing that answer is longest increasing-decrasing sequence, not implementing it.

what about replace 2 numbers min+1 with min and max?

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.