Hello everyone!

Codeforces Round #156 will take place on Sunday, December 16th at 19:30 MSK. This is my second Codeforces round and I hope not the last.

I'd like to thank Steps09, Seyaua, sdya and Gerald for helping me to prepare the round. Special thanks to Delinur for translation of all problem statements into English.

Problems’ point values are standart: **500-1000-1500-2000-2500**.

I strongly recommend you to read ALL the problems.

Gl & hf ! :)

Contest is over, I hope it was interesting for you :)

Congratulations to div1 winners:

1). WJMZBMR

2). al13n

3). rng_58

4). tourist2

5). KADR

and div2 winners:

1). ShadowSong

2). xiaoshua99

3). jiaobu

More like "lack of lag and luck" — when you say it with the right accent it sounds really hilarious, but still makes sense :D

Does this contest require any file input or output ?

I don't think so.

Thanks :) !

Usually, we don't need to get input from files. The two last contest were exceptionnal, because it was for a local stage in Saratov. If it isn't indicated, the input and output are standard.

Moreover we can write code that will check if such file exist and then read and write here, otherwise use standard IO.

Usually we don't have permissions to read files :P

Thanks ! I will have that in mind from now on ! :)

Will the scoring be dynamic or standart?

No dynamic scoring, I promise.

And will it be 500-1000-1500-2000-2500, as usual?

I don't know, temporary.

If problems will not be sorted by difficulty, I don't think that scoring will be 500-1000-1500-2000-2500 as usual.

I strongly recommend you to read ALL the problems.You see :D i don't think the score will be the same as usual :D

As a matter of fact we have contest in both divisions and as each contester can see the others' problem so it is hard to separate problems . :D

It's not the first time lots of solutions are in queue =(

I need a clarification, the integer 'q' in div2-C is always an positive integer ?

I think it can be negative.

thank u! :)

But... in proper solution it doesn't matter

In Div2C does q need to be positive, because if no then in the second test case:10 20 10 30 the example can be 4 or I am missing something?

q can be negative

yes, q can be -

On problems page (dashboard) there is

[ASK QUESTION]button !!! ( So you should not ask questions in blogs during contest) =)I didn't know this man. Take it easy, relax.

I didn't know that. I am sorry if I disturbed someone.

hi can help me about problem c? i dont know what is say

given a sequence b, find longest sequence q in the form of

a,b,a,b,a..... where a and b are integers.

thank you for your response

can you help me about your algorithm?

Well the server is tottaly trolling me. I submit on problem D and it cost more than a minute to running on test 8. I though it will TLE. Then I decided to resubmit it, When I resubmit it my last submission got passed. Now I get -50 for my submission and penalty minute.

Sorry, but it was your choice. Lag is to be expected, you should've waited for the result.

How solve problem C ???

Maintain a list of indices for each different value. I missed just a couple of characters in my code, and I got WA :(

What's the trick in D? Why counting a number of sequences in which number (n-k) appears exacly (n-k) times and there isn't any other number q that appears exacly q times is wrong?

I guess number of i such that a[i] appears exactly a[i] times should be equal to n — k.

There may be some numbers s_i such that each number s_i occurs exactly s_i times and the sum of all s_i is n-k.

Let's assume n = 4 and k = 1. Does the sequence 1, 2, 2, 4 is good? There are 2 possibilities: either first person always tell the truth or second and third does. We can't know anything for sure.

For the fourth person we are sure that he is lying. Each of the first three people may be telling the truth. So the sequence is correct.

I have some trouble understanding Div1D. If 0<k<n, then nobody can answer 0. How can Serge with such answers find out that not everybody is a liar (if everybody is a liar, then everybody can answer anything)?

If X people tell the truth then exactly X people must answer X.

I had the same trouble for a while.

For example, suppose that there are two people A and B, and they answered 1 and 2, respectively. Then there are two possibilities: {A honest B liar} or {A liar B liar}. You can conclude that B is a liar, but you have no information about A. You concluded that k = 1 people (B) is a definitely liar.

do you have an algorithm that does not require to make a table beforehand?

I can only figure out a solution with time complexity n^4 :(

Author solution is n^4 dynamic programming. And precalc (n is power of 2).

umm...so why not just make n<=50?I don't know the intention of force competitors to make a table :(

My solution is O(n^4) too.

OK, thank you! I thought Serge would be able to say that there are exactly k people lying (no matter which), not that there are exactly k people for which he knows that they are lying.

funny!! couldn't understand div2-C in contest time. :(. i could solve it... :(

please explain your algorithm

you can see solution of others within a very short time :)

where can see solution?

(you can filter status page using 'status filter' portion in the right side)

Thank you very much :)

u wc :)

Did anybody use binary search in div2-D, or it's bad idea to do it?

I think many people would have done it using binary search on the number of steps.

I could count numbers until this wave will reach any wall, but what to do then?

You can find out the number of cells filled in T steps in O(1). It is easier if you consider the simpler problem where we start filling an A*B (A<B) box starting with the bottom left cell filled.

Then you should count cells switched on which are outside of board.

These cells formulate a triangle. There are at most four triangles (one for each side). And some of them can overlap.

Thx for clear explanation, I'll try)

count how much of them out of the field using arithmetic progression

border1, border2, cap1, cap2 is distance to border and top from start. if cell on edge, then here coord are abs(bx — x) + abs(by — y) = step, step is current number of step, x, y from input. After we have line of fill edge cell on each side, we can calculate square with (a-1) * b /2, a-how mach cell if fill on this edge, b — is height step out borber, (step — distance to this side)

I think so.

Interval is 0..2n-2

This problem was similar with last COCI exam !! Isn't it ??

UPD:I mean solution of them were similar.I must learn to read problems really. I have misunderstood DIV2-E :@ :@ Complicated it for nothing :@

So slow

So obvious :P

There are two reasons to try to solve a problem faster .

UPD:Now I can sleep and relax. No problems with my solutions. I prefer sleeping than waiting for rating change and be late for school tomorrow.Thanks for the advice, but actually I meant slow system testing phase

It seems the systest will take a big amount of time... a previous round written by me also have this problem... It is because put so much big test in problem A or B, that kind of easy problem has many submissions, so if one submit need 50 seconds, then the whole judging will last for hours :(... so I hope the later writers can take care of it :)....

what is the algorithm for solve problem c?

and one thing....who is tourist2 ?

maybe there will come someone like Petr2 or ACRush2 ? (just joking :) )

may be WJMZBMR2 !!!!

I found who he is by his code....

a hint: he use lemon() a lot :)

And what does it mean?

>>see<<

I think, he meaned "who uses lemon() besides tourist2" :D

And I was thinking why I have negative votes (=

By the way, his solution of todays div1-B (2777959) includes many useless procedures and functions, it seems that he's trying to make his code difficult to read, and it's a bit unfair because, I think, CF rules include some prohibitions like that.

this is not the case.... that code is an solution for a another problem, which is the same as today's B but has many point at the start not one. this is very difficult indeed and require tons of code.. he just use that big weapon to shoot at this easy problem.. this is ok bcz CF allow you to use previous code written by you.

But his solve2(), slove3() .... etc are equal to each other! :D

read carefully...they're not equal and every one work for some case... but indeed it can be replaced by 4 rotation ...

oh, my mistake, they are different))

I know who you talking about. :)

I got TLE when I sent Prob B div 2. I think this solution does not spend more than 2 second running. I lost 50 point in that.

strlen() function works in O(n) time

Thanks

The rate of comments in this blog is more than the rate of system testing !!!

Problem A turns out to be harder than expected

Yes, I think many people tried an optimized O(n^3) solution.

Div 1 or Div 2??

Div1

More slow system test, more accepted submissions.

this systest need one codeforces contest time

I passed Div2 C with O(N^3). I even had prepared a test case where I fail because of time limit. I was lucky this test was not in the systest. I just fixed the two starting numbers — O(N^2) and then greedily find the longest sequence — O(N). So totally O(N^3).

I have added this: if (many[A] + many[B] <= ans) continue; and fooled the systest. But the test 1 2 2 3 3 4 4 5 5 6 6 7 7 ..... breaks my solution with time limit exceeded.

It's your luck no one hacked you. But in this case of course it's fair

And my solution of O(N^2+ Hashtable search) gets TLE :(

EDIT -> Used Hashtables to map a particular element to one of the index in between [0,4000) and then called every reference with arrays and the code gets Accepted

Your solution can be easily changed to O(n^2). When you are finding the longest sequence, you can only go through the elements that are equal to the one of those two fixed (not through the whole sequence like in your submission).

For Div 2 E , please tell whether my grundy number calculation is correct or not ??

In each step we should try to make y as large as possible. So we should try to make y to x^(1/2) in each step. We can keep doing this until we can make a move ie. 0<=y<x. finally grundy number will be the number of steps taken in this part.

please verify findXor function to calculate xor . link : http://www.codeforces.com/contest/255/submission/2782916

No, we shouldn't try to make y as large is possible. Actually, if n=1 and x=25, it's better to take y=3 and win (Rublo can't change the number, because 1<3^(1/2)<2 and 1<3^(1/2)<2, there is no integer in this interval). Sprague-Grundy number of some state of the game is the minimum non-negative integer, that is not equal to Sprague-Grundy numbers of any state, which we can achieve from current state.

Thank you for your reply, Now I have understood it. Actually I thought of taking sqrt(x) because I wanted to make state less. But I forgot the nice thing that I only needed to have grundy numbers upto sqrt(77777..... 12 times ) which was not so large.

EDIT : solved the problem.

rating?

probably having coffee around a corner of RAM with "paging system"....

Ratings have been updated:)

And this is the 101st comment!

Editorial in Russian available here @ http://codeforces.com/blog/entry/6161

google translate makes a good translation for this editorial .... thanks for being google-translate friendly.....

It would be really helpful if anyone could provide a dynamic programming solution to Div-2 C problem.( not the code, only the idea)

Well there are only N different numbers so we can sort them and lower them to the range [0, N — 1] instead of [1, 10 ^ 6]. Now we can build a matrix DP[MaxN][MaxN] where DP[i][Numbers[j]] would be equal to the maximum length of some progression that has the last two elements Numbers[j] and Numbers[i]. Since we know the last two elements we know the last three since it equals (a, b, a, b, a, b, ... ) are Numbers[i], Numbers[j], Numbers[i] so we can use something of a very simple knapsack solution. Try to update DP[i][Numbers[j]] with DP[j][Numbers[i]] + 1 and in the end write maximum of the matrix + 1.

Code for this idea: 2775826

Thanx a lot :)

My dp solution: take all pairs (these pairs will end of our subsequence, subsequence must be like this: x y x y x y x) and try to find answers for them. Say, pairs are : a[i] and a[j], which i > j. So d[i][j] = d[j][k] + 1, which (k < j) and (a[k] = a[i]), of course we must know answer of d[j][k]. I tried to explain to you my solution, sorry for my bad english.

Thanx a lot :)

thank you for the contest , I think that these problems have fresh ideas

when will be the Editorials out.. ?? :D :D

I cant believe it. My submission number 2812603 passes the test case 11 (458754) for which it gives the answer 667496909 on my computer.

is there any english editorial of round 156???? I'm thirsty of it