### Lewin's blog

By Lewin, 4 years ago, ,

Hello Codeforces!

I invite all of you to participate in regular Codeforces round #309 that will take place on 24 June, 19:30 MSK.

Some of you may know me as lg5293 on Topcoder (you can see some of my past problems here), but this is my first time ever writing a Codeforces round. I've designed all the problems myself and I hope you enjoy them.

I want to thank ctunoku for helping me come up with stories for the problems, Zlobober for his immense help with preparation for this round, winger for testing the problems, Delinur for translating statements, and of course MikeMirzayanov for the superb Codeforces and Polygon systems.

I hope to see you all at the round. Good luck and have fun! :)

UPD: Scoring will be dynamic. Problems will be arranged by what I think is increasing difficulty.

UPD: Editorial is here. Congratulations to the top 5:

Div 1:

Div2:

• +567

 » 4 years ago, # |   +132 I know you as a guy who writes huge answers explaining people who don't get the solutions :D . Huge editorials incoming
•  » » 4 years ago, # ^ |   +141 Thanks :) I'll try to live up to your expectations.
 » 4 years ago, # | ← Rev. 2 →   +60 A month without div1 and 2 separated contest!Last div1 and 2 contest was held on May/26/2015 Codeforces Round #305 (Div. 1) Codeforces Round #305 (Div. 2)... I wish we can enjoy your problem set.
•  » » 4 years ago, # ^ |   +51 Month without div1 and div2 separated contest — and now we'll have 2 such contests in 3 days :)
•  » » » 4 years ago, # ^ |   +23 Really... I agree with you. I have been waiting this contests... good luck all of participants....
 » 4 years ago, # |   +25 Nice, your problems are usually interesting. Too bad the round is at such a bad time for us in the Americas. I'd really wish there would be more rounds on weekends or just more variety in the contest times to benefit all time zones...
 » 4 years ago, # |   +18 This might be a weird question, but for the last round you wrote for topcoder, div 2 1000 points, is there a proof of the pattern, or must one simply notice it? Thanks.
•  » » 4 years ago, # ^ |   +13 misof describes it in this comment. The key idea to note is to count the same thing, but in a different way.
 » 4 years ago, # |   +22 i hope less no of unrated people in div2 since there is a div1 contest this time
•  » » 4 years ago, # ^ |   +57 Like you ?!
 » 4 years ago, # |   +41 Finally, Div.1 come!
•  » » 4 years ago, # ^ | ← Rev. 2 →   +25 Congratulations)
 » 4 years ago, # |   +18 eagrly waiting for div 2 intresting problems.. :)
 » 4 years ago, # |   +67 Look at your TopCoder problems, I see a lot of maths, geometry, but few graph. Will this contest have almost maths and geometry?
•  » » 4 years ago, # ^ |   +4 I'm hoping for some data structures ... :P
•  » » » 4 years ago, # ^ |   +23 Would be great if problems are of different types, imho :)
•  » » 4 years ago, # ^ |   +9 i study math olympiad. and i do programming for fun. i hope this contest have many math problems.
•  » » » 4 years ago, # ^ |   +18 Then it would be a math contest, not a programming contest :(
•  » » 4 years ago, # ^ |   +25 Let's hope not...I want data structures, sqrt-decomposition, trees, graph theory in general, etc..
•  » » » 4 years ago, # ^ |   +1 Your taste is like mine :)))
•  » » » 4 years ago, # ^ |   +23 How about a good dynamic programming problem?
 » 4 years ago, # |   +35 Please make the problem statements clear and concise . I particularly don't like problems which are hard to understand . :D .
 » 4 years ago, # |   +30 My first Div1 :D
•  » » 4 years ago, # ^ |   0 :(
 » 4 years ago, # |   -37 i didn't participate in tc for almost 5 month
 » 4 years ago, # |   +21 The first semester and the final exam just ended today...! I'm so happy to take CF at home, not dorm.
 » 4 years ago, # |   0 good round but bad time :(
•  » » 4 years ago, # ^ |   +21 Not so bad time...
•  » » 4 years ago, # ^ |   0 really bad time!because of final exams
•  » » » 4 years ago, # ^ |   +13 If you want to participate, exams can not prevent ;)
 » 4 years ago, # | ← Rev. 2 →   +24 I wish good luck to all students in the final exams successfully submit.:)
•  » » 4 years ago, # ^ |   +18 Yes, luck may help some of us :) Thnx)
 » 4 years ago, # |   +610 Just a pic about my CF contest style:
 » 4 years ago, # | ← Rev. 2 →   +24 Hope that contest will not as hard as contests of allllekssssa and PrinceOfPersia.
 » 4 years ago, # |   +11 the blog post doesn't say anything about hacks :D
 » 4 years ago, # |   -23 I think this contest have At least one Geometric problem
•  » » 4 years ago, # ^ |   +2 You hope...
•  » » 4 years ago, # ^ |   +1 Ooo I love geometric problems))
 » 4 years ago, # |   -53 I belong to the first...
•  » » 4 years ago, # ^ | ← Rev. 2 →   +3 main(){ itoa(2, col, 2); if(strcmp(col, "10") == 0) mark ++; else mark --; printf("%d", mark); } 
•  » » 4 years ago, # ^ |   +12 I don't know Russian but I guess this is the joke about binary system, isn't it? please translate for us
•  » » » 4 years ago, # ^ |   +12 There is 10 types of humans in the world. Those who understand binary code and those who doesn't
•  » » » » 4 years ago, # ^ |   +160 So my guess was correct :D how about this one:There are 10 types of humans in the world: those who know binary system , those who doesn't and those who didn't expect this joke to be about ternary system
•  » » » » » 4 years ago, # ^ |   +78 There are 10 types of people in the world: those who understand hexadecimal, and F the rest.
•  » » 4 years ago, # ^ |   -21 To people who click minus for this picture, you are very stupid! Yes, I'm waiting for minuses for this comment too...
 » 4 years ago, # |   0 Hope I become Expert in this round
•  » » 4 years ago, # ^ |   0 Good luck)
 » 4 years ago, # |   0 yeah~The contest FINALLY comes,I have been wait for so long ....
 » 4 years ago, # | ← Rev. 3 →   +11 I liked the problems of your topcoder SRM 652. I hoped it would be rated.
 » 4 years ago, # |   -10 Izi problem, izi life
•  » » 4 years ago, # ^ | ← Rev. 2 →   -6 Difference?. Shaikhitdin's comment was +9 1 minutes ago.
•  » » 4 years ago, # ^ |   +1 i think you don't have another words, am i right? you always write the same.....
•  » » 4 years ago, # ^ |   -8 Such comments don't make your life "izi"!
 » 4 years ago, # |   0 Scoring? . . .
•  » » 4 years ago, # ^ |   0 Dynamic ):
•  » » » 4 years ago, # ^ |   0 what does this mean ?
•  » » » » 4 years ago, # ^ |   0 It means that the maximum scoring for a problem will depend on the total number of participants who send an AC solution i.e. the more people who solve a problem, the less that problem will value.
•  » » » » » 4 years ago, # ^ |   0 thanks !
 » 4 years ago, # |   -29 beijing-----》00:30，shi fen dan teng！！（Very egg pain！！）
 » 4 years ago, # |   0 Since last job change, my rating was down down down. Hope this round would add some points. 00:30 for chinese player is too later in night.
•  » » 4 years ago, # ^ |   +124
•  » » » 4 years ago, # ^ | ← Rev. 2 →   -17 Never mind :(
 » 4 years ago, # | ← Rev. 2 →   0 1
 » 4 years ago, # |   +5 Codeforces is temporary unavailable ... :(
 » 4 years ago, # |   +27 There was a lot of "website was not available" stuff... did anyone else experience this?
 » 4 years ago, # |   +4 I couldn't open any problem for the first 5 min... :\
•  » » 4 years ago, # ^ |   0 You will get extra 10 mins
•  » » » 4 years ago, # ^ |   +3 but people have already submitted before i was able to open a question
 » 4 years ago, # |   +9 will this be an unrated round ?
 » 4 years ago, # |   0 Why do you block recent actions page, the most useful page here, during the rounds?
 » 4 years ago, # |   +180 Guys, sorry about failure on start. The reason is quite funny. Because of huge number of participants I blocked some pages to reduce system load. I don't know why, but this time I've blocked user profile page. But our internal monitorings have rule like  if failed url http://127.0.0.1:8088/profile/tourist and content == "Grandmaster" with timeout 10 seconds for 4 times within 5 cycles then restart So monitoring systems decided that Codeforces servers were down and restarted them just before the round. And they were restarting Codeforces serveres again and again... until I unblocked user profile page.Sorry participants, sorry lewin :(
•  » » 4 years ago, # ^ |   0 It's alright! Thanks so much for your work and contributions!
•  » » 4 years ago, # ^ |   -38 IMHO, Codeforces should consider the option to limit the number of participants to reduce system load (like TopCoder).
•  » » 4 years ago, # ^ |   +53 So this means if tourist is no longer red, Codeforces servers will lock down in shock?
•  » » » 4 years ago, # ^ |   +56 Exactly. And not only Codeforces servers but me too.
•  » » » 4 years ago, # ^ |   +10 or when tourist decided to change his handle to something else...?
•  » » » » 4 years ago, # ^ |   0 No, because now codeforces redirects links with old usernames to their actual profiles.
 » 4 years ago, # | ← Rev. 2 →   -25 REALLY? So many math problem in div 1 and 2. I honestly think that this round is pretty bad as almost all problems are only rely on math which are hard imo. I am not good at math and i feel very desperate. I hope next time will have a normal programming contest instead of math contest.
•  » » 4 years ago, # ^ |   +4 You should be aware of that possibility by looking at the previous writer's TopCoder problems.
 » 4 years ago, # |   +28 Feeling like back in Permutation and Combination classes :(
•  » » 4 years ago, # ^ |   +22 feeling like imo paper
 » 4 years ago, # |   0 The clarification in problem B changes completely its meaning. I submit a solution to this problem for the wrong meaning, of course, getting WA. Changing it to the new problem required a lot of more code, so i'll pass ;(
•  » » 4 years ago, # ^ |   0 No it doesn't, the problem statement is perfectly clear:You start out with a bunch of cycles. Then you shift each cycle until it has its largest element first (it doesn't state that you are allowed to alter the cycles meaning so you can only shift). Then you sort the cycles with respect to each cycles first element (this can't be taken as sorting the elements in each cycle since the elements doesn't have a first element to sort by). This way we get a unique representation of each permutation.There is no other way to read it.
 » 4 years ago, # |   +5 Div1A felt harder than Div1B :(
•  » » 4 years ago, # ^ | ← Rev. 2 →   -18 All you had to do was scan a number and print 25*n+1. Easiest problem I have ever solved.
•  » » » 4 years ago, # ^ |   +3 That's Div2A, he is talking about Div2C.
 » 4 years ago, # |   +43 Nice problems, looking forward to your next round ;)
 » 4 years ago, # |   +6 Lots of fun Math in this contest!
 » 4 years ago, # |   +13 And not a single hack was given today.... :P
•  » » 4 years ago, # ^ |   +3 I was a single hacker in div2 today :D
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 great job.
 » 4 years ago, # |   0 I wish I read the announcement...
 » 4 years ago, # |   +4 why is problemset still blocked ? i am waiting to submit a code from 2 hours and still cant submit
 » 4 years ago, # | ← Rev. 3 →   +7
•  » » 4 years ago, # ^ |   0 Fix the link
 » 4 years ago, # | ← Rev. 4 →   +8 Today's Div1A/Div2C is same as this problem of LightOJ !! As LightOJ requires login, you could see it here !!
•  » » 4 years ago, # ^ |   +31 I'm sorry for the collision. Hopefully you found the other problems enjoyable.
•  » » » 4 years ago, # ^ |   +4 The other problems blown upon our head. That means the domain of those problems were Out of Range of most of us!! However, Thanks a lot!
 » 4 years ago, # |   +3 Before resubmitting one should read the whole input restriction again. In Div1 A/Div2 C, I check that no of ball should be less than 1000 but forget to read that sum of them will be less than <= 1000 lost many points due to that.
 » 4 years ago, # |   0 didn't like at all. Mostly math problems. is it mathforces or what?
 » 4 years ago, # |   +11 I wish the contest could be extended by 2 more minutes....drat! I finally coded C and time up!
•  » » 4 years ago, # ^ |   0 And it would've been Accepted had I been 2 minutes faster :******(
 » 4 years ago, # | ← Rev. 4 →   0 UPD. Nevermind, I got my mistake.can someone kindly tell me what is wrong with my code?I am basically doing search over number of possible splits of set of indexes. Number of ways to split n-element set on k subsets is Cn - 1n - k. Thus, of all possible splittings is . (F[n] in my code.)So, I am simply doing search on my code according to the following rule. Suppose we are at position i(1 based). If F[n - i] >  = k, then we need to merge this element with the next one (i + 1). Subtract k from F[n-i] and check if we have to merge current element i with the i + 2. When we face with the element j with which we do not have to merge current i element, we simply write {j-1, j-2, ..., i} to output array and move to position j.For some reason, this fails. Code seems to be fine. I think the problem is in my idea. Could someone kindly tell me why what I am doing is wrong?
•  » » 4 years ago, # ^ |   0 Sorry, can't see your code yet
•  » » 4 years ago, # ^ |   0 All subsets must have size 1 or 2. This is because the smallest element in a subset must point to the largest, because the largest must be listed first in the cycle. Which also means that the smallest element must be listed last in the cycle (so it points to the first).
 » 4 years ago, # |   +71 Someone really likes combinatorics.
•  » » 4 years ago, # ^ |   +16 If you want to do well in competitive programming, combinatorics is must.
•  » » » 4 years ago, # ^ |   0 I know.
•  » » 4 years ago, # ^ |   +28 How did you know!?
•  » » » 4 years ago, # ^ |   0 I thought you like DP.
 » 4 years ago, # |   0 only 1 unrated in top 10 of div2 :o
•  » » 4 years ago, # ^ |   0 not now :P
•  » » » 4 years ago, # ^ |   0 wow
 » 4 years ago, # |   0 Couldn't make a challenge on time cause my test with a size of 1mb was suggested to be too large. It was really a big surprise.(
•  » » 4 years ago, # ^ |   0 You could use a generator?
•  » » » 4 years ago, # ^ |   +16 There were like 20 seconds before the end. I couldn't quickly understand what's the appropriate format. I've never used generators button before, so...(
 » 4 years ago, # |   +3 It was fun solving the problems. A different contest from rest ones.
 » 4 years ago, # |   0 Look at this and tell me what is the difference between these two submissions??? http://codeforces.com/contest/554/submission/11741175http://codeforces.com/contest/554/submission/11746517
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 It does not allow to view others solution so early so be patient :P
•  » » » 4 years ago, # ^ |   0 Thanks but both are exactly same except in one solution I have added ios_base::sync_with_stdio and in other one I have removed it. The one with ios_base get wrong answer on pretest one and I wasted exactly one hour to find solution for B (div2) and resubmitted again and it got accepted :( :( I need exactly 20 second to submit C :(
•  » » » » 4 years ago, # ^ |   +4 ios_base::sync_with_stdio(false); turns of synchronisation between cin and scanf, which means you cannot use both at the same time anymore.
•  » » » » » 4 years ago, # ^ |   0 ohhh!! Hell sorry I didn't know about that :( :(1 mistake cost me 1 question I will remember this forever now.
•  » » 4 years ago, # ^ |   +3 you initialized the j variables in the second loop differently
•  » » » 4 years ago, # ^ |   0 That should not make any difference!
•  » » 4 years ago, # ^ |   0 it's that line ios_base::sync_with_stdio(false); 
•  » » » 4 years ago, # ^ |   0 and yes one passed the pretest and other failed on pretest 1 why?
 » 4 years ago, # |   +1 how do you solve "**Kyoya and Colored Balls**" pls share ur ideas
•  » » 4 years ago, # ^ |   0 dynamic programming + combinatorics.dp[i][j] numbers of ways to fit in the first i all the balls from 1-j(all means all c[1],c[2]...c[j])so that at the i-th position I put the last ball of color j.So from that I can say that the last ball of j-1 color can be between 1 and i-1(to respect the condition from problem text)and also I have some space left after coming from dp[x][j-1](x
•  » » 4 years ago, # ^ |   0 Just do combinatorics, first place all balls of color 1, this can be done in one way. Then place all colors of color 2, one of them must be behind all of color 1 balls so it can be placed in one way. The rest of them has to be put between all of the previously put balls which is a standard combinatorics problem (becomes choose(placed_balls, new_balls + placed_balls - 1)). The order of the already placed balls doesn't matter so you just multiply together all of these values. See this submission:http://codeforces.com/contest/553/submission/11739706
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 can you explain why this is not working for pretest 2: we have balls 1 2 3 4. According to formula we take 1 first.for next color C(1 + 1, 1) = 2for next color C(1 + 2 + 2, 2) = 20for next color C(1 + 2 + 3 + 3, 3) = 841 * 2 * 20 * 84 = 3360 and not 1680 as it should be
•  » » » » 4 years ago, # ^ |   0 C(5,2) = 10
•  » » » » » 4 years ago, # ^ |   0 ohhh. Thank you so much! U saved my day
 » 4 years ago, # |   +1 Answer for C is 2^(number_of_components — 1) if answer exists and 0 otherwise.
•  » » 4 years ago, # ^ |   0 Can you prove this?
•  » » » 4 years ago, # ^ |   0 Well any connected component has an unique way of being filled with missing edges. So take two components and a vertex from each one. You have two options, to either make it love or hate, from then on the components are connected and filling the other edges is unique again. So to merge two components you have 2 options, hence the 2^(components-1) to merge them all.I don't have a formal proof of it being unique, but it is pretty easy to see it if you work it out on paper
•  » » » » 4 years ago, # ^ |   0 How did you check that answer exists? Because I think that my check is harder than expected.
•  » » » » » 4 years ago, # ^ |   +13 To check if answer exists assume any two nodes joined by love edge need to be colored with same color and any two edges joined with hate edge need to be colored differently. If you are able to get a valid 2-coloring(doable by a single dfs much like we do for checking bipartiteness of graph) then that particular component is ok.
•  » » » » 4 years ago, # ^ |   0 Oooohhhh.... I didn't think this way. Thanks
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 let's assume that edge 0 means love and 1 means hate (opposite of input) now assignment to the edges of complete graph is valid if and only if you can assign to each node value 0 or 1 such that for every edge its value is equal to the XOR of its two nodesso our problem now changes to assigning values to the nodes instead of edges for each competent there's exactly zero or two ways to assigns values to the nodes (if you find one assignment then by flipping the values of all nodes of this competent you get the other valid assignment)if there's a component with zero ways to assign values to its nodes then final answer is zero otherwise the answer if 2^(number of components) (because we are multiplying the ways of all components)
•  » » 4 years ago, # ^ |   0 Div1 C or Div2 C ??
•  » » » 4 years ago, # ^ |   0 Div. 1 C
 » 4 years ago, # |   0 What was the idea for problem Love triangles.I was only able to deduce the relations that must hold for a successful match but finding ways seemed to be a distant dream.Anyone?
 » 4 years ago, # |   0 Div 2 problem C was awesome !
•  » » 4 years ago, # ^ |   +1 How to solve it? I did'n even understand the 2nd example answer, how do we get it?
•  » » » 4 years ago, # ^ |   +3 You have to use multinomial theorem.Take out 1 sample of each colour and then arrange the rest in front of it.Start from color 1 and move behind and multiply the ways you can get it .
•  » » » 4 years ago, # ^ |   0 http://ideone.com/3FLh1G But I didn't submit it.
•  » » » 4 years ago, # ^ |   0 my approach is close to DP, suppose we already placed the colored balls 1 ..k-1, thenwe must place one k-colored ball at the end of the sequence and we place the remainingk-colored ball among the the 1..k-1 colored ball already placed , which is a classical problem of combinatorics then we iterate allover the colors and that gives the resultsorry for my poor english
•  » » » 4 years ago, # ^ | ← Rev. 3 →   +1 First all the balls of colors from 1 to i should be put before the last ball of ith color. So let's say that dp[i] gives the no of ways of arranging balls till ith color. Balls of colors from 1 to i-1 are arranged in dp[i-1] ways. There are s[i-1] = (c[1]+c[2]+ .. c[i-1]) balls arranged till now. Also put a ball of ith color at the end. Now there are s[i-1]+1 gaps between the balls that must be filled with c[i]-1 balls. No of ways of doing this tmp = (n+r-1)C(r-1) where r = gaps = s[i-1]+1 and n = balls = c[i-1]-1. Now dp[i] = dp[i-1]*tmp. Answer is dp[k]. Here is the 11741519
•  » » 4 years ago, # ^ |   0 Looking forward to seeing editorial for it.
 » 4 years ago, # |   0 Was the score of the problem B changed ? Cause I saw a sudden drop in my scores for problem B ? I think something is wrong here
•  » » 4 years ago, # ^ |   0 The scoring was dynamic today..
•  » » 4 years ago, # ^ |   0 This contest had Dynamic Scoring.
 » 4 years ago, # |   +39 After this contest, it reminds me of an amazing word — aftermath!
•  » » 4 years ago, # ^ |   -8 I didn't find any only-math problem in div 2. they all could be solved non-matematically as well.
•  » » » 4 years ago, # ^ |   +14 In div2, C(div1 A),D(div1 B),E(div1 C) can be solved by maths... C(div1 A) is Combination number. D(div1 B) is Fibonacci number. E(div1 C) is counting the number of bipartite graph. I have solved only these three problems... Therefore I think it is a maths round!
•  » » » » 4 years ago, # ^ |   0 Combinatorics and DP go hand in hand, so I guess that's not entirely mathematical imo.
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   +9 At first, I have not noticed that the sum of c[i] is not more than 1000... So I think the sum may be as large as one million... I gave up DP and choose factorial numbers to calculate the combination numbers.
•  » » » » » » 4 years ago, # ^ |   0 Actually, a million would pass. http://ideone.com/3FLh1G
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +54 OH NOES FIBONACCI NUMBER SO ADVANCED AND COMPLICATED MATH!!AND HOW IT IS POSSIBLE TO DERIVE THAT VERY HARD FORMULA THAT NUMBER OF THOSE GRAPHS WAS 2|connected components| - 1!?!?SCREW YOU LEWIN FOR THAT AWFUL PROBLEMSET, WE WANT PROGAMMING NOT SOME DIFFERENTIAL EQUATIONS!P.S. Sorry if that seems to rude, but that's funny :P. However at least you don't complain that this contest was very bad, because there were only math problem xD (like some guys are sometimes claiming about various contests). Frankly saying, whole competitive programming is math for me :P.
•  » » » » » 4 years ago, # ^ |   +5 Exactly. There was no difficult formula or some required prior mathematical knowledge to solve a problem. It was all based on observations that you don't need to prove. Really don't understand why people complain that it was too mathy, it was just logical solutions based on observations, just because it's not some by-the-book algorithm doesn't mean it's not programming :)
•  » » » » 4 years ago, # ^ |   +16 As I already said once before — try Ad Infinitum contests at HackerRank and you'll realize that given contest is far from math :) Unless you are calling every single programming problem "math", because programming itself is math.If somebody says that binomial coefficients, number of n-digit 0-1 strings or fibonacci numbers is advanced math — I have bad news for that person.Swistakk said smart things in his message above :)
•  » » » » » 4 years ago, # ^ |   0 Hackerrank is a good place to train myself. However, it cost too much time for a Chinese to open the website.
•  » » 4 years ago, # ^ |   0 no pun intended
•  » » 4 years ago, # ^ |   0 But math is what you love most (:3」∠)
 » 4 years ago, # |   +28 Extremely fast system testing phase!
 » 4 years ago, # |   0 For the less mathematically inclined (like myself) :-Div-2 C / Div-1 A was solvable using DP as well.
•  » » 4 years ago, # ^ |   +3 can you explain??
•  » » » 4 years ago, # ^ |   +3 My method involved (hint): What must be the color of the last ball in the lineup?
•  » » » 4 years ago, # ^ |   0 We can go for a DP solution, if we consider the colors in the decreasing order. State --> (colorToUseNext, bank).After using the color for the first time (remember we are going backwards), we can add rest of the balls with the same color to our ball-bank (balls of which can be used anytime now).Alternatively, we can use a ball from the ball-bank as well.The overall idea is to construct the sequence in the reverse order, and filling the current position with either a ball from the "bank", or using a color for the first time (and adding rest of the colors to the bank, to be used later.)
 » 4 years ago, # |   +47 Ouch, resubmission penalty with dynamic scoring really hurts.
•  » » 4 years ago, # ^ |   0 you react as if pain was inflicted by physical touch !
•  » » 4 years ago, # ^ |   +9 Yes... For 250's problem, resubmission = 50 penalty = 50 minutes penalty...As for 3000's problem, resubmission = 50 penalty = 4 minutes 10 seconds penalty...
 » 4 years ago, # |   -35
•  » » 4 years ago, # ^ |   +11 Math is cool, Math is great, Math is really tricky thing.
 » 4 years ago, # |   0 i think problem D's time-limit has been set by a cruel person :| he just ruined my contest
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 What is the complexity of your solution? Mine runs in 170msEdit: My complexity is O( (n+m) log n )
•  » » 4 years ago, # ^ |   0 There is a solution, which passes comfortably (probably can be optimized to O(n + m)).
 » 4 years ago, # |   +79 In life we learn from our mistakes and in this contest i learned that "Every city will have at least one road adjacent to it." does not means the graph is connected :)
•  » » 4 years ago, # ^ |   +5 bad luck! The problems is the same, but you need see each component =(. 3 lines of code more, no?
•  » » » 4 years ago, # ^ |   +19 Yes. Exactly 3 more lines of code
 » 4 years ago, # |   +11 Ahhhh... 0,5 of wrong submission away from being on Petr's blog third time in a row! I need to do better in Friday contest :P
 » 4 years ago, # |   +8 How to solve div.1 E? I think, I know the solution in case of acyclic graph, but adding some hacks for cycles makes this solution TL =(
•  » » 4 years ago, # ^ |   0 I tried something like this:Let dp[v][r] be a best expectation if we are in vertex v and have r units of time remaining. There is a straightforward way to compute it in O(mt2) by some easy formulas and to speed it up we need to observe that in those formulas there are some convolutions. That means that we can use multiplying polynomials to compute them. However there is a really big problem with, we can't use just one FFT, because we are adding coefficients one by one and we have to be able to update result of multiplication. That can be done and is a really nice (but not that easy) exercise which I will leave up to you (this adds logarithmic factor to complexity).
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +12 Do you know any other problems involving this semi-online FFT approach? I was REALLY amazed when I came up with this idea while solving this task.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 Yes, this one: http://codeforces.com/contest/438/problem/EHere's Egor's solution which uses that semi-online FFT http://codeforces.com/contest/438/submission/6774697 , he solved that using sqrt-decomposition (which results in complexity). But first time when I encountered it was just my head, someday I came up with such problem on my own and solved it exactly using that sqrt-decomposition, but after that contest tomasz.kociumaka told me how to do this in and I tried coding it today, but lacked time.
•  » » » » 4 years ago, # ^ |   0 I've seen such approach on codechef.
 » 4 years ago, # |   +18 I loved this contest! A lot of problems to think. No theoric problems =). These are the best competitive problems!I really enjoy the contest, but i have 40 minutes to code problem D from i found the solution and I didn't solve. I need train to code faster the problems =/.Thanks lewin!
•  » » 4 years ago, # ^ |   +1 so motivated girl coder... great job!
•  » » » 4 years ago, # ^ |   0 It's not sarcasm :D
 » 4 years ago, # |   0 It was very difficult to hack in this contest
 » 4 years ago, # |   +4 When do we get ratings?
•  » » 4 years ago, # ^ |   -8 yeah waiting curiously
 » 4 years ago, # | ← Rev. 2 →   +13 is this round unrated? UPD-> rated :)
•  » » 4 years ago, # ^ | ← Rev. 2 →   +9 UPD -> unrated!! New rating is removed!
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +17 I say, "I'm violet!" Codeforces says, "Shut up, you are blue forever" UPD. I'm violet now :)
•  » » » » 4 years ago, # ^ |   0 Blue-Zoned ? No CF isn't a bitch rated again PS i had same story xD :D
 » 4 years ago, # |   +3 Isn't the statement for B wrong considering the intended solution? for example (3 1 2) is decomposed into the cycle (3 2 1) that reorders to (3 1 2) so it is good.
•  » » 4 years ago, # ^ |   0 Why does it reorder to (3 1 2)? I think it stays (3 2 1)
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +5 some people like me thought that we should sort elements of each cycle in decreasing order in order to make first element is the biggest, but until the last moment I knew that we should make shift to the sequence of the cycle to make the first element is the biggest element
•  » » » » 4 years ago, # ^ |   +3 Actually I was one of those people and I thought the whole cycle is sorted in decreasing order, but still arrived to the same solution. Isn't the solution in both cases the same, or was I just lucky?
•  » » » » » 4 years ago, # ^ |   0 since I assumed that we should sort elements of each cycle in decreasing order I assumed that for example 3 1 2 5 4 is not one of the permutations that we should count because (3 1 2) is not sorted in decreasing order
•  » » » » » » 4 years ago, # ^ |   0 But {3 1 2 5 4} indeed shouldn't be counted.
•  » » » » » » » 4 years ago, # ^ |   0 it turned out that I still don't understand the problem
•  » » » » » 4 years ago, # ^ |   0 If you sorted the whole cycle, you would count 3 2 1 5 4 for example, which you shouldn't.
•  » » » » » » 4 years ago, # ^ |   +8 No, you wouldn't. It changes: 3 2 1 5 4 -> (3 1)(2)(5 4) -> 3 1 2 5 4
•  » » » » » » » 4 years ago, # ^ |   +11 Yep, indeed, the solution for both seems to be identical so the "confusing" statement ain't an excuse :P
•  » » » » » » » 4 years ago, # ^ |   0 Point taken. I guess this problem was easier if you were more familiar with cycle notation; I made a similar mistake during the round (I understood the statement correctly though). :/
•  » » » » » 4 years ago, # ^ |   0 Yes, the solution for both the cases was same.
•  » » 4 years ago, # ^ |   -9 reordering of (3 2 1) is (3 2 1) itself.
•  » » 4 years ago, # ^ |   +5 You cannot reorder cycle in that way, because links between elements of permutation are directed.
•  » » » 4 years ago, # ^ |   0 Maybe it's just unusual wording, but aren't "reorder the elements within cycle" and "cyclically shift the elements in cycle" different things?
•  » » » » 4 years ago, # ^ |   0 Hmm, from that point of view they look different for me, agree with you.However, there was a clarification about that (around 54 minute of the contest): "In order to get standard cyclic representation, you should write elements of each cycle in order of cycle starting from the largest element of the cycle (not just in decreasing order)."
•  » » » » 4 years ago, # ^ |   +5 Sorry for the confusion. I will remember this wording in the future. Also, another thing that I could have done was to make the standard cyclic representation in the statement not be in decreasing order.
•  » » 4 years ago, # ^ |   +8 If (3,1,2) is not considered a valid permutation, then problem statement is wrong. It only asks to reorder elements in a cycle such that largest should be at the beginning, so (3,1,2) upon reordering will stay the same. The clarification was not clear to me.If it meant that you have to sort the cycle in decreasing order , then of course (3,1,2) is invalid as it reorders to (3,2,1) which is different.
 » 4 years ago, # |   +8 Thanks to the organizers of this round, problems was very interesting. I hope you will invite us to your new Codeforces rounds in future :)
 » 4 years ago, # |   +20 Really glad to see top5 in Div2 without a single newly registered user :)
 » 4 years ago, # |   +5 What's wrong? I became div1 and then rating changes are undone and am div2 again.
 » 4 years ago, # |   +21 For some reason my rating increased by 77 and then went back down a few minutes ago to what it was before the contest. Is the contest unrated?
•  » » 4 years ago, # ^ |   +22 Same here, my rating changed and then came back. What happened?
•  » » » 4 years ago, # ^ | ← Rev. 2 →   -13 .
•  » » » » 4 years ago, # ^ |   0 Maybe they are just catching cheaters.
•  » » 4 years ago, # ^ |   +1 Yay it went up again! :D
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +13 Yes it did. However, I gained 38 rating points in the previous rating update. This time I gained one less rating point, although my rank went up by one :PIt seems like they caught one cheater :)
 » 4 years ago, # |   +12 Had become Candidate Master for the first time. I thought it would last for at least 1 contest. :P I should have saved the screenshot.
•  » » 4 years ago, # ^ |   0 You can save it now :P All rating changes have been rolled back. (for sometime I guess)
 » 4 years ago, # |   0 For me solving div2 D (div1 B) was completely random. Observing the complex problem statement I've implemented precalc which filters valid permutations out of all the permutations (with std::next_permutation) and then I've noticed the Fibonacci sequence :)
 » 4 years ago, # |   +8 Where are the rating points gone ?!
•  » » 4 years ago, # ^ |   +2 they are back :)
 » 4 years ago, # |   -32 Div 1- Ques BIn Testcase 5, the result for (10,57) is 2 1 3 4 5 6 7 8 10 9When I generated the sequence using my cod, the following is the output. Where is it wrong?(10,1) -> 1 2 3 4 5 6 7 8 9 10 (10,2) -> 1 2 3 4 5 6 7 8 10 9 (10,3) -> 1 2 3 4 5 6 7 9 8 10 (10,4) -> 1 2 3 4 5 6 7 10 9 8 (10,5) -> 1 2 3 4 5 6 8 7 9 10 (10,6) -> 1 2 3 4 5 6 8 7 10 9 (10,7) -> 1 2 3 4 5 6 9 8 7 10 (10,8) -> 1 2 3 4 5 6 10 9 8 7 (10,9) -> 1 2 3 4 5 7 6 8 9 10 (10,10) -> 1 2 3 4 5 7 6 8 10 9 (10,11) -> 1 2 3 4 5 7 6 9 8 10 (10,12) -> 1 2 3 4 5 7 6 10 9 8 (10,13) -> 1 2 3 4 5 8 7 6 9 10 (10,14) -> 1 2 3 4 5 8 7 6 10 9 (10,15) -> 1 2 3 4 5 9 8 7 6 10 (10,16) -> 1 2 3 4 5 10 9 8 7 6 (10,17) -> 1 2 3 4 6 5 7 8 9 10 (10,18) -> 1 2 3 4 6 5 7 8 10 9 (10,19) -> 1 2 3 4 6 5 7 9 8 10 (10,20) -> 1 2 3 4 6 5 7 10 9 8 (10,21) -> 1 2 3 4 6 5 8 7 9 10 (10,22) -> 1 2 3 4 6 5 8 7 10 9 (10,23) -> 1 2 3 4 6 5 9 8 7 10 (10,24) -> 1 2 3 4 6 5 10 9 8 7 (10,25) -> 1 2 3 4 7 6 5 8 9 10 (10,26) -> 1 2 3 4 7 6 5 8 10 9 (10,27) -> 1 2 3 4 7 6 5 9 8 10 (10,28) -> 1 2 3 4 7 6 5 10 9 8 (10,29) -> 1 2 3 4 8 7 6 5 9 10 (10,30) -> 1 2 3 4 8 7 6 5 10 9 (10,31) -> 1 2 3 4 9 8 7 6 5 10 (10,32) -> 1 2 3 4 10 9 8 7 6 5 (10,33) -> 1 2 3 5 4 6 7 8 9 10 (10,34) -> 1 2 3 5 4 6 7 8 10 9 (10,35) -> 1 2 3 5 4 6 7 9 8 10 (10,36) -> 1 2 3 5 4 6 7 10 9 8 (10,37) -> 1 2 3 5 4 6 8 7 9 10 (10,38) -> 1 2 3 5 4 6 8 7 10 9 (10,39) -> 1 2 3 5 4 6 9 8 7 10 (10,40) -> 1 2 3 5 4 6 10 9 8 7 (10,41) -> 1 2 3 5 4 7 6 8 9 10 (10,42) -> 1 2 3 5 4 7 6 8 10 9 (10,43) -> 1 2 3 5 4 7 6 9 8 10 (10,44) -> 1 2 3 5 4 7 6 10 9 8 (10,45) -> 1 2 3 5 4 8 7 6 9 10 (10,46) -> 1 2 3 5 4 8 7 6 10 9 (10,47) -> 1 2 3 5 4 9 8 7 6 10 (10,48) -> 1 2 3 5 4 10 9 8 7 6 (10,49) -> 1 2 3 6 5 4 7 8 9 10 (10,50) -> 1 2 3 6 5 4 7 8 10 9 (10,51) -> 1 2 3 6 5 4 7 9 8 10 (10,52) -> 1 2 3 6 5 4 7 10 9 8 (10,53) -> 1 2 3 6 5 4 8 7 9 10 (10,54) -> 1 2 3 6 5 4 8 7 10 9 (10,55) -> 1 2 3 6 5 4 9 8 7 10 (10,56) -> 1 2 3 6 5 4 10 9 8 7 (10,57) -> 1 2 3 7 6 5 4 8 9 10 (10,58) -> 1 2 3 7 6 5 4 8 10 9 (10,59) -> 1 2 3 7 6 5 4 9 8 10 (10,60) -> 1 2 3 7 6 5 4 10 9 8
•  » » 4 years ago, # ^ |   +11 (10,4) -> 1 2 3 4 5 6 7 10 9 8 is not validThe cyclic sequence will be (1)(2)(3)(4)(5)(6)(7)(9)(10 8)
•  » » » 4 years ago, # ^ |   0 ok got it , thanks.I read the ques wrongly.
 » 4 years ago, # |   +9 Rating update (1699) :O ... i would have gotten this point if i would have entered the contest without 8 minutes temporary unavailable :'(
 » 4 years ago, # |   0 Can I ask about the 10 minutes that you added to the contest duration . did you took that in consideration while rating after contest or not ?
 » 4 years ago, # |   0 Either I am stupid or div 2 D is actually hard to understand. I still don't understand what the question wants me to do.
 » 4 years ago, # |   +3 Very cool problemset, thank you :).
 » 4 years ago, # |   0 The problem set was awesome, loved to solve it :)