Polichka's blog

By Polichka, 8 years ago, translation, ,

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!

• +129

 » 8 years ago, # |   +17 I love this normal Score distribution, last contest is really unfair ...
•  » » 8 years ago, # ^ |   +65
•  » » » 8 years ago, # ^ |   -15 However, i mean 500-1000-1500-2500-2500, not participants rating distribution.
 » 8 years ago, # |   +6 good luck everybody
•  » » 8 years ago, # ^ |   +2 good luck :)
 » 8 years ago, # | ← Rev. 2 →   +21 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.
•  » » 8 years ago, # ^ |   0 D: f(i,j,x,y) = number of possible coloring sequence i..j, with i having color x and j having color y
•  » » » 8 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » 8 years ago, # ^ | ← Rev. 2 →   +1 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 conditionsWhen 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.
•  » » 8 years ago, # ^ |   -8 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 ()()()()(())
 » 8 years ago, # |   +4 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 wellFirefox 10.0, Ubuntu 11.10
•  » » 8 years ago, # ^ |   +1 Same here (Firefox 11.0 beta, Windows 7).
•  » » 8 years ago, # ^ |   0 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.
 » 8 years ago, # |   +1 Most points from hacks in this round (800)? =D
•  » » 8 years ago, # ^ |   0 You were lucky with the room.
•  » » » 8 years ago, # ^ | ← Rev. 2 →   +1 Really? I see 10 (more than my successful challenges) unchallenged solutions for problem 2 which failed the system tests (including yours) in your room =)
•  » » » » 8 years ago, # ^ |   0 You are right, I'm just kinda dumb :\
•  » » » » » 8 years ago, # ^ |   +6 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 =)
•  » » » » » » 8 years ago, # ^ |   0 No, I'm seriously, also, I failed A and B because of time pressure.
•  » » » » » » » 8 years ago, # ^ |   +6 Yeah, that happens. It's important to keep calm to make sure we don't slip on the "easy" problems.
•  » » 8 years ago, # ^ |   0 What tricky cases (not covered by the pretests) were there in B?
•  » » » 8 years ago, # ^ |   +1 00:10Not a few people overlooked the fact that the maximum possible base is 59.
•  » » » » 8 years ago, # ^ |   0 Well, I did ;) but failed pretests.
•  » » » » 8 years ago, # ^ |   0 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
•  » » » » » 8 years ago, # ^ |   0 It does check base <= 36 (Character.MAX_RADIX == 36 in Java 6), and you can't modify it.
•  » » » 8 years ago, # ^ | ← Rev. 2 →   0 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
 » 8 years ago, # |   +12 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.
•  » » 8 years ago, # ^ |   0 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.
•  » » 8 years ago, # ^ |   0 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.
 » 8 years ago, # |   0 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 ;)
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 Can anybody please tell more about your O(n log n ) approach for E ?
•  » » » 8 years ago, # ^ |   +11 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 ;)
•  » » 8 years ago, # ^ | ← Rev. 3 →   -8 You must have come from a parallel universe. Most accepted solutions I saw so far has O(M+N) complexityEdit: Sorry, I miscalculated :(
•  » » » 8 years ago, # ^ | ← Rev. 3 →   0 O(M+N) really? All I saw ran KMP (or some string matching) for each small string and that would be O(MN)
•  » » » 8 years ago, # ^ |   0 Is it possible to delete I comment? now my older comment makes no sense :D
•  » » » » 8 years ago, # ^ |   0 You can edit it and write ignore
•  » » 8 years ago, # ^ |   0 suffix array?
•  » » 8 years ago, # ^ |   +1 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 usually much 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?
•  » » » 8 years ago, # ^ |   0 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 ;)
 » 8 years ago, # |   -30 Y U NO HACK ME :(
 » 8 years ago, # |   -18 Thank you to the codeforces team for that contest. This contest has very good questions and very well pretests.
•  » » 8 years ago, # ^ |   -15 armin Riiiii*iiii
 » 8 years ago, # |   -28 Two complaints: 1. Why Am I getting logged out again n again?. 2. Problem C, was not good. Any idiot can also guess that answer without proving. 
•  » » 8 years ago, # ^ |   0 I would suggest enabling cookies and checking the check-box "log me in for a month".
 » 8 years ago, # |   0 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. :( :(
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 ignore
•  » » » 8 years ago, # ^ |   0 it is showing 23 at the end which is not required...please double check it.
•  » » » » 8 years ago, # ^ |   0 Same thing has happened to me also. It has added 23 at the end resulting in pretest:1 failure.
•  » » » » » 8 years ago, # ^ |   0 = = me too,it is the bug?
•  » » » » » » 8 years ago, # ^ |   0 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
•  » » » » » » » 8 years ago, # ^ |   0 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
 » 8 years ago, # |   0 @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.
•  » » 8 years ago, # ^ |   0 me too = =
 » 8 years ago, # | ← Rev. 2 →   +3 I got Judgement Error on my first try (1166157) of 149C - Division into Teams and after I submitted again the same answer, the two submissions were judged as Pretests Passed and I got a -1 because of the resubmission. Can anyone fix the score please?
 » 8 years ago, # |   -6 @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
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 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
 » 8 years ago, # |   0 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?
•  » » 8 years ago, # ^ | ← Rev. 2 →   +12 Let a1 >= ... >= an. Then the difference between teams' strength is a1 — a2 + a3 — a4 + a5 — a6 + ... <= a1 — a3 + a3 — a5 + a5 — a7 + ... <= a1.
 » 8 years ago, # |   -13 When will the editorial be available? I'm in very need to it :(
•  » » 8 years ago, # ^ |   +1 It is already available.http://www.codeforces.com/blog/entry/3864
•  » » » 8 years ago, # ^ |   0 Thanks very much :)
•  » » » » 8 years ago, # ^ |   0 You're welcome. :)
 » 8 years ago, # |   +8 Is it possible to arrange some contests on weekends? Looks like the upcoming ones are either on Friday or Monday. Thanks.