By zeliboba, 6 years ago, translation,

Hi, Codeforces!

Codeforces Round 317 will take place on August, 22 at 19:30 MSK.

The round is prepared by AimFund employees: Kostroma, riadwaw, yarrr, gchebanov, ArtDitel, SirShokoladina and zeliboba.

Scoring system will be static.

Thanks to Mike Mirzayanov(MikeMirzayanov) for brilliant platforms Polygon and Codeforces, problem coordinator Max Akhmedov (Zlobober) and Maria Belova (Delinur) for English translation.

This round is prepared as part of "5 years" Codeforces program as our present to community. This round is the first Thanks-Round devoted to companies donated significant money.

We wish you good luck and high frequency rating!

P.S: scoring 1 div 750-1250-1500-2000-2750. 2 div 500-1000-1750-2250-2500

P.P.S. Top-20 div2 participants will be awarded t-shirts.

Analysis

P.P.P.S. Dear friends. We are pleased to inform you that t shirts delivery will be under way next week. We hope you will really like them. Our sincere congrats again to you all!

• +468

 » 6 years ago, # |   -263 If you in div2 and you want win T-shirt upvote this comment
•  » » 6 years ago, # ^ |   +25 You know if they do that nothing changes...Cause all of div.1 programmers will join in div.2 by another account and not only you won't get any t-shirt but also you may have worse rank and rating...
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +10 Would be interesting with 10 extra T-shirts. For the first to solve each question.
•  » » » » 6 years ago, # ^ |   +5 Hmmmmm... :/It's a good idea at all but again nothing changes for div.2 users i guess...(at least for problem C,D,E div.2)
•  » » » » » 6 years ago, # ^ |   +3 Be careful. When someone says 10 extra T-shirts, It means first accept for each question and each division.
•  » » » » » » 6 years ago, # ^ |   +3 I knew that...But the div.1 participants again will join div.2 and they have better chance to get t-shirts(also they can use 2 accounts and if they didn't success to get t-shirts in div.2 they will fight for top200)
•  » » » » » » » 6 years ago, # ^ |   +5 Maybe you are right, I was not careful, I have to accept my mistake.
•  » » 6 years ago, # ^ |   +21 Really? Why do you think all the people are like you? Contests are for challenges and learning more.
 » 6 years ago, # |   +13 this round is not combined. so "Top 200 participants" means?
•  » » 6 years ago, # ^ |   +14 Top 200 of Div. 1 according to the email they sent.
 » 6 years ago, # | ← Rev. 2 →   +16 Is it rated round?!
•  » » 6 years ago, # ^ |   +21 Yes, as usual
•  » » » 6 years ago, # ^ |   0 Thanks :D
 » 6 years ago, # |   +26 I think it should be combined division round :)
•  » » 6 years ago, # ^ |   +34 Sorry, but we haven't got appropriate problems for combined round.
•  » » » 6 years ago, # ^ |   -18 Then, Top 200?
•  » » » » 6 years ago, # ^ |   +4 Top 200 will awarded T-shirts
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +5 Okay, but it's a bit sad. Combined rounds are great :P If you want, and if you have time for it, you can think about change it to combined round, for example taking some problems from div2, other from div1 and maybe add one additional problem? I think cf community would really enjoy it, am I right? :D
•  » » » » 6 years ago, # ^ |   +78 "Combined rounds are great" — no, they are not. Actually I'm very happy that this round will not be combined.
•  » » » » » 6 years ago, # ^ |   0 Why? I'm actually unsure on the matter and I think it'd be interesting to hear opinions from both sides.
•  » » » » » » 6 years ago, # ^ |   +18 Basically because there are huge rating rises and problems tend to end up unbalanced with too many easy ones for a red (that's a thing with normal rounds as well, but a gap between C and D out of 5 isn't as bad as a gap between F and G out of 8).The authors of the round probably realised it.
•  » » » 6 years ago, # ^ |   0 yes,separate round gives more learning opp. to the newbies .
•  » » 6 years ago, # ^ | ← Rev. 2 →   +57 Am I the only one around here,who feels that combined division round causes worse rating inflation.My friend increases rating very heavily, even skips a color (blue to orange, skipping purple) on a combined division round.
•  » » » 6 years ago, # ^ |   0 I think the reason is that many who have been away from competitive programming for a while comes back for the combined rounds. Their rating will be at the level when they were at their top, but now they are rusty so they will lose points on average meaning that everyone else will gain points on average.
•  » » » » 6 years ago, # ^ |   0 But because of rating inflation, those who comes back after a long time doesn't have very high rating.
•  » » » » » 6 years ago, # ^ |   0 Rating inflation only effect div 1 since the flow between div 1 and div 2 is so slow. That's another thing, rating can only enter div 1, rating never leaves div 1 except for combined contests. I wonder how TC handles this, they don't have combined contests right and the rating have been pumped from div 1 to div 2 for like over 10 years right?
•  » » » » » 6 years ago, # ^ |   0 I checked some old accounts now, most have rating curves roughly like this:http://codeforces.com/profile/hos.lyricYou can't really see the rating inflation on them since most of them haven't gained anything the past 2 years even though they played continuously. If they had stopped for 2 years instead and then came back they would definitely have too much rating!
 » 6 years ago, # |   +76 There were old legends about some company planning to run their round within the next month... :DLooking forward for your round guys!
 » 6 years ago, # |   -26 Div 1 users : "It's time to register for Div.2" :((
•  » » 6 years ago, # ^ |   0 why would div1 users want to register in div2?
•  » » » 6 years ago, # ^ |   -32 cuz when its not division combined , getting Tshirts in div2 is easier in for low rated div1 users :)
•  » » » » 6 years ago, # ^ |   +12 It's written that top200 in div1 will receive t-shirt.
•  » » » » » 6 years ago, # ^ |   0 oh sorry
 » 6 years ago, # | ← Rev. 2 →   -26 Oh Yes,I think this contest is like Goodbye contest and All user Receive high rating
 » 6 years ago, # |   +2 Hello, what do you mean by "Scoring system will be static" ? what's the difference with the last round ?
•  » » 6 years ago, # ^ |   0 "Scoring system will be static" it is mean, that scoring system won't be dinamyc (max scores for problems you will know before round)
 » 6 years ago, # |   +17 Though its very obvious only Div — 1 will get t-shirt and they should get but it will more exciting for all Div — 2 coders like me if we get a chance to complete with Div — 1 coders . A collaborate Div 1 & 2 round will be more interesting for everyone and Div — 2 coders get a chance to win t-shirt also .
•  » » 6 years ago, # ^ |   +9 If it's combined, ((we will fight to win a t-shirt but nothing will happen as usual)) :D
•  » » » 6 years ago, # ^ |   +14 I didn't perform well any of previous collaborate contest but i like these contest most because one can get the proper picture of his/her current state . So just the opportunity to participate with Div 1 coders is enough for me :D
 » 6 years ago, # |   -31 when you want to give t-shirts. you must prepare one both division contest.(like round Codeforces Round #300)
•  » » 6 years ago, # ^ |   +39 There are 0 participants from div2 in top 300.
•  » » » 6 years ago, # ^ |   +7 You can't say that man...We have lots of phenomenons like this all the time
•  » » » 6 years ago, # ^ |   0 Now a div 1 once a div 2 coder :p you never know :D
 » 6 years ago, # |   +16 thanks for preparing this codeforces round.
 » 6 years ago, # |   +19 Where can we see the t-shirt's.
 » 6 years ago, # |   -24 That's sad for div 2. Even "random x from top y" method would be great. But thanks for the contest anyway.
 » 6 years ago, # |   +19 This would be a good time to get red + T-shirt!
•  » » 6 years ago, # ^ |   +3 Meh, I'm too slow for red...
•  » » 6 years ago, # ^ |   0 Ah well, just one contest wrong.
 » 6 years ago, # |   -30 I guess if they had 400 t-shirts they would give 1 each to both division's 200 toppers. But they only have 200 t-shirts.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +7 If they give T-shirts to Div.2, we will be seeing loads of fake Div.2 users.
•  » » » 6 years ago, # ^ |   +5 Ok, That makes sense.
 » 6 years ago, # |   -23 how about allowing div 2 users to submit div 1 D and E if they solve upto div 1 C ? ( no extra time )
•  » » 6 years ago, # ^ |   -11 Yeah, surely, imagine how exactly that should look like and how big changes this will demand in whole system of Codeforces ( ͡° ͜ʖ ͡°)
 » 6 years ago, # |   -37 if a div1 user makes a fake account for div2 contests it shows that he/she is more programmer than human!i think being human is more important than being programmer!!!!
•  » » 6 years ago, # ^ |   -10 If you believe in God,... It's good to know that "**God is also a programmer**".
•  » » » 6 years ago, # ^ |   0 Never go full retard.
•  » » » » 6 years ago, # ^ |   0 It does not matter.This is possible for every programmer.
•  » » 6 years ago, # ^ |   0 of course every programmer is a human :)
•  » » » 6 years ago, # ^ |   0 Depends on if you consider computers that can program as programmers.
•  » » » » 6 years ago, # ^ |   +16 We are all machines developed by nature and evolution :)
•  » » » » » 6 years ago, # ^ |   -16 That is debatable. Prepare for downvotes, my friend :(
•  » » » » 6 years ago, # ^ |   0 I think we are computers which run the programs written by God. So God is a programmer.
 » 6 years ago, # |   -53 Will it be possible for you to provide T-shirts to some(your limit) top div2 rated contestants?
•  » » 6 years ago, # ^ |   -41 i'll buy an account gg easy
•  » » 6 years ago, # ^ |   +1 I don't know he got -30 by just proposing something. Seriously, what's wrong with these people? I honestly think that there can be very few people who can still perform in div1 top 200. And if you offer a very few T-shirts in div2 as he suggested, many coders in div2 can be challenged to perform well. It will be an inspiration for those who can win in div2.
•  » » » 6 years ago, # ^ |   +1 There will be a lot of fake accounts from div 1, because it's easy to win div 2 than being in div1 top 200.
•  » » » » 6 years ago, # ^ |   -13 Yeah possible. But if one can win in div2 and solved same quality problems as in top 200 in Div1, Why not give a T-shirt? ( Since div1 and div2 doesn't have same problems, it is troublesome I guess).
•  » » » » » 6 years ago, # ^ |   +43 Codeforces Round 300. No div2 Zeptolab code rush. No div2 Good bye 2014. No div2
•  » » » » » » 6 years ago, # ^ |   0 In Codeforces Round 300, there are two div2 participants though :P. Imagine if you were one of those guys, and you don't receive T-shirt.But I see what you're saying. It is not gonna happen 99% sure.
•  » » » » » » » 6 years ago, # ^ | ← Rev. 2 →   +37 If you are good enough to get top 200 in div 1 then it takes just a single contest to become div 1 so they can only blame themselves for not doing the contest held a week ago. If it is the unlikely case that the person have only memorized solutions and thus can't reliably get into div 1 then you could argue that they aren't worth a T-shirt even if they did well in this specific contest.
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   -39 I mentioned that.
•  » » 6 years ago, # ^ | ← Rev. 2 →   -59 I did not find too many points.
 » 6 years ago, # |   +17 I speek Croatian and Croatian is similar to Russian, can I also apply?
 » 6 years ago, # |   +2 Good luck :)
•  » » 6 years ago, # ^ |   +6 No luck just skill
•  » » » 6 years ago, # ^ |   +3 Good skill :) ???
•  » » » 6 years ago, # ^ |   0 Skill and accuracy and speed too.
 » 6 years ago, # |   0 Oh~~ sounds good~
 » 6 years ago, # | ← Rev. 10 →   -6 like aim fund contests !!!
 » 6 years ago, # |   -13 Bless All!
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 233
 » 6 years ago, # |   0 I think I will solve 2 questions today
•  » » 6 years ago, # ^ |   +2 Not important how many problems you solve...Wish you learn new things... ;)
•  » » » 6 years ago, # ^ |   0 rate is not too important it's important you learn things and enjoy from contest :D
•  » » » 6 years ago, # ^ |   0 wooow You are my hero :)
•  » » » » 6 years ago, # ^ |   +9 prince of Persia said : "you wan't to " accept " or you want to "solve" ??? " :D
•  » » » » » 6 years ago, # ^ |   0 or learn?
•  » » 6 years ago, # ^ | ← Rev. 3 →   0 I think we can do it!
 » 6 years ago, # |   0 Good luck everyone! :)
 » 6 years ago, # |   +19 Is scoring the same for both divisions?
•  » » 6 years ago, # ^ |   0 No, post fixed
 » 6 years ago, # |   +8 Last one isn't usualy 2750, right?
 » 6 years ago, # |   +27 Tough set. I guess those t-shirts are really special.
 » 6 years ago, # |   +124 div0 contest :))
•  » » 6 years ago, # ^ |   0 I think that's a great idea. One more division for the Gods :)But it'd require to prepare 2 more problems for a contest...
 » 6 years ago, # |   +6 Did anyone else get WA on problem B test 10?
•  » » 6 years ago, # ^ |   +2 So many times. And I think I figured out why: you are supposed to take the least cost sell orders, and print them descending. I think :P
•  » » » 6 years ago, # ^ |   0 I coded A and B very fast but I faild at the same point, Damn my luck.
•  » » » 6 years ago, # ^ |   0 From what I see in statement ,in the order book for sells they are sorted descending.Even if you want to take first s lowest agg sells. Tricky statement.
•  » » 6 years ago, # ^ |   +1 Yes. Then I found that I hadn't noticed this : "A buy order is better if it has higher price and a sell order is better if it has lower price". After considering it, passed.
•  » » » 6 years ago, # ^ |   0 Then I got WA for some other reason, wonder what. Any tricky cases?
•  » » » 6 years ago, # ^ |   +1 I noticed this with 1 minute left. I barely missed the submission window(was typing the cout statement once contest ended, last line of code -.-)
•  » » » 6 years ago, # ^ |   0 Ah, that makes sense. Such a shame that there was only one example.
•  » » 6 years ago, # ^ |   0 Along with 4 failed attempts, yes (
•  » » 6 years ago, # ^ |   0 Yes, you have to take the minimum items of the 'b' or 's' ( can't remember which exactly )
 » 6 years ago, # | ← Rev. 2 →   0 I am impressed. Thank you for round anyway.
 » 6 years ago, # |   0 So light pretests for div2 C( My solution with O(n^2) complexity passed them, but I know there will not be such luck on final test. So I interested how to solve it faster?
•  » » 6 years ago, # ^ |   0 How would be a n^2 solution for it? Couldn't even think about it!
•  » » » 6 years ago, # ^ |   0 Set A and B, and you can count how many possible C there are.
•  » » » » 6 years ago, # ^ |   0 Will this get TLE?
•  » » » » » 6 years ago, # ^ |   0 For sure.
•  » » 6 years ago, # ^ |   0 How did you solve it >.<
•  » » 6 years ago, # ^ | ← Rev. 2 →   +13 Just calculate the inverse instead. The total amount of ways you can increase is (l + 1)*(l + 2)*(l + 3)/6, then you just remove all cases that don't work. You can't form a triangle with a set of numbers if one is larger or equal than the sum of the other two, so just iterate over all increases (O(n)) of a, b, and c and for each increase reduce the answer by the amount of ways to increase the other two such that their sum is less than the largest one.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +29 Like this:  ll f(ll a, ll b, ll c, ll l) { if (a < b + c) return 0; ll d = min(l, a - b - c); return (d + 1) * (d + 2) / 2; } int solve(ll a, ll b, ll c, ll l) { ll ans = (l + 1) * (l + 2) * (l + 3) / 6; for (int i = 0; i <= l; ++i) { ans -= f(a + i, b, c, l - i); ans -= f(b + i, a, c, l - i); ans -= f(c + i, b, a, l - i); } cout<
•  » » » » 6 years ago, # ^ |   0 It is probably a stupid question, but why ~~~~~ ll d = min(l, a — b — c); ~~~~~
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   +1 Its the amount of increases that you can distribute between b and c. Of course you can't distribute more than l and if you distribute more than a - b - c then the triangle becomes valid.
•  » » » » » » 6 years ago, # ^ |   0 Thank you. I learned a lot...
•  » » » » 6 years ago, # ^ |   0 nice and simple solution thanks :)
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 How is it intuitive that there are no overlaps? When you're increasing 'a', you also increase 'b' and 'c' On a closer look, when you increase 'a', and hence increase 'b' and 'c', for those values always 'b'<'a'+'c' and 'c'<'a'+'b' But this wasn't really intuitive :|
•  » » » 6 years ago, # ^ |   +7 Why the total amount is (l + 1)*(l + 2)*(l + 3)/6 . I am a little bad in maths.
•  » » » » 6 years ago, # ^ | ← Rev. 3 →   +10 You should divide l indistinguishable elements to 4 groups: (increase a, increase b, increase c, do nothing). Using stars and bars technique we get
•  » » » » » 6 years ago, # ^ |   0 Thanks a lot riadwaw...
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 It's probably stupid, but could you explain how did you get formula for calculating total amount? Thanks in advance.UPD: Same comment as above, sorry for duplicate.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 suppose we increase a,b,c by x,y,zfix z then the triangle ineq conditions reduces to let v1 = x+y,v2 = x-y x+y >= max(0,(c+z)-a-b+1) x+y <= l-z x-y >= b-(c+z)-a+1 x-y <= b+(c+z)-a-1 subject to above contrainsts,we hvave to find all such pairs such that v1%2==v2%2 and v2<=|v1|to do the rest, you need to analyse each interval properly.
 » 6 years ago, # |   +61 the hardest contest i have ever seen.
 » 6 years ago, # |   +6 Div1 — A today is so mind-blowing (harder than Div1-B IMO). Is there a simple way to solve it?
•  » » 6 years ago, # ^ |   0 I tried iterating through all ways of adding an amount to a and then binary searching for the min and max values for b, therefore fixing c but could not get it to work. Is this a valid solution?
 » 6 years ago, # |   0 ... And how to solve problem A (div. 1)?
 » 6 years ago, # |   +2 How div1 B is solved by a lot of contestants it's very hard!! maybe a lot of them are going to fail system test? div1 C is far easier than div1 B but they both have almost the same points!! I didn't submit my solution because of this reason
•  » » 6 years ago, # ^ |   -10 I can prove my solution at div1B and it's not that hard
•  » » 6 years ago, # ^ |   0 div1 B is dynamic programming + some greedy approaces. Actually if you can notice, that elements, which absolute difference is taken are located in non-intersecting sequences. Also it is obvious, that elements in such sequences are neighbours in sorted array. So you should find the optimal way of splitting the sorted array in "blocks", minimizing the target function. In fact there is no more, then 2 different length of blocks are possible, so you can do DP in k^2.
•  » » » 6 years ago, # ^ |   0 Yes, this is the only observation required to solve this problem that there wont be more than 2 different lengths. Thanks for the explanation dude :)
•  » » 6 years ago, # ^ |   +1 Not exactly. C demanded a lot of stupid code, while code for B was pretty easy. C was not idealogically complicated, but not fun to code and multiedges stopped me for half an hour.
•  » » » 6 years ago, # ^ |   +5 I have implemented it in simple way:handle cases for variables appearing only once and variables appearing twice but in same sign and check which nodes are satisfied. put all unsatisfied nodes in priority_queue such that the top is the node with least degree, each time pop a node from queue and select arbitrary edge connected with that node to make that node satisfied , then delete that edge(the other node degree is reduced by 1) , if in some moment degree of a node which is not yet satisfied is 0 then "NO" otherwise "YES" didn't even have to check for trees or search for cycles
•  » » » » 6 years ago, # ^ |   0 and you even don't have to handle cases you described separately.
•  » » 6 years ago, # ^ |   0 You wont solve 1 C if you haven't seen the problem before since it is a huge research topic.Also you wont improve if you care about points, better to fail and learn than to not try at all.
•  » » » 6 years ago, # ^ |   0 This particular case it's not a huge research topic and I think I solved it(or at list I have a good and proved idea, maybe some bugs but I have a good idea) without meeting it before
•  » » » » 6 years ago, # ^ |   0 Oh, I read the problem wrong >.<.
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 Aparently, me too=)))I thought that you can have just -2 and 2 ore just one of them but you can have two of -2 or two of 2 which is very easy tot treat.I don't really understant why did they do that :(
•  » » 6 years ago, # ^ |   +5 Div1 — B is just DP: imagine we will build each subsequence {a(i), a(i+k), a(i+2*k), ..} seperately, and to make the result minimum, each subsequence must be sorted. We will have to build cnt1 = n%k subsequence of length n/k+1 and cnt0 = (n-cnt1*l1)/l0 subsequence of length n/k. Sort array a in ascending order. In order to minimize the result, there must be no pair of two subsequence that intersect with each other. So, this problem could be reduced to: finding a way to split array a (after sorted) into cnt0 continous subsequence of length l0 and cnt1 continous subsequnce of length l1. Notice that cnt0*cnt1 <= n, so a DP with complexity O(cnt0*cnt1) would work.
•  » » » 6 years ago, # ^ |   +8 You wanted to say cnt0*cnt1<=(k*k), no?
•  » » » 6 years ago, # ^ |   0 Wow, that's actually a solution I was trying to code during the contest! Can you please describe your DP a bit more detaled?
•  » » 6 years ago, # ^ |   0 B was very nice and much easier than A, at least in my oppinion. I needed about 10 minutes to figure out the dp after I read it but I still have no clue about A :(
 » 6 years ago, # |   +36 That CNF-2 (Div1-C) is easy but hard to implement (many corner cases)
•  » » 6 years ago, # ^ |   -34 If you compute the number of degenerate triangles and substract this number from the total one is very easy but it's hard to think.I guess this was the slution without corner cases
•  » » » 6 years ago, # ^ |   0 Did you mean Div1-A?
•  » » » » 6 years ago, # ^ |   -8 Yes I saw it later when I already had -30 contributin :)) but it didn't make sense to refer at div1C.There were 3 cases in my solution and I treated each of them in one line.Any way sorry for misunderstanding
•  » » 6 years ago, # ^ |   0 It may be implemented without corner cases:)
 » 6 years ago, # |   +4 2E/1C was quite interesting I know what I was supost to do but I didn't have time to implement it, stil I liked that problem. Can't wait to see the editorial :)
•  » » 6 years ago, # ^ |   +3 Yeah basically the problem is equivalent to "Given a graph can you direct it's edges so that each node has an in degree at least one".You can always do that as long as the graph is not a tree. And if it isn't finding a cycle and then directing all edges outward from that cycle does the trick. But yeah I also ran out of time to implement this.
•  » » » 6 years ago, # ^ |   0 ... as long as each component of the graph is not a tree ...
 » 6 years ago, # | ← Rev. 3 →   +22 number_of_contests_with_only_D++ :(
•  » » 6 years ago, # ^ |   0 Why would you write underscore at the end of variable? Awful.
•  » » » 6 years ago, # ^ |   +16 it was not the only stupid mistake anyway :P
•  » » » 6 years ago, # ^ |   +10 Actualy it is widely used convention if we are talking about nonpublic attributes of classes :).
 » 6 years ago, # |   0 So Cool. Congratulations to the winners.
 » 6 years ago, # |   0 And is this be standard from now on. New round every Saturday?
 » 6 years ago, # | ← Rev. 2 →   0 I got TL on the 6th pretest (Div. 2 C), and that in 2 minutes before closing... I... I could solve it... Arghh!Anyway, it was a great round!
•  » » 6 years ago, # ^ |   +3 Me too, but it seems that there's a O(n) aproach, so we couldn't solve it actually hahahaha
 » 6 years ago, # |   +106 Why is system testing stuck at 75%?
•  » » 6 years ago, # ^ |   +19 Check div2 — testing runs fine there.
•  » » 6 years ago, # ^ |   0 I guess all graders are grading Div2 at the moment
 » 6 years ago, # |   0 Is it possible to change something in code after the contest has finished if it is only 1 operator , I mean switch = and <= ?
•  » » 6 years ago, # ^ |   +8 No.
•  » » 6 years ago, # ^ |   0 yep change it and also you can submit it in practice :D
•  » » 6 years ago, # ^ |   0 Why not? Every one can. But really do you think it will be judged again?
•  » » 6 years ago, # ^ |   0 You can submit in practice after the grading finishes, but it will not affect how you performed during the competition.
•  » » 6 years ago, # ^ |   +13 Sure, why not? You are allowed to change up to 10 letters in your solution after the contest, so remember that your variable names should be short, because that way you will be able to do more changes.
•  » » » 6 years ago, # ^ |   0 haha :PSome contest allow minor changes like that , that's why I asked
•  » » » » 6 years ago, # ^ |   +38 "Some contest allow minor changes like that" — yyyy o_0. Can you give me an example of at least one :P?
 » 6 years ago, # |   +8 Thanks for preaparing this great round, also thanks for t-shirt :D
•  » » 6 years ago, # ^ |   0 t-shirt!
 » 6 years ago, # |   +3 from 25 to 1300, such is life in codeforces.
•  » » 6 years ago, # ^ |   -21 I liked your humor :)
 » 6 years ago, # | ← Rev. 2 →   +13 The contest was great ! Really hope that Round 318 will also give 200 T-shirts.
 » 6 years ago, # | ← Rev. 2 →   0 typically how long does it take before the rating changes? it was a great (hard) contest! :P
•  » » 6 years ago, # ^ |   0 15-20 min
 » 6 years ago, # |   0 could any body please say me what is the calculating way for first contesters?
•  » » 6 years ago, # ^ |   0 starting rating assumed as 1500
•  » » » 6 years ago, # ^ |   0 okay but how the rating changes?
•  » » » » 6 years ago, # ^ |   0 this and this may help.
•  » » » » » 6 years ago, # ^ |   +8 Is it just me or does that picture with the formula seem like gibberish to anybody else?
 » 6 years ago, # |   -8 I think the problem statement for Div 1 C is unclear. In the problem statement it is writtenWe know that each variable occurs in at most two clauses (with negation and without negation in total)Therefore, I thought that when a variable appears twice, the variable and its negation will both appear. Fortunately, there is test case 3 that shows that this is not true, but I did not have enough time to update my solution when I realized that.
•  » » 6 years ago, # ^ |   +24 two in total means 0+2 and 1+1 and 2+0 , no ambiguity in that
•  » » 6 years ago, # ^ |   0 I don't see how that can be understood like this. Moreover you have "at most" which suggests that sometimes it can be one (or maybe even zero?), so there will be no place for variable and its negation at one time.
•  » » » 6 years ago, # ^ |   0 Yes I know that there can be zero or one of the variable. What I meant is that the addition (with negation and without negation in total) sounded to me like we can get any subset of the set{negation, without negation}and thus in this case {negation, negation} is not possible.
 » 6 years ago, # |   -9 Just a wrong character on code of A, and using 109 as inf on code of B but answer can be 2 * 109. Why I can't learn anything? :(
 » 6 years ago, # |   +89 Late for the contest for 30 minutes, still got the T-shirt
 » 6 years ago, # |   +13 what about editorial??
 » 6 years ago, # |   +90 ScreencastIf you wouldn't shed tear when I type long[] allCumulUpds = new long[n + 1]; instead of m + 1 you have no soul
•  » » 6 years ago, # ^ |   +5 Authors have soul, I am sure. I remember Bambi’s Mother Dies, Mufasa Dies, and so on when we watched this bug realtime in your submission.
•  » » » 6 years ago, # ^ |   0 What does it mean to watch a submission realtime if you are author of a contest?
•  » » » » 6 years ago, # ^ |   0 Authors can open any solution during the contest. Also avaliable results at final testset.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +16 I noted that in this problem n denotes number of edges and m number of vertices, what will lead to inevitable errors, so I declared them as "cl" and "var" what makes it much harder to misuse them. Second technique I use is to always declare arrays of sizes of sufficient constants, here 3e5+5. Any of those two things will prevent you from making this bug :).EDIT: Heh, it seems that I messed up problems ^^. First remark is no longer relevant, however I guess second still stays.
•  » » » 6 years ago, # ^ |   +19 But 2nd technique may lead to other bugs, like Petr described in one of his recent weekly reports
•  » » » » 6 years ago, # ^ |   0 Hmmm, yeah, I guess you're sufficiently experienced to be acknowledged with both technique of making array of a 'just right size' and technique of making it big beforehand : D. Hence, my comment was probably anything new to you :P. However I use it like this for almost all my coding life and I don't remember any case when it caused a bug. Orrr maybe, concluding from what Petr has written it may prevent us from noting some bugs rather than cause them — I guess there is some tradeoff (pretty much like always). However I am a guy really prone to mistakes you did this time, so I will stick to my method.
•  » » 6 years ago, # ^ |   0 What tool do you use to parse contest problems ? Is there any github repo ?
•  » » » 6 years ago, # ^ |   0 I use CHelper
•  » » » » 6 years ago, # ^ |   0 Will check it out, thanks.
 » 6 years ago, # |   +8 Aha ..T-shirt! It's my first time to receive gift from Codeforces.. Here is my question. When will the T-shirt be sent? I can't wait to wear the lovely T-shirt!
 » 6 years ago, # |   +5 Can someone provide an editorial? Thanks
•  » » 6 years ago, # ^ |   +6 As always you may ask specific questions in comments. Now part of tutorial is published
•  » » 6 years ago, # ^ | ← Rev. 2 →   +8 With respect to C I would be very interested in a discussion of how to implement the problem well specifically the part of finding the cycle in the component of the graph and then directing all the edges.If one attempts to find the cycle with a DFS one processes nodes until an edge is found between the node we are currently processing and a node we visited earlier. It is very unclear to me how to write the recursive function so that once we find such a cycle we can exit the recursion and along the way store the cycle in some sensible way.
•  » » » 6 years ago, # ^ |   0 What I do for this is maintain a DSU while adding edges, and then when an edge is found connecting two vertices in the same set, we know there exists a cycle from one vertex on this edge.Then, we can run findcyc() from such a vertex, keeping the current dfs stack, until it reaches the starting vertex again — which it must due to the earlier argument. Thus, our cycle is isolated. Another nice thing here is that we can direct the edges along the cycle in findcyc() itself. Next we dfs() from every node on the cycle to direct the edges. 12656691Any other approaches?
•  » » » » 6 years ago, # ^ |   +8 Come to think of it with the approach you describe (which I think is the nicest one) you don't need to find the cycle and then separately perform DFSs at all.If you start the DFS from the node on the cycle you can simply direct all the edges (that haven't been directed yet) away from the current vertex. This way every vertex has an edge pointing to it (the one that caused them to be thrown on the "stack") and eventually some node also has an edge to the starting node. So you only need one DFS per component assuming you can start with a node on the cycle.
•  » » » 6 years ago, # ^ |   0 Not really proud of that code, but maybe you can get an idea how to do that by dfs: http://codeforces.com/contest/571/submission/12659401Condition on finding cycle is if (vis2[nei] && e != wh_var) { that means, I have visited that neighbour earlier and I'm not looking at the edge I used to be in current vertex.My dfs returns int. "If dfs returns nonzero value than cycle exists and returned vertex lies on a cycle and I have already assigned logical value to it". Whenever recursive call returns nonzero I stop executing and pass that value higher.
•  » » » 6 years ago, # ^ |   0 You may also appreciate version with exceptions http://codeforces.com/contest/571/submission/12667656 :P. Finding a cycle can hardly be called 'exception', but exceptions can help you unwind stack of function calls without passing intermediate values.
•  » » » 6 years ago, # ^ | ← Rev. 4 →   +3 This is my solution: (I use outgoing edge instead of incoming edge) 1.Keep removing vertices with degree 1, and assign its only edge to it.2.Now there are only vertices with degree>=2. Find a vertex which has no outgoing edge. Starting from this vertex, find an unused edge and pass through this edge. Now we find an outgoing edge for this vertex. Keep doing this to the vertex on the other side of previous edge until a vertex which already has an outgoing edge is reached. It is guarenteed that we can always "go out" from a vertex with no outgoing edge because there are at least two edges connected to it.3.If there are still vertices which has no outgoing edge, do step2 again. Otherwise, orient all unused edges arbitrarily.
 » 6 years ago, # |   +87
 » 6 years ago, # |   +93 P.P.S. Top-20 div2 participants will be awarded t-shirts.So genius that say this after contest :D
•  » » 6 years ago, # ^ |   +4 Guys looked at the results and understood that participants from div2 earned T-shirts too, cause solved many problems. Why not?
•  » » 6 years ago, # ^ |   +3 And now in next contest we'll see div1 guys playing with fakes in div2, hoping for such P.P.S. once again :)
•  » » » 6 years ago, # ^ |   +16 Add simple rule that he/she participated minimum 10 contest
•  » » » » 6 years ago, # ^ |   +5 O_oSo new users can't join the contests???Bad idea at all...
•  » » » » » 6 years ago, # ^ |   -8 Usually who win div2 — are div1 users. New user can't win contest or get top-20 in one contest.
•  » » » » » » 6 years ago, # ^ |   +8 They can if they have done competitive programming in other places like icpc or tc.
•  » » » » » » » 6 years ago, # ^ |   -16 Probability is very low I think.
•  » » » » » » 6 years ago, # ^ |   0 Ermm, having reached 3rd place in div 2 on my first contest, I beg to differ. And if you look at the standings, there are 4 more unrated people in the top 20.
 » 6 years ago, # |   0 When are you going to publish an editorial?
 » 6 years ago, # |   +24 First codeforces Tshirt :)
 » 6 years ago, # |   0 always getting wrong answer on 10th test case.iam unable to figure out .can anyone please help me :) .the link for the submission (http://codeforces.com/contest/572/submission/12670760)
•  » » 6 years ago, # ^ |   0 10th test was about wrong S and B priorities. You should write out B with bigger price and C with lower price.
 » 6 years ago, # |   0 That P.P.S made my day... :3 :D !!! Thanks all... !!!!
 » 6 years ago, # | ← Rev. 2 →   +9 Just asking out of curiosity, did you consider using the new dynamic scoring system with 250 points gaps? If you did, what was the reason behind choosing the standard scoring system instead?
•  » » 6 years ago, # ^ | ← Rev. 2 →   +11 In short, all of us do not like the dynamic system, so we have not even considered it =)
•  » » » 6 years ago, # ^ |   +20 Why? So far, according to my contest experience, there were situations that dynamic scoring would have given more appropriate scores rather than standard but have not seen the same thing for the opposite. The only problem that dynamic scoring might cause was certain formulas that can lead to different points just because of 1 submission, but now it's only 250 points which is fairly good I think. For instance, it could have fixed the point distribution in this contest too, esspecialy for A-B and C-D. I've no doubt that all scoring systems common feature is fairness as far as it's same for all the contestants. But it would not hurt to make things better, right?
•  » » » » 6 years ago, # ^ |   0 Contests are supposed to be fun and dynamic scoring makes them less fun for me since its stressful not knowing how much the problems are worth.
•  » » » » » 6 years ago, # ^ |   0 Well for me, it's more stressful when you do not know if the problem you are working on worth it's points.
•  » » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 Then why do you gamble by skipping problem A, B and C? Usually A gives the most score per effort, then B, then C, then D and lastly E, so doing them in any other order is a risky gamble.Edit: While on the other hand with dynamic scoring the effort per problem ratio can be all over the place, usually A gives the least score per effort in those contests meaning that you must try to game the system instead of just focusing on solving problems.
•  » » » » » » » 6 years ago, # ^ |   +1 Because solving just A and B is boring and I want to give more time to harder and more interesting ones. If I would have started from A and B, there would be no time for D at all. The question is if you have the power to lead all of the contestants(by setting scores) would you encourage harder problems or not?
•  » » » » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 Since they can set the scores however they want they obviously want the easier problems to be worth it, if they wanted the harder problems to be worth more they wouldn't set A and B to be 750 and 1250.
•  » » 6 years ago, # ^ |   +12 Oh, you're the first person I see which doesn't hate dynamic score :P. I like to know what is the value of a problem beforehand. Dynamic scoring often can lead to weird strategies like skipping A and B, because they will be worth 250 and 500 pts or sth like that. What matters is also strategy, not only problem solving skill and you have to admit that choosing D as only problem to solve was not best choice =). I guess that probably it was twice that hard to solve D than ABC combined, so what you did was probably harder than what I did, but my place was significantly better :P.
•  » » » 6 years ago, # ^ |   +1 I like dynamic scoring too, and I believe it would be more fair if it was applied for this contest , because how can a problem which is solved the most(problem B) have almost the same points as the problem solved by few people(problem C)!!
•  » » » » 6 years ago, # ^ |   0 Haha, that said just after stating that C was far easier than B http://codeforces.com/blog/entry/19863?#comment-247365 XDDD
•  » » » » » 6 years ago, # ^ |   +8 first problem I tried during the contest was B , but I couldn't solve it ,I thought it's harder than usual div1 B problems, so I moved to C , the idea came to me very quickly but it took me some time to code it, after finishing I saw that B was solved by a lot of contestants even more than A , and C is solved by low number of contestants so I decided to give up.I posted that comment immediately after the contest finished I was trying to express my surprise of number of people who solved B , I didn't know that I'm only missing an observation to solve B , it wasn't that hard as I thought.in the end, a lot people solved B and that's what matters so it should not have that much of points
•  » » » » » » 6 years ago, # ^ | ← Rev. 4 →   0 Just 329 people solved B, it was way harder than your average B problem. Also I really dislike contests where the easiest problem is too hard since then lots of people chickens out and it gets hard to gain rating.
 » 6 years ago, # |   0 just a friendly reminder, it's analysis not analisys (last link of the blog)
•  » » 6 years ago, # ^ |   0 Thanks
 » 6 years ago, # |   0 Is it normal that I got no message, e-mail or anything regarding the T-shirt? (I got 3rd in div 2.) I added my address details to my profile the day after the contest. This was my first time competing so I'm not really sure how things work around here..
•  » » 6 years ago, # ^ |   0 Only for Top 200 Div.1 users.
•  » » » 6 years ago, # ^ |   0 At the end of the post, added after the contest ended: "P.P.S. Top-20 div2 participants will be awarded t-shirts."
 » 6 years ago, # |   +11 When will the T-shirts be sent?
 » 6 years ago, # | ← Rev. 2 →   +3 Will the t-shirts be sent to other countries like China?
 » 6 years ago, # |   0 I still haven't received my T-shirt. Is there any information on when they will arrive (in the Netherlands)?
•  » » 6 years ago, # ^ |   0 I don't know, but we will send it to you.
 » 6 years ago, # |   +8 I still haven't received my T-shirt. Will it still be send?
•  » » 6 years ago, # ^ |   0 Hi, all T-shirts have been sent as I know.
•  » » » 6 years ago, # ^ |   0 Was that long ago? I think my address is (and was) up-to-date.
•  » » » 6 years ago, # ^ |   +11 Hi , even I haven't received my T-shirt please look into it
•  » » 6 years ago, # ^ |   0 I too haven't received it yet.Is there any mistake?
 » 6 years ago, # |   +14 Finally, just received my T-shirt today! Thank you Aim Fund, Thank you MikeMirzayanov :D