There are two ways to solve this problem.

The first is to hard-code numbers of days in months, check the first day of the year and then iterate over days/months — http://ideone.com/4TYPCc

The second way is to check all possible cases by hand. The 2016 consists of 52 weeks and two extra days. The answer for "x of week" will be either 52 or 53. You must also count the number of months with all 31 days and care about February. http://ideone.com/Bf9QLz

611B - New Year and Old Property

Each number with exactly one zero can be obtained by taking the number without any zeros (e.g. 63_{10} = 111111_{2}) and subtracting some power of two, e.g. 63_{10} - 16_{10} = 111111_{2} - 10000_{2} = 101111_{2}. Subtracting a power of two changes one digit from '1' to '0' and this is what we want. But how can we iterate over numbers without any zeros? It turns out that each of them is of form 2^{x} - 1 for some *x* (you can check that it's true for 63_{10}).

What should we do to solve this problem? Iterate over possible values of *x* to get all possible 2^{x} - 1 — numbers without any zeros. There are at most values to consider because we don't care about numbers much larger than 10^{18}. For each 2^{x} - 1 you should iterate over powers of two and try subtracting each of them. Now you have candidates for numbers with exactly one zero. For each of them check if it is in the given interval. You can additionally change such a number into binary system and count zeros to be sure. Watch out for overflows! Use '1LL << x' instead of '1 << x' to get big powers of two. http://ideone.com/Kfu8sF

How would we solve this problem in *O*(*wh* + *q*) if a domino would occupy only one cell? Before reading queries we would precalculate *dp*[*r*][*c*] — the number of empty cells in a "prefix" rectangle with bottom right corner in a cell *r*, *c*. Then the answer for rectangle *r*1, *c*1, *r*2, *c*2 is equal to *dp*[*r*2][*c*2] - *dp*[*r*2][*c*1 - 1] - *dp*[*r*1 - 1][*c*2] + *dp*[*r*1 - 1][*c*1 - 1]. We will want to use the same technique in this problem.

Let's separately consider horizontal and vertical placements of a domino. Now, we will focus on horizontal case.

Let's say that a cell is good if it's empty and the cell on the right is empty too. Then we can a place a domino horizontally in these two cells. The crucial observation is that the number of ways to horizontally place a domino is equal to the number of good cells in a rectangle *r*1, *c*1, *r*1, *c*2 - 1.

You should precalculate a two-dimensional array *hor*[*r*][*c*] to later find the number of good cells quickly. The same for vertical dominoes. http://ideone.com/wHsZej

611D - New Year and Ancient Prophecy

By {*x*... *y*} I will mean the number defined by digits with indices *x*, *x* + 1, ..., *y*.

Let *dp*[*b*][*c*] define the number of ways to split some prefix (into increasing numbers) so that the last number is {*b*... *c*} We will try to calculate it in *O*(*n*^{2}) or . The answer will be equal to the sum of values of *dp*[*i*][*n*] for all *i*.

Of course, *dp*[*b*][*c*] = 0 if *digit*[*b*] = 0 — because we don't allow leading zeros.

We want to add to *dp*[*b*][*c*] all values *dp*[*a*][*b* - 1] where the number {*a*... *b* - 1} is smaller than {*b*... *c*}. One crucial observation is that longer numbers are greater than shorter ones. So, we don't care about *dp*[*a*][*b* - 1] with very low *a* because those long numbers are too big (we want {*a*... *b* - 1} to be smaller than our current number {*b*... *c*}). On the other hand, all *a* that (*b* - 1) - *a* < *c* - *b* will produce numbers shorter than our current {*b*... *c*}. Let's add at once all *dp*[*a*][*b* - 1] for those *a*. We need . Creating an additional array with prefix sums will allow us to calculate such a sum in *O*(1).

There is one other case. Maybe numbers {*a*... *b* - 1} and {*b*... *c*} have the same length. There is (at most) one *a* that (*b* - 1) - *a* = *c* - *b*. Let's find it and then let's compare numbers {*a*... *b* - 1} and {*b*... *c*}. There are few ways to do it.

One of them is to store hashes of each of *n*·(*n* + 1) / 2 intervals. Then for fixed *a*, *b* we can binary search the first index where numbers {*a*...} and {*b*... } differ. http://ideone.com/Rrgk8T. It isn't an intended solution though. Other way is to precalculate the same information for all pairs *a*, *b* with dynamic programming. I defined *nxt*[*a*][*b*] as the lowest *x* that *digit*[*a* + *x*] ≠ *digit*[*b* + *x*]. Now, either *nxt*[*a*][*b*] = *nxt*[*a* + 1][*b* + 1] + 1 or *nxt*[*a*][*b*] = 0. http://ideone.com/zczsc3

611E - New Year and Three Musketeers

The answer is - 1 only if there is some criminal stronger than *a* + *b* + *c*. Let's deal with this case and then let's assume that *a* ≤ *b* ≤ *c*.

Let's store all criminal- s in a set (well, in a multiset). Maybe some criminals can be defeated only by all musketeers together. Let's count and remove them. Then, maybe some criminals can be defeated only by *b* + *c* or *a* + *b* + *c* (no other subsets of musketeers can defeat them). We won't use *a* + *b* + *c* now because it's not worse to use *b* + *c* because then we have the other musketeer free and maybe he can fight some other criminal. Greedily, let's remove all criminals which can be defeated only by *b* + *c* and at the same time let *a* defeat as strong criminals as possible. Because why would he rest?

Now, maybe some criminals can be defeated only by *a* + *c* or *b* + *c* or *a* + *b* + *c*. It's not worse to use *a* + *c* and to let the other musketeer *b* defeat as strong criminals as possible (when two musketeers *a* + *c* fight together).

We used *a* + *b* + *c*, *b* + *c*, *a* + *c*. We don't know what is the next strongest subset of musketeers. Maybe it's *a* + *b* and maybe it's *c*. Previous greedy steps were correct because we are sure that .

Now in each hour we can either use *a*, *b*, *c* separately or use *a* + *b* and *c*. Let's say we will use only pair *a* + *b* and *c*. And let's say that there are *x* criminals weaker than *a* + *b* and *y* criminals weaker than *c*. Then the answer is equal to . The explanation isn't complicated. We can't be faster than because we fight at most two criminals in each hour. And maybe e.g. *y* (because *c* is weak) so *c* will quickly defeat all *y* criminals he can defeat — and musketeers *a* + *b* must defeat *x* - *y* criminals.

Ok, we know the answer in *O*(1) if we're going to use only *a* + *b* and *c*. So let's assume it (using only these two subsets) and find the possible answer. Then, let's use *a*, *b*, *c* once. Now we again assume that we use only *a* + *b* and *c*. Then we use *a*, *b*, *c* once. And so on.

What we did is iterating over the number of times we want to use *a*, *b*, *c*. http://ideone.com/R3Oy3F

Let's not care where we start. We will iterate over robot's moves.

Let's say the first moves are LDR. The very first move 'L' hits a wall only if we started in the first column. Let's maintain some subrectangle of the grid — starting cells for which we would still continue cleaning. After the first move our subrectangle lost the first column. The second move 'D' affects the last row. Also, all cells from the last row of our remaining subrectangle have the same score so it's enough to multiply the number of cells there and an index of the current move. The third move 'R' does nothing.

Let's simulate all moves till our subrectangle becomes empty. To do it, we should keep the current *x*, *y* — where we are with respect to some starting point. We should also keep *max*_{x}, *max*_{y}, *min*_{x}, *min*_{y} — exceeding value of one of these four variables means that something happens and our subrectangle losts one row or one column.

But how to do it fast? You can notice (and prove) that the second and and each next execution of the pattern looks exactly the same. If we have pattern RRUDLDU and the first letter 'U' affects out subrectangle in the second execution of the pattern, then it will also affect it in the third execution and so on. If and only if.

So, we should simalate the first *n* moves (everything can happen there). Then, we should simulate the next *n* moves and remember all places where something happened. Then we should in loop iterate over these places. Each event will decrease width or height of our subrectangle so the complexity of this part is *O*(*w* + *h*). In total *O*(*w* + *h* + *n*). http://ideone.com/xrU9u2

**CHALLENGE FOR PROBLEM F (CLEANING ROBOT)** — I was considering an alternative version of this problem, harder one. The same constraint for *n* but this time *h*, *w* ≤ 10^{9}. Describe a solution in comments and optionally implement it (it should get AC on this problem, right?). I will mention here the first person to solve this challenge.

We are given a polygon with vertices *P*_{1}, *P*_{2}, ..., *P*_{n}. Let *Poly*(*i*, *j*) denote the doubled area of a polygon with vertices *P*_{i}, *P*_{i + 1}, *P*_{i + 2}, ..., *P*_{j - 1}, *P*_{j}. While implementing you must remember that indices are in a circle (there is 1 after *n*) but I won't care about it in this editorial.

We will use the cross product of two points, defined as *A* × *B* = *A*.*x*·*B*.*y* - *A*.*y*·*B*.*x*. It's well known (and you should remember it) that the doubled area of a polygon with points *Q*_{1}, *Q*_{2}, ..., *Q*_{k} is equal to *Q*_{1} × *Q*_{2} + *Q*_{2} × *Q*_{3} + ... + *Q*_{k - 1} × *Q*_{k} + *Q*_{k} × *Q*_{1}.

Let *smaller* denote the area of a smaller piece, *bigger* for a bigger piece, and *total* for a whole polygon (cake).*smaller* + *bigger* = *total**smaller* + (*smaller* + *diff*) = *total**diff* = *total* - 2·*smaller* (the same applies to doubled areas)

And the same equation with sums:

where every sum denotes the sum over possible divisions.

In *O*(*n*) we can calculate *total* (the area of the given polygon). So, the remaining thing is to find and then we will get (this is what we're looking for).

For each index *a* let's find the biggest index *b* that a diagonal from *a* to *b* produces a smaller piece on the left. So, .

To do it, we can use two pointers because for bigger *a* we need bigger *b*. We must keep (as a variable) the sum *S* = *P*_{a} × *P*_{a + 1} + ... + *P*_{b - 1} × *P*_{b}. Note that *S* isn't equal to *Poly*(*a*, *b*) because there is no *P*_{b} × *P*_{a} term. But *S* + *P*_{b} × *P*_{a} = *Poly*(*a*, *b*).

To check if we should increase *b*, we must calculate *Poly*(*a*, *b* + 1) = *S* + *P*_{b} × *P*_{b + 1} + *P*_{b + 1} × *P*_{a}. If it's not lower that then we should increase *b* by 1 (we should also increase *S* by *P*_{b} × *P*_{b + 1}). When moving *a* we should decrease *S* by *P*_{a} × *P*_{a + 1}.

For each *a* we have found the biggest (last) *b* that we have a smaller piece on the left. Now, we will try to sum up areas of all polygons starting with *a* and ending not later than *b*. So, we are looking for *Z* = *Poly*(*a*, *a* + 1) + *Poly*(*a*, *a* + 2) + ... + *Poly*(*a*, *b*). The first term is equal to zero but well, it doesn't change anything.

Let's talk about some intuition (way of thinking) for a moment. Each area is equal so the sum of cross products of pairs of adjacent (neighboring) points. We can say that each cross product means one side of a polygon. You can take a look at the sum *Z* and think — how many of those polygons have a side *P*_{a}*P*_{a + 1}? All *b* - *a* of them. And *b* - *a* - 1 polygons have a side *P*_{a + 1}*P*_{a + 2}. And so on. And now let's do it formally:

*Poly*(*a*, *a* + 1) = *P*_{a} × *P*_{a + 1} + *P*_{a + 1} × *P*_{a}*Poly*(*a*, *a* + 2) = *P*_{a} × *P*_{a + 1} + *P*_{a + 1} × *P*_{a + 2} + *P*_{a + 2} × *P*_{a}*Poly*(*a*, *a* + 3) = *P*_{a} × *P*_{a + 1} + *P*_{a + 1} × *P*_{a + 2} + *P*_{a + 2} × *P*_{a + 3} + *P*_{a + 3} × *P*_{a}

...*Poly*(*a*, *b*) = *P*_{a} × *P*_{a + 1} + *P*_{a + 1} × *P*_{a + 2} + *P*_{a + 2} × *P*_{a + 3} + ... + *P*_{b - 1} × *P*_{b} + *P*_{b} × *P*_{a}

*Z* = *Poly*(*a*, *a* + 1) + *Poly*(*a*, *a* + 2) + ... + *Poly*(*a*, *b*) =

= (*b* - *a*)·(*P*_{a} × *P*_{a + 1}) + (*b* - *a* - 1)·(*P*_{a + 1} × *P*_{a + 2}) + (*b* - *a* - 2)·(*P*_{a + 2} × *P*_{a + 3}) + ... + 1·(*P*_{b - 1} × *P*_{b}) +

+ *P*_{a + 1} × *P*_{a} + *P*_{a + 2} × *P*_{a} + ... + *P*_{b} × *P*_{a}

The last equation is intentionally broken into several lines. We have two sums to calculate.

The first sum is (

*b*-*a*)·(*P*_{a}×*P*_{a + 1}) + (*b*-*a*- 1)·(*P*_{a + 1}×*P*_{a + 2}) + ... + 1·(*P*_{b - 1}×*P*_{b}). We can calculate it in*O*(1) if we two more variables`sum_product`

and`sum_product2`

. The first one must be equal to the sum of*P*_{i}×*P*_{i + 1}for indices in an interval [*a*,*b*- 1] and the second one must be equal to the sum of (*P*_{i}×*P*_{i + 1})·(*i*+ 1). Then, the sum is equal to`sum_product * (b + 1) - sum_product2`

.The second sum is

*P*_{a + 1}×*P*_{a}+*P*_{a + 2}×*P*_{a}+ ... +*P*_{b}×*P*_{a}=*SUM*_*POINTS*×*P*_{a}where*SUM*_*POINTS*is some fake point we must keep and*SUM*_*POINTS*=*P*_{a + 1}+*P*_{a + 2}+ ... +*P*_{b}. So, this fake point's*x*-coordinate is equal to the sum of*x*-coordinates of*P*_{a + 1},*P*_{a + 2}, ...,*P*_{b}and the same for*y*-coordinate. In my code you can see variables`sum_x`

and`sum_y`

.

Implementation. http://ideone.com/RUY5lF

611H - New Year and Forgotten Tree

There are at most *k* = 6 groups of vertices. Each grouped is defined by the number of digits of its vertices.

It can be probed that you can choose one vertex (I call it "boss") in each group and then each edge will be incident with at least one boss. We can iterate over all *k*^{k - 2} possible labeled trees — we must connect bosses with *k* - 1 edges. Then we should add edges to other vertices. An edge between groups *x* and *y* will "kill" one vertex either from a group *x* or from a group *y*. You can solve it with flow or in *O*(2^{k}) with Hall's theorem. http://ideone.com/7KuS1l

I read incorrectly statement of C ;_; and ended up solving wrong problem >.< . How can we tell the number of dominos that can be placed in rectangle r1 c1 r2 c2?

Found that so many people passed D.

What did you do to solve this problem?

(The editorial is really nice, and I wonder if there are any other ideas?)

In D, you've written:

Of course, dp[b][c] = 0 if digit[0] = 0 — because we don't allow leading zeros.Shouldn't it be

digit[b] = 0?sure, thanks

Fast and great tutorial,thanks you!

A — New Year and Days

I didn't read clearly . I think the first day of a week is Sunday... Very pitiful .

After I lock my code and see others,I find the mistake. I want hack myself but can't.

At first i thought it was 2015,but when i checked the calendar and found out the sample was wrong,thank god I did not make a mistake

why this greedy failed for problem e??

if(a+b>c) --> remove as per the previous rules else --> try to remove element less than equal to c, try to remove element less than equal to b ... if element is removed try to remove element closer to a else try to remove element less than a+b

It should work, my code passes doing this greedy. See below for a "proof". (I think it's correct, but not 100% sure)

Ok, so I read your code. You make the following error.

You eliminate everything that if between

c+ 1 anda+bwhich is correct.Afterwards, you ONLY use (

a,b,c) which is wrong. You should instead deletec, then deletea,bif possible, and if not, just deletea+bas it is larger.Example test case that you might fail on:

2 5 6 10 10 10

You'll print 2 (I think?) while the answer is clearly 1.

Thanks..dont know why i overlooked the possibility of same thing for a+b<c in a+b>c case

Alternate approach on E that uses only greedy all the way:

Toss everything in a set. This will make deleting things very easy.

WLOG

a≤b≤c, so thena+b+c≥b+c≥a+c≥max(c,a+b).Therefore, greedy away using

a+b+c, then the pair (b+c,a), then the pair (a+c,b), until the largest element is at mostmax(c,a+b).Now we distinguish 2 cases:

Case 1:

a+b>c. Then greedy using the pair (a+b,c), as the largest elements remaining can only be taken using this pair. Now all remaining elements are at mostc. At this point, we'll fnish as in Case 2.Case 2:

c≥a+b. In other words, all remaining elements are at mostc. Then every time we will take ac, i.e. the largest remaining element. Now we have to decide when to take (a,b) and when to takea+b. At each step, if there is an element that is ≤bin our set, I claim that we might as well take (a,b). The proof is: in the future this element will be taken by something. If it's taken byaorbthat's fine. If it's taken bya+b, we might as well have taken it with aband then used theafor something else. If it's taken byc, you might as well have taken it withb, and letctake any remaining element.So only greedy is enough to finish.

Am I only the guy who solved E with binary search? It seemed for me a bit easier and straightforward than greedy solution. In the search we try to find lowest time musketeers can defeat criminals. For each particular fixed time we use 7 counters (a, b, c, ab, ac, bc, abc) and greedy approach. Iterate through all criminals starting from more strongest and try to assign for each the musketeers squad if possible in the following order: a, b, c, ab, ac, bc, abc. In that case I don't even need to check whether c > ab. My submission

That is still greedy though. Cause you greedily assign them to a, b, c, ab, ac, bc, abc.

Yes, I agree. Bin search + gready.

Could you explain this line:

`if (va + vac + vabc + vab < m && mas[i] <= a) va++;`

I think that`va`

=how many times you useWhy do you sum`(a)`

to defeat criminals.`va, vac, vabc, vab`

together?Because (a) is used in the following team combinations: a, ab, ac and abc. We have separate counter for each group: va, vab, vac, vabc. So, if (a) overall is used less than (m) times, we can use it, otherwise we can't.

Do you mean we can't use

`a`

more than`(m)`

times?Yes. Because

`m`

is the binary search step and it denotes number of hours enough for musketeers to defeat criminals. And`a`

denotes one of the musketeer (weakest one) and it can't spent more than`m`

hours fighting alone or as a part of the team.I get va++ , vb++ and vc++ from previous comments. But I do not understand the next three statements. Mainly the conditional part.

What does this actually check?

" va + vb + vab + vac + vbc + vabc < m "

Hi, I think that, although it passes in the tests, your code gives the wrong answer for the following sample:

3 38 48 72 73 89 97

It answers 3 but the answer is 2

I am sorry, your code is right. I understood the problem wrong.

For problem C, O(10^10) did not pass but it should have passed in 3s. I know solution of O(10^7) exists but why O(10^10) didnt pass? Can anybody tell me how much order can pass in 3s. Solution link: http://codeforces.com/contest/611/submission/15128001

Why do you think 10^10 should have passed in 3 seconds? That is simply too many operations, it is no surprise that it did not pass.

Not to mention that in fact your solution is doing 10^5 * 500 * 500 operations, which is actually 2.5 * 10 ^ 10, so even worse than you are thinking.

I believe 10**8 operations per second is average

There is also a solution with

O(hlogh+wlogw+n) complexity for problem F.nor the lastnelements of the sequence.I've skipped the third part and wrote O(h log hw + w log hw), got TLE. Added inline's — after contest — accepted. >_<

Solved D with string comparison in with suffix automaton and LCA... 15118514

Could someone explain G with more details?

deleted

Seems like invalid memory access in line 47. The indices you use there seem completely mixed up, and in some cases the index may even evaluate to -1.

Cheers!

Could someone tell me why the correct answer for "1 100" is "1" at problem B? I don't really know what's wrong with my solution.

Link: http://codeforces.com/contest/611/submission/15114734

Correct answer is 16. ~~~~~ Participant's output 1 Jury's answer 16 ~~~~~

I have found an alternative solution to problem F, in complexity

O(nlog(n)), like this:First, let's pre-compute the minimum number of moves to get to a certain relative coordinate. We will have 4 arrays,

MinPosX,MinPosY,MinNegX,MinPosX, where for exampleMinPosX[d] is the minimum number of moves after which the coordinateXwill have increased byd. I leave the pre-comp part as an exercise. You can also look at my source below for hints.Let's fix one coordinate (say the row), namely

i. Then, the number of moves is bounded bymin(MinNegY[i],MinPosY[n-i+ 1]) (it is easy to see why). Actually, for a coordinate set (i,j), the value ismin(MinNegY[i],MinPosY[n-i+ 1],MinNegX[j],MinPosX[m-j+ 1]). We have 2 of the values fixed. Now, it is easy to see / prove thatMinNegY,MinPosYare monotonically increasing arrays, so we can binary search where the min transitions fromMinNegX[j] tomin(MinNegY[i],MinPosY[n-i+ 1]) toMinPosX[m-j+ 1]. There are some special cases, where the middle one does not exist.Source code: http://codeforces.com/contest/611/submission/15129711

I have done the same but getting wrong answer

Can you tell me why am i getting wrong answer? http://codeforces.com/contest/611/submission/15130593 Idea is same as yours

In D, Shouldn't it be

nxt[a][b] =nxt[a+ 1][b+ 1] + 1 instead of "-1" Errichto ?Yes, I also have the same question :)

you are right, it should be "+1". Thanks

Thanks. And I'd like to thank you even more for setting up such great contests and finding time to put up such great editorials... Seems surreal how much time you have in a world where people don't even have time for their own families :) ... Have a great new year Errichto !!

In the problem D's solution, I think you should write

`nxt[a][b] = nxt[a+1][b+1] + 1`

instead of`nxt[a][b] = nxt[a+1][b+1] - 1`

. Because you have denoted`nxt[a][b]`

as the lowest number x, such that`digit[a+x] != digit[b+x]`

. Am I right?In problem D , Can someone explain me the use of nxt[a][b] should be nxt[a+1][b+1] or 0 with some example and why do need it ? Thanks.

Why do we need it? When we compare two numbers of the same length, e.g. 234569 and 234860 we care about the first place with two different digits. In this sample 4-th digits differ.

`nxt[a][b]`

assumes that one number starts at indexaand the other numbers starts at indexb. Then, it tells us where is the first place with different digits. In other words, it tells us the smallest non-negativeithatdigit[a+i] ≠digit[b+i].Now, let's understand "zero or nxt[a+1][b+1]+1". What happens when

`digit[a] != digit[b]`

? Then an array`nxt[][]`

should tell us thati= 0. Sonxt[a][b] = 0. Otherwise, it's enough to take a look intonxt[a+ 1][b+ 1]. It is the smallest non-negativejthatdigit[a+ 1 +j] ≠digit[b+ 1 +j]. So, we can say that now the smallestiis equal toi= 1 +j= 1 +nxt[a+ 1][b+ 1].This is a very important comment. I'd include it in the main text, or at least made a reference.

Thanks for the explanation

So why is it

`x = nxt[a+1][b+1]`

in the code snippet and not`nxt[a+1][b+1] + 1`

? And shouldn't it be`if(t[a] != t[b]) x = 0`

instead of`if(t[a] != t[b]) x = a`

?where?

In the code snippet http://ideone.com/zczsc3

Oh, sorry for that.

`nxt[a][b]`

has a bit different meaning in my code. Ifdigit[a] ≠digit[b] thennxt[a][b] =a. Ifdigit[a+ 1] ≠digit[b+ 1] thennxt[a][b] =a+ 1. And so on.In other words,

nxt[a][b] from my code is equal toa+nxt[a][b] from the editorialOk, thanks :)

It may be good to write it in the editorial itself. :)

Besides, could you please point me to some resource so that I could learn what the idea behind hashing is? I'm still learning and I never came across it. Thanks

It think that it'd be better to strengthen the neural pathways you've just established :)

I mean, we need to connect the concepts together so they support each other whenever you are faced with a different problem.

The big picture behind this problem is the concept of suffix array. This problem addresses the specific part of that bigger concept — the longest common prefix concept. I understood this only after reading the submission 15113502.

From my point of view, it is better to attack this single concept from different angles, cause the stuff is pretty basic. If you are going after hashing, you are at risk of losing the essential empirical evidence in the face of the brain for the necessity to retain the lcp concept on educationally relevant time scale.

But, probably, I am wrong.

instead of nxt[a][b] we can use lcs[a][b] (longest common substring starting from a and b to the end) and check if the length >= intended length it will make the same job of nxt[][] right ?

I think it's a wonderful goodbye round and I will never forget it because it is my first goodbye round.Thank you a lot,Errichto!!!

For problem B, can someone please explain the reason behind the condition

`(1LL << i) / 2 <= b`

inside the for loop in the solution provided (link) ? What would have been the effect if the condition was`for(int i = 0; (1LL << i) <= b; ++i)`

. I can't understand the importance of`/2`

Thanks.Maybe 2

^{i}>bbut 2^{i}- 1 - 2^{j}≤b. It means that with condition 2^{i}≤bwe would miss some solutions.I claim that 2

^{i}- 1 - 2^{j}≥ 2^{i}/ 2. It's true becausej≤i- 2. So, we have the following two inequalities"b≥ 2^{i}- 1 - 2^{j}^{i}- 1 - 2^{j}≥ 2^{i}/ 2Thus, we have

b≥ 2^{i}- 1 - 2^{j}≥ 2^{i}/ 2 and I can write`(1LL << i) / 2 <= b`

.If your 'b' will be like 2^k — 1, you'll not calculate 2^k — 2 and some another numbers. For example: 1 7

Could someone explain G with more details?

I will do it but not today

Can someone look at my code on E?

http://codeforces.com/contest/611/submission/15137943

I couldn't find any bug :( My greedy can be wrong but it finds smaller answer, so there must be some bugs. Thanks for help.

Here is a small test case -- your answer is 2, the correct one is 3:

You can beat the first criminal with A+B, the second one with A+C, and the third one with B+C. Yet, you need at least three hours.

I'm really grateful about reply. I never think like that :(

tourist replays .. what a moment ! :D

Good Bye 2015 on Problem E Pretest 10 :)

Attempt to Problem F: (Sorry for large picture)

The problem with original solution is that we cannot simulate all O(

w+h) steps now. Instead, let's consider the sequence of reducing the rectangle beR, and after two runs we have aw*hrectangle left. (w,h> 0, or we can end earlier)Four directions are troublesome, so we consider

Rto be either Vertical or Horizontal.For example, the above picture illustrates a

VVHVHsequence.Let

t_{1}...t_{|R|}be the timestamp of when theith move takes place, then, the contribution to answer of each piece is written as follows ( + 2npart omitted)How about, after 2nd round? Looks similar to 1st round: (

dhis the total decrement ofhafter a round,dwsimilar)(I forgot the +

npart fort_{3..5}, but I hope you got the idea)let's focus on the topmost pieces of each round, their contribution is of course (

w*t_{1}), (w-dw) * (t_{1}+n), (w- 2dw) * (t_{1}+ 2n).... (w-kdw) * (t_{1}+kn) where (k+ 1) is the number of round lasted.How to sum it? Let's do some sum Getting rid of

w*t_{1}: sum of them is (t_{1})(w+ (w-dw) + (w- 2dw)..(w-kdw), the right part can be summed using Arit Sequence. So the remaining job is to sum (w-dw) * (n) + (w- 2dw) * (2n) + ... + (w-kdw) * (kn), which is equal to (w-dw) *n+ (2w- 4dw) *n+ (3w- 9dw) *n..., the first term (wpart) is just 1 + 2 + 3 + 4 + 5..., the second term (dw) is (1 + 2^{2}+ 3^{2}+ 4^{2}+ ...) =k(k+ 1)(2k+ 1) / 6. Both can be calculated in O(1), and then we multiply it bynand add to the first part, then this piece is done once we knowk.How about those (

w- 1), (w- 2).. piece? looks so annoying, but we can just rewritew' =w- 1,w' =w- 2... and we're all good. Same applies to height pieces.Getting

kis not difficult either. One easy way is to takek=min(remaining_{h}/dh,remaining_{w}/dw), and then we knowk. The remaining part can be handled by a final enum, as we know that we'll end in less than or equal to one turn.Happy New Year! Conceptually looks easy to me, so I'm wondering if I made something wrong.

15140553 Code for reference. Sorry for ugly code (Idk why i use a Priority Queue to sort indexes LOLZ) Also should be pretty fast.

Morning news: last night a unitconvert website got DDOSed, the attack seems to be from all around the world. The attack was at 16:35 UTC, specialists say "number of mondays in 2016" was the common search used to over-bulk the servers, stay tuned as we find out the organization behind this.

In problem D tourist http://codeforces.com/contest/611/submission/15107147 Why he(tourist) is adding the value

dp[i — len][i — 1] to the value sum (when added == false) after updating dp[i][j] = sum; ( after updating sum if that number is smaller than that ) why do we need this part, can someone explain ?

if (i — len >= 0 && !added) { add(sum, dp[i — len][i — 1]); } Thank in advance.

"One of them is to store hashes of each of n·(n + 1) / 2 intervals"

What are the hashes of the intervals? I've never used such a thing. The only hashes I've used are the md5/sha1 hashes.

thanks

He was talking about Rolling hash. It is useful for string comparison, because it can be calculated very fast for neighbour substrings. If two strings have same hash, they are very likely equal and comparing numbers is much easier than comparing strings.

I solved E with branch and cut LP: 15130924. The idea is you create 8 variables corresponding to a, b, c, ab, ac, bc, abc, and total time. Then the problem can be expressed as a set of linear inequalities on these variables.

I have no proof that it works, though. Maybe it runs for a very long time on some input.

Detailed editorial for G (geometry) is added.

Fairly unnecessary solution on H, but I'll post it here anyways.

Let

G_{1}, ...,G_{k}be the groups. LetE_{GiGj}be the edges we need to make between groupsG_{i}andG_{j}. WLOGE_{GiGi}= 0 since we can take care of those immediately at the beginning.Claim: A necessary and sufficient condition for checking whether the answer exists can be described by the following. Take any subset of the groups. Let

Ebe the sum of the edges between those groups and only those groups. LetVbe the number of total vertices in those groups. If for all subsets satisfyingV> 0,E≤V- 1 then an answer exists.Proof: We prove this by induction and an algorithm. We separate 2 cases.

Case 1: Some group

Ghas size ≥ 2. I claim that there exists a different groupHsuch thatE_{GH}≥ 1 and decreasing the group size ofGby 1 maintains the condition.First, ignore all groups

Hthat have no edges needed betweenGandH. So from now on only considerGand the groups thatGneeds an edge between. LetSbe any subset of the groups that includesG. Call a subsetS"tight" is the total number of vertices inSis exactly 1 more than the total number of edges inS.Now all we have to show is that there exists some group

Hin every tight subset. Then drawing an edge fromGtoHand reducing the size ofGby 1 clearly maintains the condition. By reducing the size ofG, I mean saying that the vertex inGthat we drew an edge to will no longer be used in further edges. This guarantees that we have a tree in the end.Lemma: If

S_{1},S_{2}are tight, then is tight.Proof: Let

V(S) denote number of vertices in a group,E(S) denote number of edges among a group. The number of vertices in is equal toNow, because

S_{1}andS_{2}are tight,But .

Combining this with the previous, , which implies that is tight.

Now if no group is in every tight subset, then the intersection of all tight subsets is just

Gitself, which is a contradiction to the definition of tight, asV(G) ≥ 2, but there are no edges needed betweenGand itself.Case 2:

Ghas one vertex.If

Ghas at least 2 edges adjacent to it (needed between it and other groups), ignore it. Otherwise, it has exactly one edge adjacent to it, and just use that edge. In other words, reduce the size ofGto 0 and draw the edge. This clearly maintains the condition I described above. So the proof is complete.Alternatively, do Case 1 until all groups of size 1 and then brute-force spanning trees.

Alternative solution for problem D:

let dp(L, R) = number of ways to use number(L, R)

having number(L, R) you need to have number(R + 1, P) for all P >= R+1 and number(L, R) < number(R+1, P) and R < N.

there is an index P >= R+1 where number(L, R) < number(R+1, P) so we can update dp(R+1, P) += dp(L, R) for each P (range update).

the answer is the sum of dp(L, N-1) for each L.

The trick is that all range updates can be done in constant time, see 15196533

In problem E the answer using only a + b and c should be max(max(x, y) / 2, x – y, y – x).

Can anyone please explain why my following solution for C fails???

My Submission

Really need help. I am quite baffled.....

I have written a more detailed editorial about 611 C, "New Year and Dominos" here. Please refer it and ask me any doubts. :)

Thanks , that helps me a lot to understand the editorial :)

Why am I getting

WAonTest case 72forproblem B: 85538392While the very similar solution gets accepted: 85538021

Does it have to do something with pow()?