Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

By RAD, 7 years ago, ,

Hi everyone!

Codeforces Round #170 begins soon, and I'll be the problem setter. I hope many people will be happy to solve all the problems.

UPD: The scoring is dynamic. The problems are sorted by increasing of estimated difficulty.

And the standard part: thanks to Gerald for his help with the problems, Seyaua and sdya for testing the contest, Delinur for translations, MikeMirzayanov for building the Codeforces platform.

Good luck!

UPD: Tutorial

• +173

 » 7 years ago, # |   -32 i wish you good luck and have fun ;) =d>
 » 7 years ago, # |   -38 It's also 11.30 here. I'm doing my internship, hope I will not get fired for sleeping at work -.-
•  » » 7 years ago, # ^ |   +2 http://codeforces.com/blog/entry/6777#comment-123735 are you the same guy ?
•  » » » 7 years ago, # ^ |   0 it may be one of the way to get positive votes.
•  » » 7 years ago, # ^ |   +2 Wow, so I'm not the only one? :')Let's do our best, then.
 » 7 years ago, # |   +21 I hope it will be a good contest! I just have a question, why do seyaua and sdya have different name, but their image are same??? (i know their family name are same! maybe they are brother!)
•  » » 7 years ago, # ^ |   +27 They are twins
•  » » » 7 years ago, # ^ |   +10 really fantastic for me!! thanks a lot!!
 » 7 years ago, # |   -49 yes we are twins...
•  » » 7 years ago, # ^ |   -12 Y U NO stop acting like a potato?
•  » » » 7 years ago, # ^ |   -6 Why did you add potato?
•  » » » » 7 years ago, # ^ |   -11
 » 7 years ago, # |   -32 How can I get positive votes in blogs? Please, help me!!!
•  » » 7 years ago, # ^ | ← Rev. 2 →   -11 Just write good things, bro!!! And things that have meanings!!!
•  » » 7 years ago, # ^ |   0 Always if you say 'LIKE ME' people will Dislike, because everyone want to harm))
 » 7 years ago, # |   -18 А какие задачи нравится вам?
 » 7 years ago, # |   +1 Score distribution is still unavailable :(
•  » » 7 years ago, # ^ |   -9 I hope that the scores will be the highest.
 » 7 years ago, # |   0 4 problems with Score 3k :v Nice contest!
 » 7 years ago, # |   +3 what is wrong with testcase 4 of 2C ???
•  » » 7 years ago, # ^ |   +16 Perhaps a scenario in which nobody speaks any language?
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 5 2 0 0 0 0 0 The result is 5 :)
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 [sorry ! I just wrote it when no answer was available].all the vertices have degree 0 so everyone should learn a language !!
•  » » 7 years ago, # ^ |   0 maybe like this one 2 1 0 0 this should be 2 not one
•  » » 7 years ago, # ^ |   0 All of the employees know nothing.
 » 7 years ago, # |   +3 last 15mins I have problems with connection to codeforces.is this only with me or with all?
•  » » 7 years ago, # ^ |   +6 had no problems
 » 7 years ago, # |   +1 Very FAST system testing @ Div 2!
 » 7 years ago, # |   -47 I've challenged this solution twice during contest time but it returned correct answerSubmission: 3209935But it failed on similar test case! admins please clarify?Here is one of my test case: 100 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100
•  » » 7 years ago, # ^ |   +35 HEY you scrolled your browser only to give him negative votes! :P
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 HAHA it's more interesting that ppl didn't get lazy votedowning XDXD
 » 7 years ago, # |   0 now I read problem B can someone explayn why length of answer<=2???
•  » » 7 years ago, # ^ |   +4 Because not all combinations of 1 or 2 letters can appear at the same time.
•  » » 7 years ago, # ^ |   0 Actually It's <=3
•  » » » 7 years ago, # ^ |   0 No, it's not.
•  » » » » 7 years ago, # ^ |   0 Ah, I thought the length of string is <50! What an epic fail!
•  » » 7 years ago, # ^ | ← Rev. 2 →   +1 in 30 names with length 20 maximum number of consecutive pair elements is 30*19 and number of strings with length 2 is 26^2 30*19<26^2 so length 2 Is enough :)
 » 7 years ago, # |   +2 not good contest! :|
•  » » 7 years ago, # ^ |   +58 Hard problems but very interesting!
•  » » » 7 years ago, # ^ |   -11 but in this contest the speed of coding was too important to be helpful for coders!
•  » » » » 7 years ago, # ^ |   +9 for me, I enjoyed solving div1 B.anyway I think speed of coding is important part of a good programmer.
 » 7 years ago, # |   0 When the "Razbor" will be onnounced?!
 » 7 years ago, # |   +21 The contest was very hard but the system testing was too fast!
•  » » 7 years ago, # ^ |   -8 And did you understand anything? If did, then could you make it clear for me?
 » 7 years ago, # |   +3 Lost 2nd position because of 10 (instead of 1000000). :( It is REALLY disappointing. I was too nervous I think. T_T
 » 7 years ago, # | ← Rev. 2 →   +54 That was really fast system testing!Short editorial for problems I know how to solve (sorry for possible errors):DIV1-A. Connect persons with common language, then output is max(0, #connected components — 1) + #persons without any language knowledgeDIV1-B. [extracted from rng_58 source code] For case m = 3, n >= 5 there's no solution. m = 3, n = 3/4 one can construct big triangle and a point near one of the points of the triangle. For other cases (m > 3) one can construct (as rng_58 did I think) "function X^2" for one convex polygon (points (i, i * i + LARGE_DELTA)), and "function -X^2" for the rest of the points (poiints (i, -i * i — LARGE_DELTA).DIV1-C. It can be considered as nim game. For every row/column with coordinates [1 .. maxCoordinate — 1] count the number of "free" unit segments ("free" = not covered by any move played). Let that number be countRow_r for row r, or countCol_c for column c. Then nim sum would be NIM_SUM = (XOR_SUM countRow_r) XOR (XOR_SUM countCol_c). So by the theory of nim game first player wins if NIM_SUM != 0, otherwise second wins. Then we have to find a move which makes NIM_SUM equal to zero, and by the theory of nim games that move exists.DIV1-E. Construct graph with two nodes u_in, u_out per one node u originally given in the input. Attach the "source" to u_in with capacity 2 and cost 0, attach u_out to the "target" with capacity 1 and cost 0. Then attach u_in to v_out with capacity 1 and cost DISTANCE(u, v) when v can be a child of u (ie. v.y < u.y). Then run min-cost-max-flow and if the flow is n — 1 you can construct the graph and output it minimum cost, otherwise no solution exists.
•  » » 7 years ago, # ^ |   +8 "number of free segments >= NIM_SUM. It can be proved that such row/column exists."Not necessarily. You only have to find one such that ("Y" xor NIM_SUM) <= "Y". The other condition would work for some cases but it's not guaranteed to always hold, unlike this one.http://en.wikipedia.org/wiki/Nim
•  » » » 7 years ago, # ^ |   +3 Thanks, that was my error. I corrected it.
•  » » 7 years ago, # ^ | ← Rev. 7 →   +27 supplement .. .DIV1-D is a knapsack problem, actually is a dependency 0-1 knapsack problem, But the dependence is very weak. So we prefer to use a grouping 0-1 knapsack problem model to solve this. The expect score is trivial, so let us focus on the penalty. You can found the penalty system in the problem is a little bit different against the reality, that is once we start solving on those large point, we'll never back to solve a small point. This declare is obviosly true.Then, for two large point u, v, let us denoted by (t, f) for time and fail probability. tu fv (1-fu) + (tu+tv) (1-fv) tv fu (1-fv) + (tu+tv) (1-fu) Simplificate on the formula, Then we could found a large point u is in front of v, iff tu fu (1-fv) < tv fv (1-fu) . Once the principal contradiction is grasped, all problems will be readily solved. Sort the problem by the above function. Running a 0-1 knapsack problem. Choose the answer. const int N = 1009, M = 2009, P = 1000000; pair dp[M]; int n, t; struct rec{ LL t1, t2, s1, s2, pf; LL ps()const{return P - pf;} bool operator < (const rec& r) const{ return t2*pf*r.ps() < r.t2*r.pf*ps(); } void input(){ RD(s1, s2, t1, t2), pf = RF() * P + 0.5, s1 *= P; } void update(){ DWN(i, t, 0){ if (i + t1 <= t) checkMax(dp[i+t1], MP(dp[i].fi+s1, dp[i].se)); if (i + t1 + t2 <= t) checkMax(dp[i+t1+t2], MP(dp[i].fi+s1+s2*ps(), (dp[i].se+t2)*pf/P)); } } } A[N]; int main(){ #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif RD(n, t); REP(i, n) A[i].input(); sort(A, A+n); REP(i, n) A[i].update(); LL a = 0; DB b = 0; REP_1(i, t){ if (dp[i].fi > a || dp[i].fi == a && i-dp[i].se < b){ a = dp[i].fi, b = i-dp[i].se; } } printf("%.9lf %.9lf\n", (DB) a/P, b); } As we want to minimize the penalty, it'll be a wise idea that we use the second dimension of the dp array, record the maximum expected save of the penalty.
 » 7 years ago, # | ← Rev. 7 →   -56 My solution is correct!!!!!! :@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ this failed on system test: http://codeforces.com/contest/278/submission/3214079 and then just added this lines for debug and when i submitted Accepted :/ http://codeforces.com/contest/278/submission/3219530difference is only : void add(string &s,int toindex,int strindex) { if(s.length() <= strindex) return; if(root[toindex].c[s[strindex]] == 0) { root[toindex].c[s[strindex]] = ++cindex; add(s,cindex,++strindex); }else { add(s,root[toindex].c[s[strindex]],++strindex); } } void add(string &s,int toindex,int strindex) { if(s.length() <= strindex) return; int ind = root[toindex].c[s[strindex]]; if(ind == 0) { root[toindex].c[s[strindex]] = ++cindex; add(s,cindex,++strindex); }else { add(s,ind,++strindex); } } why it has different answer?SeyauaGerald
•  » » 7 years ago, # ^ |   +17 You have undefiined behavior in line add(s,root[toindex].c[s[strindex]],++strindex); arguments can be calculated in any order. For example it can be calc strindex for last argument add 1 to strindex calc root[toindex].c[s[strindex]] with new strindex. Probably this one happened. It can depend on compiler and OS.
•  » » » 7 years ago, # ^ |   +1 Also the same compiler on the same OS can reorder the parameters if it finds that to its advantage.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   -34 typedef struct node{ int c[255]; node() { for(int i = 0; i < 255; i++) c[i] = 0; } } node;nooo i initialize all the nodes, none of them mustn't be undefined..... strindex is always less then s.size(); every s[i] is less then 255, c[255]; and it means that if(root[toindex].c[s[strindex]] == 0) is false and int ind = root[toindex].c[s[strindex]];if(ind == 0) that's true :/
•  » » » » 7 years ago, # ^ |   +13 add(s,root[toindex].c[s[strindex]],++strindex); may be done as ++strindex,add(s,root[toindex].c[s[strindex]],strindex); and may be done as add(s,root[toindex].c[s[strindex]],strindex),++strindex,;One of them is correct, and one not.
•  » » » » » 7 years ago, # ^ |   -85 fucking compilers :@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 » 7 years ago, # |   +6 The problem Standard was A , B , C , E , E :D
 » 7 years ago, # |   +35
 » 7 years ago, # |   +23 In div-1 1st prob:pretest 4 could have been avoided to increase successful hacking attempts.
•  » » 7 years ago, # ^ |   0 Agree with you!!! the more hacks contest have, the more enjoyable it is!
 » 7 years ago, # |   -29 Контест будет рейтинговым ?
•  » » 7 years ago, # ^ |   0 А почему бы ему не быть рейтинговым?
 » 7 years ago, # |   +36 When will the rating update ? If there any problem, please update this blog.
 » 7 years ago, # |   +1 In problem Games, I get WA on test 17. In the test one of the cuts is "2 4 2 3", while the jury's answer is 2 0 2 5. How could it be right?
•  » » 7 years ago, # ^ |   0 What's the problem?
•  » » » 7 years ago, # ^ |   0 If the part 2 3 2 4 was already cut, how can we cut 2 0 2 5? Won't we repeat the edge 2 3 2 4?
•  » » » » 7 years ago, # ^ |   +3 As long as you touch some uncut parts, it's fine. (I asked this question during contest time)
•  » » 7 years ago, # ^ |   0 Please note that the paper doesn't move during the cuts and you can cut along previus cuts but you have to cut at least one more unit line.
•  » » » 7 years ago, # ^ |   0 Thanks to both of you :)
•  » » 7 years ago, # ^ |   +6 I did the same mistake :( I believe this problem should have better definition of cutting even with a figure showing different situations.
 » 7 years ago, # |   0 Could someone comment on possible strategies for div1-b checker ?
•  » » 7 years ago, # ^ |   -9 Fit m vertices evenly on a circle with radius R1. Fit the other n — m ones evenly on a circle with radius R2 < R1. This can always be done, except when m = 3 and n > 4, I don't know the reason for this yet though.
•  » » 7 years ago, # ^ | ← Rev. 2 →   +10 You can also create a distribution like this:http://s16.postimage.org/83zarzh2d/design.pngThis will guarantee that you cannot form a polygon whith more than 4 vertices selected from both the first and the second set of points. So, if you have M>3 or if M=3 and N<=4 then the given strategy will provide a good solution.
•  » » » 7 years ago, # ^ |   0 Thanks for the solution, but I was asking about how the checker would have evaluated the answers. I would like to know what logic did checker apply on the output points so as to verify that maximum convexity is m. (a naive approach of selecting m+1 points and checking will be too time consuming and I am not able to think of a better checker)
•  » » » » 7 years ago, # ^ |   0 My guess about the checker is to run Convex Hull algorithm(O(nlgn)) on your points and see if the output is m or not.
•  » » » » 7 years ago, # ^ |   +8 I am sorry I misunderstood your question. My guess for how the checker works for this problem is that it sorts the output points clockwise or anti-clockwise, and then it used a dynamic programming algorithm to find the maximum convexity of the points. If the maximum convexity is equal to M, and there are no 3 points situated on a straight line (which could be verified in N^3 complexity, given that N is no bigger than 200) then the solution is considered correct.As for the Convex Hull algorithm, I do not believe this algorithm would have found the maximum convexity of a set of points (consider a hexagon inside a square, the convex hull algorithm would say that the maximum convexity is 4, which is not correct) .
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 You also need to make sure you don't have 3 points at the same line, like here: http://s24.postimage.org/oynvny78l/design2.png I wrote same solution but made this bug during the contest. I took a random distance out of my head between those two simmetric figures, but, as usual, if it is possible to make a bug I will make it:)
•  » » » » 7 years ago, # ^ | ← Rev. 4 →   -8 My guess about the checker is to run Convex Hull algorithm(O(nlgn)) on your points and see if the output is m or not. [Edit: sorry I meant to reply to pareshverma91]
•  » » 7 years ago, # ^ |   +23 First of all, check that no three points lie on the same straight line.Then iterate over all points, and assume that the i-th point is the leftmost point of largest convex polygon. Sort all the points to the right of i by the angle relative to the i-th point.Calculate the following DP: z[t][j] = the maximal size of polygon, where the first point is i, the last point is j, and the next to last is t ( j is always greater than t by the relative angle). We can connect points i and j to finish the polygon of z[t][j] points. Or we can find the next point k to continue building the polygon. k must be greater than j by relative angle, and triple (t, j, k) must have positive orientation. This solution is O(n 4) in total, but actually it's C(n, 4). And you can improve the DP to make it O(n 3). Code: http://pastebin.com/Ubf25Qq8
 » 7 years ago, # |   +1 Fast System test is awesome, hopping rating update be as fast as it .... every contest.
 » 7 years ago, # |   +10 In problem div1-C, the sentence "that is the knife has to touch the part of the paper that is not cut before." is ambiguous. One could understand, as in my case, that the knife can only touch the part of the paper that is not cut before. My submitted solution in contest time was written according to this interpretation. Please, try to be clearer the next time.
•  » » 7 years ago, # ^ | ← Rev. 2 →   +9 I find it clear. In your interpretation, it'd be "cannot touch the part that was cut before" — exactly to remove the possibility of this ambiguity. But if you're not sure, you can still ask an official question — they're answered pretty fast.
•  » » » 7 years ago, # ^ |   +5 I also asked the same question during the contest. Maybe it should have been better to make a public clarification since lots of people asked about it.
•  » » 7 years ago, # ^ |   0 The same here ; /. In fact it's our fault, but that's not a good thing when many contestans got the description wrong :d.
•  » » 7 years ago, # ^ |   +8 I made the same mistake too :(I think for this kind of ambiguous, one of the best solution is to have it in samples to resolve it.Samples are not used for testing, but are used for better understand the statement and resolve the ambiguous.The current samples are already very good that resolved the ambiguous of "it is not guaranteed that the cuts were obtained during any correct game".Hope it can be better next time.
 » 7 years ago, # | ← Rev. 2 →   0 Why my solution in problem C div2 getting "Ошибка исполнения на тесте 10"?I think everything is OK...but i can't understand why it is giving TLE...PLS help...Here is my code:3214342
•  » » 7 years ago, # ^ | ← Rev. 2 →   +1 You don't get TLE (Time Limit Exceeded), but Runtime Error. Download the test, run in your environment, debug.Edit: Aha, you can't download the test. But repeat the last full line 30 times and you should get runtime error locally. I did with your prog.
•  » » » 7 years ago, # ^ |   0 thx for help...but my prog giving true result in my computer...but in codeforces it's giving runtime error...but i don't know why?...
•  » » » » 7 years ago, # ^ |   0 This is the problematic line:int n,i,j,k,l,f,d,c,ans,cnt,s,t[MN],m;Don't declare all the letters in advance. You used global variable L, where you should have a local L. Probably your compiler optimized the code incorrectly, not expecting that the value of L could change inside the loop. Actually it is changed inside recurent calls to dfs. Incorrect optimization surprisingly gave expected behavior in your environment. I bet you don't use gcc, do you? What's your compiler?
•  » » » » » 7 years ago, # ^ |   0 thx a lot for helping...i accepted it...problem was "l" i think...i took it from global and it got accepted...
 » 7 years ago, # |   0 Will the editorial be public?
 » 7 years ago, # |   -8 in problem div 1 C "You are given an n × m piece of paper" "(0 ≤ xbi, xei ≤ n, 0 ≤ ybi, yei ≤ m)" how can be both correct? if 0<=xbi<=n and 0<=ybi<=m than we are given n+1 x m+1 piece of paper no?
 » 7 years ago, # |   +13 Also made a screencast: link
 » 7 years ago, # |   +1 Hi,Is it please possible to have as many rounds in the weekends as possible? For ex, the next div2 round is on monday and i don't see why it was not scheduled on sunday. For people from western europe the 7:30pm from russia is really bad during work days.Thanks a lot!