Serega's blog

By Serega, 6 years ago, translation, ,

Hello everyone!

In several days (July 24, 19:30 MSK) will take place Codeforces Round #193 (Div. 2), which I have prepared. Those who has already reached the first division traditionally can participate in the round out of the competition.

I would like to thank Vitaliy Gridnev (gridnevvvit), Pavel Kunyavskiy (PavelKunyavskiy) and Dmitriy Ivanov (DmitriyIvanov) for testing of problemset, coordinator of Codeforces rounds Gerald Agapov (Gerald) for useful hints and Maria Belova (delinur) for translation of statements into English.

Good luck and high rating to all!

UPD1. The score distribution in this round will be dynamic (see here). In our opinion problems are sorted according to their difficulty.

UPD2. Analysis of problems is publisched.

UPD3. Rating is updated. Congrutalations to the winners who solved 4 problems:

Williamacm

Windseeker

Tifuera

seen

• +134

 » 6 years ago, # |   0 Hope that the tactics proven to work,the one from the last contest, will be applied here as well :)
 » 6 years ago, # |   +6 I hope, the contest will be as good as round 192, I hope there is clear explanation and good picture like in the past :)thanks :)
 » 6 years ago, # |   -21 First , Thanks For Round Preparation. Second , Hope from you not to follow the rule of "The lower rate problem setter The higher problems difficulty" :).
•  » » 6 years ago, # ^ |   +14 Just to remember my previous comment ,for me the problems was very hard to understand
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +21 I guess the rule really applied for this contest. The problem statements were too much painful to understand. :/
•  » » » » 6 years ago, # ^ |   +2 A was badly written
 » 6 years ago, # |   -30
 » 6 years ago, # |   +5 This is not about asking up-votes , because sincerely I could not care less about that, but I would like to ask the dear down voters, what is the logic of negatively rating my comment, and the one below positive ( nothing personal with the windoro, just an example ), when they almost say the same thing ? PS:Now you have reason to down-vote.
•  » » 6 years ago, # ^ |   -16
•  » » 6 years ago, # ^ |   -8 Even I understand you. Don't try to search the logic — it's Codeforces, upvotes and downvotes appears randomely.
•  » » » 6 years ago, # ^ |   0 For instance, like now.
•  » » » » 6 years ago, # ^ |   +67 Sometimes I am surprised to find that some comments that have good/helpful content being downvoted... so I just give them an upvote to balance it out >:)
 » 6 years ago, # |   -13 I was able to solve one problem from last contest (Eventually solved 3). Hoping to double that in this one. Good luck everyone!
 » 6 years ago, # | ← Rev. 3 →   -8 Wish everyone & myself a good rating~
 » 6 years ago, # |   -10 I think there will be short and not mathematical problems
 » 6 years ago, # |   +36 So many contest on codeforces. Feeling really fantastic! (Y)
 » 6 years ago, # |   +1 What is the dynamic score distribution ?
•  » » 6 years ago, # ^ |   +1 Task score depends on number of people solving the task. More in detail: link
 » 6 years ago, # |   +6 good luck to all...
 » 6 years ago, # |   +7 Slow testing again...
 » 6 years ago, # |   +23 the problems don't look like div2 to me
 » 6 years ago, # | ← Rev. 2 →   +12 18 mins have passed and i am still waiting for my judgement. Its not easy moving on to the next problem knowing your queued solution might be wrong.
 » 6 years ago, # |   +59 is the problems statements (in English version of codeforces) written in English? I can't understand the problems at all!
•  » » 6 years ago, # ^ |   +25 I give up the contest , one hour of contest passed and I still can't understand problems A C D E
•  » » » 6 years ago, # ^ |   +3 I think so
•  » » » 6 years ago, # ^ |   +3 Same here :(
•  » » 6 years ago, # ^ |   +1 I guess meaning of A . Luckily,I get AC. But I spent an hour and a half on a guess！！！
 » 6 years ago, # |   +8 If the test is so slow, I think this contest should be unrated.
•  » » 6 years ago, # ^ |   -7 I hope it
•  » » 6 years ago, # ^ |   0 cplayer right because contest will be very difficulty and testing is slow. So I didn't attend.
 » 6 years ago, # |   0 Maybe adding even more time it is a possible solution.
 » 6 years ago, # |   +3 Could someone tell me why my submit is in queue while other submits behind me is tested? THX~
 » 6 years ago, # |   -9 First Codeforces was temporary unavailable, after that I submitted my solution, but it takes more than 20 minutes in queue and...
 » 6 years ago, # |   +6 My first submission is 14 min after contest but it still in queue. In current standing I see Egor accepted C 30 min after contest. The system test work down, i think i should sleep and ignore this contest
 » 6 years ago, # |   +2
 » 6 years ago, # |   +3 Oh common what's happening. Why did some people get answer for their submissions on B 30-40 minutes into contest and I didn't have an answer for 30 minutes after I submitted 15 minutes into the contest. What is more I got a wrong answer and instead of searching for a mistake 20-30 minutes in contest I have to search for an error 50 minutes after beginning. This is way to big loss of points ....
 » 6 years ago, # |   +6 The language of each problem statement is very accurate but yet very advanced. While I appreciate the comprehensive context , I still think it's a disadvantage for those who are less skilled in English.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +18 Yeah, "A student's life is fraught with complications. Some Berland University students know this only too well. Having studied for two years, they contracted strong antipathy towards the chairperson of some department. Indeed, the person in question wasn't the kindest of ladies to begin with: prone to reforming groups, banning automatic passes and other mean deeds. At last the students decided that she just can't get away with all this anymore..." It's just too hard to understand !!!
•  » » » 6 years ago, # ^ |   0 It took 10mins to understand each questions
 » 6 years ago, # |   +3 the level of these problems is very high compared to average Div-2 problems....wonder why??
•  » » 6 years ago, # ^ |   0 This has been the case with recent div2 only contests.Also, including all kind of tests in pretest has also become a routine. Most contests don't have many hacks.
•  » » » 6 years ago, # ^ |   -8 +1 on the hacks comment!!
 » 6 years ago, # |   +13 Apparently it is not guaranteed that being an excellent coder leads you to develop a reliable and fault-tolerant web application. Right, CodeForces?
 » 6 years ago, # |   0 sk11
 » 6 years ago, # |   +22 As SmartCoder said: "First , Thanks For Round Preparation. Second , Hope from you not to follow the rule of "The lower rate problem setter The higher problems difficulty" :)." 2 days ago, and has a lot of negative feedbacks! But he was right!
•  » » 6 years ago, # ^ |   +16 No one believes me :)
 » 6 years ago, # |   +1 for B problem, is it available to solve it other than use segment tree ?
•  » » 6 years ago, # ^ | ← Rev. 3 →   +3 You don't need a segment tree, there are no updates at all, so you can precompute everything you need. In my solution i compute F[i], which is what the answer would be for just one segment, using only the numbers from 1 to i. And then let's say that the begginning of the second interval is at Z. Then the current answer is Sum(Z,Z+K-1)+F[Z-1], you can simply check all possible begginings of B (from K+1 to N) and pick the one that has the largest answer. You can calculate Sum(a,b) constantly after linear precompute :) Hope i helped
•  » » » 6 years ago, # ^ |   0 thx for the answer, i will see your code and take my time :)
 » 6 years ago, # |   +1 I am not expecting the system testing to start soon. Rather I'd go to sleep.
•  » » 6 years ago, # ^ |   0 It's started.
 » 6 years ago, # | ← Rev. 2 →   +3 Could someone give me hints about problem D? My idea is the following : We take a sile V, suppose there is direct passage to P siles from V. If P>=K, then we can pick subsets from those K vertices and the sile V will be their adjacent sile, since its mentioned that there is only one adjacent sile to a subset of K vertices, and obviously V is one. Every sile from those will be chosen in exactly C(K-1,P-1) subsets, and therefor an edge connecting V and some sile Z, will be used exactly C(K-1,P-1). Knowing that we can sum all the edges outgoing from one sile and then multiply it by C(K-1,P-1) , and doing that for every sile we get the total sum, now we have to divide it by the total amount of subsets of K vertices we can pick, which is C(K,N). However since P is different for each sile, i couldn't find a way to avoid using large numbers and therefor couldn't get my solution to work. Is that the proper idea or am i too far :P?[C(A,B) = Binomial Coefficient]
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 I think it's correct, but use C(K - 1, P - 1) instead. I submitted the same thing with binoms in long double, hope it will be enough.UPD: it is enough.
•  » » » 6 years ago, # ^ |   0 Yea, sorry, it's C(K-1,P-1), edited. However why does it work? I am surprised it works since binomial coefficients are usually really large... It will be interesting to see a proof why it won't overflow
•  » » » » 6 years ago, # ^ |   0 I think if both the nominator and denominator are very large, precision errors appear only after the decimal point separator in the resulting number. But if they are small, then precision errors should be negligible in nominator and denominator.
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   +3 The reason why the binomial coefficients do not grow large is that for this special graph, K can only be 1, 2, or N-1. K can be 1 when N is even. (matching) K can be 2 when N is odd. (many triangles share a same point) K can be N-1 no matter N is even or odd. (clique) This property makes the binomial coefficients very limited in range.
•  » » » » » » 6 years ago, # ^ |   0 Thanks, that's a very nice observation! I feel a little bit stupid now — my solution does not use any properties of the graph — it is just a brutal bignum computation but somehow it actually works, and it would (in a way) work on any graph.
•  » » » » » » 6 years ago, # ^ |   +3 Why?? How do you prove it?
•  » » » » » » » 6 years ago, # ^ |   0 I mainly got it from observation and then verified it with the test data. Indeed the K=2 construction is already quite tight in constraints. K=1 and N-1 are trivial. However I tried but could not come up with a proof for the other cases. Hope that there would be an editorial for that.
•  » » » 6 years ago, # ^ |   0 It's really depressing when I know it's enough.... I got the formula, did some preprocessing to check overflowing, and after knew it will overflow (I checked C(2000,1500)), I closed the problem. Poor me, LOL.
 » 6 years ago, # |   +12 oh . how much i miss round 192 :D
 » 6 years ago, # | ← Rev. 3 →   +3 00:16:47 Skipped [pretests] → 4148842 01:00:50 Accepted [final tests] → 4152076 Same code, 46 minutes in queue :(
 » 6 years ago, # |   0 this contest din't go really well for me looking for the next contest
 » 6 years ago, # |   +2 Yeah, after this round! I never rate a round tutorial before I participate in the round. To muslims: I was fast, and azaan was in the contest time, I just participate in this round for 40 minutes. Excuse me, but it was the worst contest I ever participate in Codeforces.
•  » » 6 years ago, # ^ |   +9 in my country, the contest time is about 4-5 hours after azaan :)just dont participate if you have other important things to do, and if you still insisted, you shouldn't say the worst timeremember, there is different place, different time, and different religion for others
•  » » » 6 years ago, # ^ |   0 I'm not talking about the time! I'm talking about the problems!
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 oh, sry, i misunderstood that.
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 he said:" I was fast, and azaan was in the contest time, I just participate in this round for 40 minutes"You did not misunderstood.
 » 6 years ago, # |   +9 How lucky am I! I passed E at the last second!
 » 6 years ago, # |   +6 long in-queue is still the most annoying problem. this problem affects the ranks directly.
 » 6 years ago, # |   +9 Forgot to mark one flag in solution to problem E, and hence I was outputting the correct string, but not lexicographically smallest, but just the one with the maximal number of '1's. Failed on test #169 (last test case). It seems that my luck was a little bit less strong than test cases this time.
 » 6 years ago, # | ← Rev. 2 →   +7 To be honest,I don't think the problems description is pellucid...
 » 6 years ago, # |   +4 How to do C?
 » 6 years ago, # | ← Rev. 3 →   0 Can someone clarify me this sentence in problem D :"The insurgents studied the polygon plan and noticed its unusual structure. As it turned out, for any k-element set of silos S there is exactly one silo that is directly connected by a passage with each silo from S (we'll call this silo adjacent with S)."How is it possible to this test case be valid :5 2-1 -1 14 319 -1 1-1 60Silos set S = {1, 2} (number 1 and 2 silo) have 0 adjacent silo, right? Silo 1 is connected with 4 and 5, and silo 2 is connected with 3...
 » 6 years ago, # |   0 Editorial was out 30 minutes ago, but no one announced it!
 » 6 years ago, # |   +15 It's just my opinion, but I think CodeForces should balance the difficulty between Div 1 and 2 more. With solving 3 problems, you can place on top 20 in Div 2, and will be promoted to Div 1. In Div 1, with solving 1 problem, you can't stay longer and will be kicked to Div 2. I got this many times, do well in Div 2 but not good enough in Div 1.My example for "easier" difficulty is TopCoder. In Div 1, you will be sent to Div 2 only if you can't solve any problem. Maybe the difference comes because the problem's count is differ (3 on TopCoder and 5 on CodeForces). Or maybe the competition here is intended to be more strict?Just my opinion, it's not a bad thing actually.
•  » » 6 years ago, # ^ |   +12
 » 6 years ago, # |   +19 I can understand that English isn't necessarily the first language of everyone (it isn't mine either). But the problem statements today were simply too hard to understand. The description of Problem A seemed unclear (e.g "if j ≥ 4 and the players who had turns number j - 1, j - 2, j - 3, made during their turns the same moves as player bi on the current turn, then he had drunk a glass of juice" — who is the 'he' referring to? The current player, or the players in the last three turns? Why is the whole description of the game in past tense?). The first paragraph of Problem C looks like it is fresh out of Google Translate (not that it mattered for solving the problem, but still).I hate to be a grammar Nazi, but this really makes a difference in programming contests.
•  » » 6 years ago, # ^ | ← Rev. 4 →   +5 I agree. This problem took me a minimum of 10 minutes to understand, I honestly lost track. I initially thought it was 30 but then checked my submission time. For my first contest on here, this was really disconcerting.Things that threw me: Trying to figure out who "he" was Understanding that Vasya was always player 0 Figuring out the what difference between an elbow and a nod actually was Having to assume "optimally well" meant drinking the most juice (most drinking games in my country, the aim is to NOT have to drink...) Interpreting the question to understand Vasya may or may not have played optimally well, and you were to disregard his moves from the record. Mind you, English IS my native tongue, which might actually have proved to be a disadvantage here.
•  » » » 6 years ago, # ^ |   -8 you can learn russian as a workaround ;)
•  » » » » 6 years ago, # ^ |   +6 If only there were more hours in a day.
•  » » 6 years ago, # ^ |   +22 Actually the Russian statements were hard to understand too.
 » 6 years ago, # |   +9 Horrible problem statement !!!
 » 6 years ago, # | ← Rev. 2 →   0 even though i submitted A a bit earlier than everybody else and hence wasn't in queue for very long time, i was still greatly affected by it....when i submitted A i was 7th in standings and i remained in the top 20 till about 30 minutes into contest, so i thought B must be very difficult as very few people had done it till then, and i tried to hack instead of attempt B....after 50 minutes into contest i had moved to 400th in standings, i was like WTF!!!Codeforces, please do something to fix the lengthy queue problem! ur coders, for god's sake!!
•  » » 6 years ago, # ^ |   0 Exactly... It really happens... Specially for the coders like us(Specialist, pupil & newbie). We have to keep an eye in the standing too. But when this situation occurs, it is really difficult to realize the difficulty of the problems. :(Again, if I submit a problem but if it stays in queue for the long times, then it's hard to give concentration to another problem. And if I get "wrong answer" verdict after a long queue, it effects standing too. If I get this verdict few minutes ago, I can re-think my solution few minutes ago. Thus I could submit the problem again few minutes ago saving time penalty. I think(like many others commented in this blog), contest should be unrated when "long time queue problem" happens. It will be fair, I think.
•  » » » 6 years ago, # ^ |   0 Hmm, I totally agree with you except the last paragraph of your comment. There are usually some technical problems in CF contests, like long queue or server down, but the circumstance is the same for all coders. So I think there is no reason to make the contest unrated because of "unfairness".
•  » » » » 6 years ago, # ^ | ← Rev. 3 →   +1 Ok... Lets see two cases :Case 1: Usual contest. No problem of long time queue. Mr. A submitted a solution and the solution is ok. Mr. B submitted a solution but "wrong answer"(You know, it can be happened even for a Grandmaster too). He resubmitted it within one or two minutes. And this time it is ok.Case 2: The contest like last one. Mr. A & Mr. B both submitted a solution and there is no verdict. After 10 or 15 minutes the verdict is given. Solution for Mr. A is ok and solution for Mr. B is wrong. Now think, In last contest, someone got verdict even if he/she submit a solution later while the contestant had submitted a solution earlier didn't get any verdict. So there are many chances for some other contestants to enter between Mr. A & Mr. B in the standing.I've told "unfair" thinking this. And in my view this two cases can never be same. In case 2, if there is no "long queue" problem, Mr. B could get a chance to resubmit his solution within one or two minutes. But for "long queue" problem, he didn't get this chance. Moreover, some other contestants also entered between Mr. A & Mr. B.
 » 6 years ago, # |   0 The descriptions are so bad!!!
 » 6 years ago, # | ← Rev. 2 →   -9 The problems are translated well , but all problems are too long ! Shortering some problems will be better .
 » 6 years ago, # |   0 My idea in problem D is: Take an arbitary silo u and check the total danger of all possible S which are adjacent to u.Let deg[u] be the number of silos which has a passage to u. Consider an arbitary passage (u,v) which has danger c. Assume that (u,v) appears in S, then the total danger increases by c. So we must find out how many times (u,v) appears, which is equals to how many S which contains (u,v). We must choose (k-1) other silos from the set of the other (deg[u]-1) silos, so it would be C(deg[u]-1,k-1).Every passage from u appears exactly C(deg[u]-1,k-1) times, so let s[u] be the sum of the danger of all passages from u. The total danger of all possible S adjacent to u is: s[u]*C(deg[u]-1,k-1).Then, the answer of the problem is: (s[1]*C(deg[1]-1,k-1)+s[2]*C(deg[2]-1,k-1])+...) / C(n,k) (C(n,k) is the number of all S possible)The problem here is: how to handle the C(n,k), which should be huge?I use Extended in Pascal and /C(n,k) by every s[u]*C(deg[u]-1,k-1). It's easy to see that C(deg[u]-1,k-1)/C(n,k)=k/(n-k+1)*(deg[u]-1-0)/(n-0)*(deg[u]-1-1)/(n-1)*...It's not very precise and I got WA on test 21:Output1999999999Answer2000000000Anybody has an idea how to handle this? Coding big number would be too complicated.
•  » » 6 years ago, # ^ |   +1 Just use Java: 4158861
 » 6 years ago, # |   0 Was a tough contest indeed as the problem statements were complicated to understand.Hopefully will get better problem statements from the next contest..
 » 6 years ago, # |   0 I'm trying this problem:http://codeforces.com/contest/332/problem/BCF shows WA for the 1st test case.Test #1 5 2 3 6 1 1 6Correct output 1 4And my code gives correct output in my PC and in Ideone too.http://ideone.com/cTqaKyBut it gives 2 4in CF!!!http://codeforces.com/contest/332/submission/4171816Can anyone please tell me where is the problem? :O
 » 6 years ago, # |   0 I don't if I must name this contest "weak" or "too difficult", but the problem explanation was really weak!
 » 6 years ago, # |   0 I agree the questions were not easy to understand I mean the questions were not well described .... But anyway thanks Designing questions and running a contest is not an easy task So you did it .... Thanks