Let me warmly welcome you to Codeforces Beta Round #11. I am the main problemsetter for this contest. I hope you'll have fun solving the prepared tasks :-)

Thanks to Mike Mirzayanov for making this possible and to Ania Piekarska for testing the problems.

Good luck,

Jakub Pachocki

I really liked problem E. I haven't solved it and maybe even far from complete solution yet, but solving it was very interesting.

after 6 years of you comment i want to said to you that i facing the same problem :D

Can you explain how to solve B? I saw people using logic

`while (sum<x || (sum-x)%2==1) {ans++; sum+=ans;}`

, what is the logic behind`(sum-x)%2==1`

?There seems to be no editorial for this round or description of how to do this problem, so I will post my solution here.

SolutionMy solution involved adding X's so that every L and R in the original string was correct (if a character was bad I would add an X right before it). However, sometimes it is suboptimal to add this many. If I added two X's, and there was exactly one L or R between them, then removing them removes two bad characters (those X's), but changes one good character (the one between them) to a bad character, and leaves the rest of the string unaffected, which is a net decrease by one for both correct and incorrect characters, and this is a good move to make if the answer is above 50%. This can be done by just looking through the list of positions where I added X's, with a few extra checks to ensure that there are never two of the same step adjacent to each other. Code

does petr reply only to red coders ?

nope

but its very rare...

Let n be a positive integer. Consider any k such that 1 + 2 + ... + k >= n. Then n is reachable in k jumps if there is a subset A of {1, 2, ..., k}, such that when we make all jumps from A go left and all jumps not from A go right, we reach n. This is equivalent to k(k + 1)/2 - 2 * (sum of numbers in A) = n. It's very easy to prove that the sum of numbers in A can be any number between 0 and k(k + 1)/2, so it's possible to reach n iff the difference between k(k + 1)/2 and n is even.

http://informatics.mccme.ru/moodle/mod/statements/view3.php?id=477&chapterid=77

и разбор:

http://informatics.mccme.ru/moodle/mod/book/view.php?id=489

а вообще весьма странно что подобные вещи плохо в инете находятся... или я плохо ищу))

самому что ли сделать доброе дело - накатать статью :D (а если потом ее кто нибудь переведет на английский - будет совсем замечательно)

I have problem in my head or codeforce has problem in its head....

my contest code of B got WA in test 4 using scanf and printf

but in practice same code got AC using cin and cout?

is there any explanation anyone can give?

here is my WA in test 4 code

http://pastebin.com/cbBH5nzz

if u replace scanf("%lld",&num)==1 with cin>>num and printf("%lld\n",i) with cout<<i<<endl; it gets AC ...

As you can see there is an 2005 MSVS compiler and it doesn't work with %lld, but with %I64d!

Or you can just make all variable int (it's enough) and use %d.

I tested it just now.

I'm wrong. (c)

From 2005 version VS supports both %I64d and %lld.

Thanks for the problems, but I'd like to pay attention to some inaccuracies in them.

1. B: "He can go either left or right with each jump." One may think that Jack can go either left or right

from his point of view. For example, going left and then right would move him (0,0) -> (-1,0) -> (-1,1). That will make the problem two-dimensional and thus much more complicated. A friend of mine spent much time until he realized his mistake. It would be better to write something like "He can go eitherbackorforthwith each jump."2. C. What is a diagonal of a non-square matrix? It is a rarely used term, at least I've hardly found a mention of it only on the second page of Google's result. It would be much better if the definition of this term was given in the problem. It requires only a sentence or two, but clarifies the problem.

3. C. "a square must contain at least one 1 and can't touch (by side or corner) any foreign 1". What does "foreign" mean here? Is it a "1" which doesn't belong to this square or to any square?

4. Also "a square must contain at least one 1", but earlier "A square should be at least 2×2". I understand, that there is no contradiction, but why increasing the confusion?

Thanks.

For example: the authors should explain why the result is 1 for the 1st test case, 2 for the 2nd test case... for the problem C.

Look, there are 3 squares in the first example, but two of them (2x2 in the left bottom corner and big square of type 2) are "touching" each other, so they don't count. There is also a single "1" in the top right corner, but "A square should be at least 2×2". So only one remains - the 2x2 square of type 1, which is located in the bottom right corner of the matrix.

As for the 2nd test case in the 1st example, there are 4 squares, but two of them are touching each other, so the answer is only two small squares, which are located inside the big square.

But it took much time and even a discussion with my friend to explain these examples. The authors should have left some comments on them.

Look, there are 3 squares in the first example, but two of them (2x2 in the left bottom corner and big square of type 2) are "touching" each other, so they don't count. There is also a single "1" in the top right corner, but "A square should be at least 2×2". So only one remains - the 2x2 square of type 1, which is located in the bottom right corner of the matrix.

As for the 2nd test case in the 1st example, there are 4 squares, but two of them are touching each other, so the answer is only two small squares, which are located inside the big square.

But it took much time and even a discussion with my friend to explain these examples. The authors should have left some comments on them.

You mean explain withit problem statement?

If yes, I'll agree with you.

For example. If you want to reach 10^9 position, in some you'll be near it. Let it be a 10^8 position (of course the real position place will be close to 10^9, you can prove it yourself). So we need to compute 10^8 cells. It takes more than 1 sec time. :(

And you need about 120 MB to store billion length bool array.

Maybe there is a much better DP solution, and maybe even it got AC, but i solved that with little formula and very little bruteforce (most of participants use only brute).

If you request a code you can get it there - http://codeforces.ru/contest/11/status/B?order=BY_ARRIVED_ASC

I am new to programming. The people have solved problem D quite easily as it is quite trivial for them. I am not able to understand how they are solving using DP. what is the subproblem. I have spent 3-4 days trying to understand the solutions but no success. Can anyone help ? I will be grateful for the same

After participating in the contest,I learnt I also had had so much to learn since the day.

This blog link explains problem 11-D.

http://codeforces.com/blog/entry/337

thanks!

Can someone explain how to solve B? I saw people using logic

`while (sum<x || (sum-x)%2==1) {ans++; sum+=ans;}`

, what is the logic behind`(sum-x)%2==1`

?Let us suppose you take j jumps to reach some point y where y >= 0. Let us suppose you took some forward and some backward jumps. Clearly, we can write : 1. (sum of forward jumps) — (sum of backward jumps) = y ...equation(i) 2. (sum of forward jumps) + (sum of backward jumps) = j(j+1)/2 .... equation(ii)

Combine both to get: j(j+1)/2 — 2(sum of backward jumps) = y

The above equation is the key. [Note : sum of backward jumps -> is the sum of some elements from the set {1,2..,j} which can take any value between 0 to j*(j+1)/2 ..not too difficult to prove]

Hence, if (j(j+1)/2 — y) is even and (j(j+1)/2-y)/2 lies in the range [0,j(j+1)/2] then clearly we can reach y in j moves. Hope it is clear!!

I will try my best to explain the my approach on problem 11D without using sum of subsets dp. Denote

`d[last][mask]`

as the number of ways to form a chain consists of every elements with its bit on in the mask, the first bit (`first_bit`

) in mask is the head of the chain (we are fixing the order of the cycle) and`last`

is the last element in the chain. The transition is easy, take every possible`next`

bit that satisfies`next > first_bit`

,`next`

doesn't appear in the current mask,`next`

and`last`

share an edge and`d[next][mask^(1 << next)] += d[last][mask]`

. Check through every dp state that there is an edge between`last`

and`first_bit`

and add them to the final answer. Finally divide the answer by 2 as we repeated the calculation in the last step.My submission: 79403398.