Hello everybody!

Today Codeforces Round # 106 for Div2 participants will be. And all who wants can take part in this competition. You will have the opportunity to break from parents with Peter, to learn some interesting facts about the Martians and to solve, of course, interesting problems for you as we hope.

This round has been prepared by a team of three people: Gerald, NALP и Polichka. We express our gratitude for their help to Artem Rakhov (RAD), Mike Mirzayanov (MikeMirzayanov) and Maria Belova (Delinur) .

Score distribution: **500-1000-1500-2500-2500**.

Good luck and high rating to all!

I love this normal Score distribution, last contest is really unfair ...

However, i mean 500-1000-1500-2500-2500, not participants rating distribution.

good luck everybody

good luck :)

I like the problmsets, thank you, Gerald NALP and Polichka. Wait for the editorial.

How to solve problem D and E? Would someone give me a hint? Thanks.

D: f(i,j,x,y) = number of possible coloring sequence i..j, with i having color x and j having color y

How to deal with the conditions? condition 2: A matched pair can have exactly one color. condition 3: No two neighboring colored brackets have the same color.

In short: when you found some neighbor brackets, check them. When you found 2 matching brackets, check them.

A bit more details (I may forgot some cases): When i and j are matching brackets, f(i,j,x,y) = sum( f(i',j',x',y') )

--> you consider x & y, x & x', y & y' if they satisfies conditions

When i and j are not matching brackets, f(i,j,x,y) = sum( f(i,j',x,x') * (f(j'+1,j,y',y))

--> you consider x' and y' if they satisfies conditions.

for D, my idea was a DP. Scan from left, chose matching brackets. Color them in colors which are allowed, Now rest of string are divided in two parts. Solve them recursively.

Example :

(()()()())()()()()(())gets divided into ()()()() and ()()()()(())this contest I have the same problem, as last div2: after I submit my hack, nothing happens, and even page doesn't reload, but hack is submitted well

Firefox 10.0, Ubuntu 11.10

Same here (Firefox 11.0 beta, Windows 7).

I failed to submit solution to A at the first time, i.e. I did submit but it seems the server didn't receive it.

Most points from hacks in this round (800)? =D

You were lucky with the room.

Really? I see 10 (more than my successful challenges) unchallenged solutions for problem 2 which failed the system tests (including yours) in your room =)

You are right, I'm just kinda dumb :\

Hey, I didn't mean it like that =/ Also, there were 6 solutions that failed system tests in my room, so I missed a large number of them, I can say I had some luck to have 14 wrong solutions in my room, in that specific problem.

Btw, at first I submitted a solution that gave the wrong answer for 0:10 but it passed pretests, that's why I managed to make so many hacks, because I knew where to look for a specific mistake =)

No, I'm seriously, also, I failed A and B because of time pressure.

Yeah, that happens. It's important to keep calm to make sure we don't slip on the "easy" problems.

What tricky cases (not covered by the pretests) were there in B?

00:10

Not a few people overlooked the fact that the maximum possible base is 59.

Well, I did ;) but failed pretests.

I used Integer.parseInt(String,base) .It failed.Does it check for only bases <=36.If yes,how can I modify it??I know the other approach of finding it by evaluating it bit by bit.Only tell me if I can use the parseInt() function

See this page: http://docs.oracle.com/javase/6/docs/api/java/lang/Integer.html#parseInt(java.lang.String, int)

It does check base <= 36 (Character.MAX_RADIX == 36 in Java 6), and you can't modify it.

I did all my 8 challenges in problem B, the most common one was 0:10 for people that output -1 when it works for base 36 (or some other base < 60). There was one person in my room that checked minutes <= 60, that wasn't covered in the pre-tests either.

EDIT: evima beat me to it =P

Two bugs: 1. After hacked i got javascript alert "Undefined" instead of "your solution have been hacked" 2. When i tried to hack other solution nothing happened after giving input and after 10-15 seconds it showed "the solution have been hacked or resubmitted", later in hack page i've seen that my hack was successful.

I experienced the second bug twice. In my case, the first hack was successful, but the second one was ignored (someone was faster).

I got the same message "the solution have been..." regardless of whether the hack was successful.

I got bug1 too. It happened to me last round too I posted it on my blog and nobody replied to me and now same problem still exists.

BTW, there is an O(n log n) algorithm for E. I see that most passed solutions are O(nm). Waiting to see which one is in the editorial ;)

Can anybody please tell more about your O(n log n ) approach for E ?

Let me sketch both approaches.

Let's call the long word s. For every short word w: we are to say whether there is an i such that w[1..i] and w[i+1..end] both occur in s, and w[1..i] occurs before w[i+1..end] (so that they don't overlap). It only makes sense to consider the leftmost occurence of w[1..i], and the rightmost occurence of w[i+1..end]. So we are interested in the values f[i] and g[i], where f[i] is the position of the leftmost occurence of w[1..i] in s, and g[i] is the position of the rightmost occurence of w[i+1..end] in s. Once we have f and g, we can easily check whether there exists an index i such that g[i]-f[i] is large enough (larger or equal to i, I think). And if we have a method of computing f, then we can use it to compute g (it's pretty much just f for both strings (s and w) reversed). So we're left with how to compute f.

The O(nm) approach: search for every word w in s, using KMP. During matching, we virtually get the f[i] array as a byproduct (this is clear if you know how KMP works).

The O(n log n) approach: we use a Suffix Array for s (and s reversed to compute g). There are fast algorithms for SA construction (even linear-time). We also precompute a Range-Minimum-Query structure for the SA. Now how to compute f: for every prefix (starting from i=1), we find the range [a,b] such that sa[a..b] corresponds to the indexes in s which begin with w[1..i]. We compute this range from the previous one using a binary search. We then run an RMQ query on sa[a..b] to find the minimum index (which is the f[i] that we want).

The details can be seen in my solution ;)

You must have come from a parallel universe. Most accepted solutions I saw so far has O(M+N) complexity

Edit: Sorry, I miscalculated :(

O(M+N) really? All I saw ran KMP (or some string matching) for each small string and that would be O(MN)

Is it possible to delete I comment? now my older comment makes no sense :D

You can edit it and write ignore

suffix array?

O(N*logN) is also not a feasible solution since you HAVE to examine the words. So it is at least O(N*logN + M) or more likely O(N*logN + L), where L is the sum of characters in all M words :) (yeah, I know M is

usuallymuch smaller than N*logN, just making a note). My solution uses hashes instead of Knuth-Morris-Pratt and also has time complexity of O(N * M). To be honest I'm also curious about the logarithmic solution.Also, if you use suffix array and then do a binary search in it for each word wouldn't you get time complexity of O(N + M * logN * 1000) or something?

Yes, my algorithm is actually O((n + L) * log n). I'm just treating the value in parentheses as n, since in the problem, L is also <= 100000 ;)

The algorithm can even be made linear-time using very advanced techniques. Not that it would run faster ;)

Y U NO HACK ME :(

Thank you to the codeforces team for that contest. This contest has very good questions and very well pretests.

armin Riiiii*iiii

I would suggest enabling cookies and checking the check-box "log me in for a month".

Hi...my submission ID for problem B is 1168221. My program gave correct output for 1st pretest on my system and also on Ideone.com but it is judged wrong on pretest 1. It is giving an additional output of 23 in the end. Please resolve the issue. :( :(

ignore

it is showing 23 at the end which is not required...please double check it.

Same thing has happened to me also. It has added 23 at the end resulting in pretest:1 failure.

= = me too,it is the bug?

Same thing.I submitted the code...It was showing 23.After contest, I didn't use pow().I submitted again. This time it was correct :( BadLuck

yes, i have understand it. it is a rounding off problem. i use a int variable to get the return of pow(). it's prototype double pow(double n, double i);

so while u didn't use pow(),u gonna be AC

@admin . Hello, My submission for Problem B whose id is 1167928 gives correct answer for pretest 1 on my system as well as on ideone.com. My my submission has been judged to be wrong on pretest 1 itself. On codeforces for pretest 1 it outputs an extra 23, but 23 is not printed for the same input on my system and not even on ideone.com. Please look into the matter ans resolve the issue.

me too = =

I got

Judgement Erroron my first try (1166157) of 149C - Division into Teams and after I submitted again thesameanswer, the two submissions were judged asPretests Passedand I got a-1because of the resubmission. Can anyone fix the score please?@admin:My submission id : 1168245 : It is failing for Pretest1 for Problem B. I am getting correct answer on my machine (using g++ compiler) but when solution is submitted, '23' is additional printed in codeforce's compiler resulting in wrong answer of pretest 1. I see same thing has happened to other person also, who have complained in this forum. Is there bug in codeforce's compiler.Please check

I think it caused by roundoff errors and/or c++ optimization. Those who complained this problem in the forum use the cmath function pow(double,double), which can cause roundoff error in some environment, even though the parameters are integers.

And, when I ran dragonfire's code with some additional std::cout for debug, then extra '23' is disappeared (see my submission: 1170942).

This is sooo strange, but probably it suppressed the compiler optimization and the calculation became correct

What's the proof that makes the solution of taking the odd indexes in a team and the even in the other -after sorting the numbers- work in problem C?

Let a1 >= ... >= an. Then the difference between teams' strength is a1 — a2 + a3 — a4 + a5 — a6 + ... <= a1 — a3 + a3 — a5 + a5 — a7 + ... <= a1.

When will the editorial be available? I'm in very need to it :(

It is already available.

http://www.codeforces.com/blog/entry/3864

Thanks very much :)

You're welcome. :)

Is it possible to arrange some contests on weekends? Looks like the upcoming ones are either on Friday or Monday. Thanks.