### KAN's blog

By KAN, 4 years ago, translation,

Hello everybody!

The Technocup 2017 (a competition for high-school students hosted by Mail.Ru Group together with MIPT, Bauman MSTU and Codeforces) Finals is happening tomorrow in Moscow. For those who will not participate in the Finals, we prepared mirror contests for both divisions. The round will start at 13:05 UTC at Sunday, March 5th, 2017 and will last for two hours.

The round was prepared by Endagorion, WHITE2302, Alladdin, fcspartakm, Amethyst1, MikeMirzayanov, ifsmirnov and me.

You can view the current onsite results at link.

There will be six problems in each division.

Editorial is here.

• +275

 » 4 years ago, # |   +61 Why isn't this on the home page?
•  » » 4 years ago, # ^ |   0 Will there be an editorial for Div2 and Div1 problems ?
•  » » » 4 years ago, # ^ |   +5 What makes you think I would know this? xP
•  » » » » 4 years ago, # ^ |   +9 Sorry, I just hijacked the top comment xD
•  » » » » » 4 years ago, # ^ |   0
 » 4 years ago, # |   +45 I thought that I will die before I participate in a new round
•  » » 4 years ago, # ^ |   -25 hahaha!
 » 4 years ago, # |   +26 Error 403: this page is not available in your country... Syrian contestants will relate :( :( :(
 » 4 years ago, # |   +12 I have developed a habit of viewing if there is a new round every day...
•  » » 4 years ago, # ^ |   +39 *every hour
•  » » » 4 years ago, # ^ |   0 You can try using Coding Calendar. It will update and remind you whenever there is a new coding contest (not just for Codeforces)
 » 4 years ago, # |   0 Will the descriptions of the problems in English or in Russian? Thanks a lot.
•  » » 4 years ago, # ^ |   0 both in Russian and in English
•  » » » 4 years ago, # ^ |   +6 wish in chinese
•  » » » » 4 years ago, # ^ |   0 so am i.
•  » » » » » 4 years ago, # ^ |   0 so am I.
•  » » » » 4 years ago, # ^ |   0 Another close English and Russian version and do the rating? It would be interesting! ))
 » 4 years ago, # |   +9 Scoring distribution ?
 » 4 years ago, # |   +9 Will it be rated or unrated?
•  » » 4 years ago, # ^ |   +6 Yes, it will. In Russian it is stated clearly.
•  » » » 4 years ago, # ^ |   0 @Andrekk, Could you please give me the link of the russian statement?
•  » » » » 4 years ago, # ^ |   +5 I can't do it. You switch the language via button in the upper right corner of any web page, but URL isn't changed. Basically, in russian it says, ' А для тех, кто не будет участвовать в финале, мы подготовили рейтинговую трансляцию финала для обоих дивизионов' which was translated just like 'For those who will not participate in the Finals, we prepared mirror contests for both divisions'.
 » 4 years ago, # |   -62 I am so stupid that I can not be like tourist))). More likes,please. LOLKEKCHEBUREK
 » 4 years ago, # |   +73 Slept for 2 hours, went for an ACM training, then a CF round... feel awesome!
 » 4 years ago, # |   +2 What are the problem scores?
•  » » 4 years ago, # ^ |   0 It'll be announced after the contest begins. :D
 » 4 years ago, # |   +5 scores distribution?
 » 4 years ago, # | ← Rev. 2 →   +53 Rating prediction for this contest could be found for div1 & div2 Since today results table sortable, just click on column header to sort by it.Extensions: About CF-PredictorGood luck & high rating for everyone!
•  » » 4 years ago, # ^ |   +5 Amazing! Thank you.What is seed? My position in sorted list of competitors ordered by their rating?
•  » » » 4 years ago, # ^ |   +5 Seed is your expected ranking according to your current rating. In other words, if your final ranking equals your seed, then your rating change should be 0. If your final ranking is lower than your seed, then you will gain rating points.
•  » » » » 4 years ago, # ^ |   0 Thank you. How is that determined?
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   +3
•  » » » » » » 4 years ago, # ^ |   0 Thank you.
•  » » » 4 years ago, # ^ |   +3 You are welcome:) If talk simple, if your rank equals to your seed, your rating doesn't change. But actually it could change according to anti inflation policy.
 » 4 years ago, # | ← Rev. 4 →   +9 Very weak pretests in problem D. LOL :DOMG!! MY SOLUTION IS CORRECT!! HOW?! EVEN I DIDN'T READ STATEMENTS FULLY!
•  » » 4 years ago, # ^ | ← Rev. 6 →   +14 Your submission : http://codeforces.com/contest/782/submission/25256168, Should have Failed on : Weak systest 4 DII D DII C ABB A ABC A 
•  » » » 4 years ago, # ^ |   0 My answer is NO for this case.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +7 Yeah, it should be : YES DID DIC ABB ABC 
•  » » » » » 4 years ago, # ^ |   0 Is my solution correct? 25263983
 » 4 years ago, # | ← Rev. 5 →   -50 I am getting WA on pretest 5, for Div2 C. Can anyone help me? My submission: 25264506
•  » » 4 years ago, # ^ |   +3 Please remove your code, it is covering page, just keep submission link please.
•  » » » 4 years ago, # ^ |   0 Done.I thought that block of code means one can see code only if he clicks on the top of codes, but I was wrong. So I have removed my code.
•  » » » » 4 years ago, # ^ |   0 25270511 Just a small change in dfs checking if val(parent)==id is required after checking for the current node as well and AC! :D
•  » » » » » 4 years ago, # ^ |   0 Thank you pratik.pugalia I have now found my mistake.Thanks a lot for your comment !
 » 4 years ago, # |   0 Can you solve Div2B using binary search? I tried searching for the time or for the meeting point, but I'm getting WA6. Is the approach wrong or I just screwed up floating-point arithmetic?
•  » » 4 years ago, # ^ |   +1 I had the same problem. After 5 unsuccessful submissions, I put cout.precision(7); at the beginning of the code and it passed the pretests.
•  » » » 4 years ago, # ^ |   0 Damn, that did it, I got AC. I feel really stupid now, I'm not even sure why this line matters.Thanks.
•  » » » » 4 years ago, # ^ |   0 It's because by default cout precision is low. The problem requires precision upto 10^-6. So, suppose answer is 1.000777, cout without precision setting would round it to 1.001, resulting in WA.
•  » » 4 years ago, # ^ |   0 Don't we need ternary search?
•  » » 4 years ago, # ^ |   0 No. A unimodal function can't be solved with binary search. You need ternary search.
•  » » » 4 years ago, # ^ |   +4 You can binary search on time, it's monotonic.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +7 yeah, it's monotonic on time, unimodal on distance.
•  » » » » » 4 years ago, # ^ |   0 How to prove its unimodal on distance ?
•  » » » » 4 years ago, # ^ | ← Rev. 3 →   0 I used Ternary search and got AC. It should not be Binary search bcz then we may choose boundary values(min or max).Edit: it's possible follow this (binary search on time)
•  » » » » » 4 years ago, # ^ |   0 I used ternary search and got TLE.
•  » » » » » » 4 years ago, # ^ |   +6 Ternary search works perfectly fine. Got AC. Check for boundary conditions. Using iterative method works. Compute log2(MAX_NO_OF_ITERATIONS) and do the search that many times. Code rep(it,0,100) { lthird=low+(high-low)/3; rthird=high-(high-low)/3; tmp1=f(lthird),tmp2=f(rthird); if(tmp1=tmp2) low=lthird; else high=rthird; }  Function fldb f(ldb p) { ldb curr=0; rep(i,1,n+1) curr=max(curr,(((ldb)(abs(p-x[i])))/v[i])); return curr; } 
•  » » » » » » » 4 years ago, # ^ |   0 Please look into my submission.http://codeforces.com/contest/782/submission/25253601
•  » » » » » » » » 4 years ago, # ^ |   0 i think it's due to eps use 1e-6 http://codeforces.com/contest/782/submission/25268096
•  » » » » » » » » » 4 years ago, # ^ |   0 Isn't it weird behavior just because a 10 is multiplied more you get TLE even though complexity in in log3(n)^2 order and time limit is 5s?
•  » » » » » » » 4 years ago, # ^ |   +3 You may check my solution.Binary search works just fine.I haven't checked a ternary search solution yet,but I believe these two methods are both correct,though may be different in some details.Code
•  » » 4 years ago, # ^ |   0 I used binary search to solve Div2B, try use double instead of float maybe will work.
 » 4 years ago, # |   0 Test case 6 in Div 2 B ?
 » 4 years ago, # | ← Rev. 2 →   0 How did you solve Div2 B?
•  » » 4 years ago, # ^ |   0 Binary search the answer.
•  » » 4 years ago, # ^ |   0 Binary search a suitable x and find t, take the minimum of all iterations.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +1 Binarysearch eps = 0.00000001; L = 0; R = 100000007; while( R-L > eps){ m = (L+R)/2; if(canmeet(m) R = m; else L = m; } res = (L+R)/2; canmeet(long double meettime) { each person can go to the left to x[i]-v[i]*meettime , and to the right to x[i]+v[i]*meettime you have to check if the intersection of all segments [ x[i]-v[i]*meettime , x[i]+v[i]*meettime ] is not empty } 
•  » » » 4 years ago, # ^ |   0 Is it possible by applying binary search on distance?
•  » » » 4 years ago, # ^ |   0 i didn't get, can you explain a bit more about canmeet function ,please?
•  » » » » 4 years ago, # ^ |   0 I'll try to explain.In some time 't', any person can be present at positions in range (x[i]-t*v[i] to x[i]+t*v[i]).All the persons will be present at a common position 'p' iff 'p' lies in all such segments.
•  » » » » » 4 years ago, # ^ |   0 got it thank you :) !!
 » 4 years ago, # |   0 How to solve B? I think this it can be solved by ternary search, but I couldn't implement.
•  » » 4 years ago, # ^ |   0 I passed pretests using ternary search. I'm not sure it is a correct solution, though.
•  » » 4 years ago, # ^ |   0 I make it 10.Suppose now we are searching (l,r). Denote t=(r-l)/10, we divide (l,r) into 10 smaller sections(l, l+t), (l+t, l+t*2) ......(l+t*9, r), then compute the result of l+t, l+t*2, l+t*3 .....l+t*9. Suppose l+t*k is the minimum, the optimal answer must be in (l+t*(k-1), l+t*(k+1)).(10 sections -->2 sections）
 » 4 years ago, # | ← Rev. 2 →   +9 After trying to find a flow solution for problem B, my head is now overflowed...PS: How to build the flow correctly for problem B?
•  » » 4 years ago, # ^ |   0 B -- This can be modelled as a maximum bipartite matching, with all teams sharing the first option having all their first options removed. This is a standard algorithm -- See Hopcroft-Karp for an efficient algorithm.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +2 I feel like an idiot after reading your solution. That's a lot simpler than I thought.
•  » » » » 4 years ago, # ^ |   +3 It can be modeled as 2SAT also, but both of these are overkill solutions. I saw some people in my room had done some nifty 30 line solutions...
•  » » » » » 4 years ago, # ^ |   0 I bet that all these nifty solutions look like flow algorithms. Nson's for example:All teams start with the first option (xxx). Until there's no conflict for some team i, make team i's choice the second option (xx+y).That's it. This is the solution. And it reminds me very much the idea "find an augmenting path and send flow through it" (Ford-Fulkerson's).
•  » » » 4 years ago, # ^ |   0 Can you please explain your graph weights? I tried thinking on the flows solution during the contest, but was unable to find an analogy which completely fits the solution.
•  » » » » 4 years ago, # ^ |   +3 This is a maximum bipartite matching (not exactly max flow), but the most efficient popular solution (in contest contexts) is Hopcroft-Karp, which is basically a specialised case of Dinic's algorithm for max flow.The maximum bipartite matching is as follows: For each team, if it can possibly use its first option (that is, if no other team starts with the same 3 letters), draw an edge to its first option. Then, always draw an edge to the second option. If you can match all vertices on the left to all vertices on the right, then you have found your solution. Otherwise, there is no solution.To convert from maximum bipartite matching (say if you have Dinic's bookcode), simply connect the source to all teams with capacity 1, replace all original edges with capacity 1, and add edges from all abbreviations to the sink with capacity 1.(Unfortunately I had a sneaky bug and failed main tests, but that's the implementation, not the idea.)
 » 4 years ago, # | ← Rev. 4 →   +102 A-D: Graphs Graphs Graphs Graphs
•  » » 4 years ago, # ^ |   +1 B is just tedious implementation, I don't see graphs here.
•  » » » 4 years ago, # ^ |   0 Well I directly throw some flow models (hope no TLE btw), so it's graph for me :(
•  » » » » 4 years ago, # ^ |   0 If you use Dinic's/Hopcroft-Karp, the complexity should be O(N^(3/2)), so unlikely to TLE.
•  » » » » 4 years ago, # ^ |   +19 Funny it can be solved this way. I just looked which teams are forced to have second option (in while loop) and if there are no more than I use first option, that's it. Team is forced to use second option if there is another team with same 3letter prefix (all such conflicts are detected on the beginning) and then in loop I detect conflicts of form that I can't use first option because it is taken.
•  » » » 4 years ago, # ^ |   +32 I used 2-SAT to solve so it's also graph for me.
•  » » 4 years ago, # ^ |   +18 D is matrix multiplication, I don't see graphs here.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   -33 Deleted, sorry.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   -13 He's div1!
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 How to solve D?EDIT: I'm sorry, it can be found here.
 » 4 years ago, # |   +74 Bonus points for those who will come up with a test to D so that longest possible path has length from interval (1018, 260). I think such test will cause many solutions to fail, but maybe such test doesn't exist.
•  » » 4 years ago, # ^ |   +26 It is test 20.
•  » » » 4 years ago, # ^ |   +1 Good job problemsetters :).
 » 4 years ago, # |   +15 i've stuck in B for about 2 hours. What a day!
•  » » 4 years ago, # ^ |   +5 u r not alone my friend. prestest 3 never cleared for me.
•  » » 4 years ago, # ^ |   0 Too. Can't even imagine, where I am wrong. Also, I haven't got any changes in my rating. Is it ok?
•  » » » 4 years ago, # ^ |   0 I think the system is updating the data.
 » 4 years ago, # |   +1 i think B is Ternary Search problem ..i am not sure i couldn't implement it !
•  » » 4 years ago, # ^ |   +5 You was right
•  » » » 4 years ago, # ^ |   +8 I did it using binary search :/
•  » » » » 4 years ago, # ^ | ← Rev. 5 →   0 Although you failed the main tests.
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   +1 I commented before systest was over and thats why the confused emoji was there. Although, it can be solved using binary search. I don't think I said anything wrong there. My implementation maybe wrong but the idea was correct. :)
•  » » » » » 4 years ago, # ^ |   +1 i solved it using binary search and got ac :)
•  » » 4 years ago, # ^ |   0 I used binary search.
 » 4 years ago, # |   0 how to solve D div1 faster than ?
•  » » 4 years ago, # ^ |   +13 Using bitset.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 I was thinking O(N^3 * log (10^18) / 64), where 64 comes from using OR operator to do something like union of sets. But I didn't have time to code it. Besides, I'm curious to know whether there is something faster than O(N^3 * log (1e18)) too.Edit: seems like I was beaten to the response.
 » 4 years ago, # |   0 Any ideas for Div2C?
•  » » 4 years ago, # ^ |   +1 maximum vertex degree + 1
•  » » » 4 years ago, # ^ | ← Rev. 3 →   -8 But what about this test?51 - 21 - 32 - 42 - 5.your answer is 3 but the main answer is 4!P.S. oh. sorry! it was my mistake... the solution is correct.
•  » » » » 4 years ago, # ^ |   0 the degs are 2 3 1 1 1 so answer is 3 + 1 = 4
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 degree(node_2) + 1 = 4 
•  » » » » 4 years ago, # ^ |   0 Why is my answer 3? Highest degree = 3. Add 1, you get 4
•  » » » » 4 years ago, # ^ |   0 first visit current node,then go to current node's child node.For each current node's children,first ensure that it is undiscovered .And then put down perfect color number for this children,start from color number 1,compare each time with children's parent & grandparent,if match,color number increases,is mismatch assign this color number for this children,And mark this node as a discovered node,And goes down from this children :) For total number of color counting,count any noode's total child,then increase it by 1,because node itself is also to be colored :)
•  » » 4 years ago, # ^ |   0 It was just a simple one-pass dfs. For each node, you assign it all values to its children which are not equal to itself and its parent.
 » 4 years ago, # |   0 Will greedy work for div 2 D?I pushed every second option in a vector for the corresponding first option, in a map. For this situation, if answer exists, the answer must be the second option, if size of vector > 1. If size of vector is 1, then we can use the first option for each of these clubs, given this doesn't already appear in our answer.
•  » » 4 years ago, # ^ |   +10 Of course it work, but when you check if there is at least 1 vector with size 1 we have to use the second option, we have to continue searching until all vector of size 1 can use first option
•  » » » 4 years ago, # ^ |   0 Yeah. My implementation took n^2. I am scared of looking at my submissions page, as I didn't do very well.
 » 4 years ago, # |   +4 That was fast.
 » 4 years ago, # |   +10 Thats the fastest system test ever :p
 » 4 years ago, # |   +10 How to solve Div1 C?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +27 Put in an array the nodes following the visiting order of a dfs on the graph. Then, for each contiguous block of ceil(2n / k) nodes in the array, assign a robot. If a robot gets no node, just assign any node to it. This works because the dfs spanning tree has exactly n - 1 edges and you visit each of them 2 times (going down and up); hence, 2(n - 1) + 1 nodes will be visited.
•  » » » 4 years ago, # ^ |   0 Explain to me, please. The total number of verteces, which visited our robots on the basis by K may be < 2 * (n-1), isnt it?
•  » » » » 4 years ago, # ^ |   +5 No. k*(ceil(2*n)/k) >= 2*n
•  » » » » » 4 years ago, # ^ |   0 I am sorry. I have to be careful when reading conditions
•  » » 4 years ago, # ^ |   +5 consider a dfs tree
 » 4 years ago, # |   +9 This is not completely related to the contest itself, but when I go to my room I see a bug in the page title.It says Room #0 instead of Room #21.
 » 4 years ago, # | ← Rev. 3 →   +97 The test data of Div 1 D is weak.This solution, which consider starting at any city, passed system test. 25265977
•  » » 4 years ago, # ^ |   +117 If you don't post this comment, I won't know the starting position is fixed forever though I pass it...
•  » » » 4 years ago, # ^ |   +31 So we're waiting for rejudge? Actually, it's weird. So many people were anxious to challenge. For example, test 2 2 2 2 0 2 2 1 should give the answer 0.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +13 Last time there wasn't a rejudge when a Div 2 D (some rounds ago) have quite weak tests though.P.S. I think my solution does consider starting only at vertex 1 though.
•  » » 4 years ago, # ^ |   +28 System tests are becoming weaker recently, especially in Div 1.
•  » » 4 years ago, # ^ |   +105 Bad job problemsetters :(
•  » » 4 years ago, # ^ |   +31 Omg, I can't believe people are creating anti-unordered_map tests when hacking, but nobody create tests against such thing and people get away with it xd.
 » 4 years ago, # | ← Rev. 3 →   0 When I tried to view the onsite results, I got an error says "You do not have view access to non-public contest".Edit: It's available to me now.
 » 4 years ago, # |   +5 I tried Div1C with Minimum Spanning Tree and Backtracking. in this solution, searched node of backtracking in MST is no more than 2n-2 then i stored searched node and divided k-set....but i got WA. Why?!! T.T
•  » » 4 years ago, # ^ |   +5 I had exact same problem, can somebody explain what getting WA4 means in terms of solution incorrectness?
•  » » » 4 years ago, # ^ |   0 Well the answer is somehow I chose a convoluted and wrong order in the DFS to add the vertices. One simply adds the current vertex, and then after every call of dfs adds the current vertex again. Two line change :(
•  » » » » 4 years ago, # ^ |   0 Thank you guys :) was supper easy I don't know how I didn't figure out the answer faster
 » 4 years ago, # | ← Rev. 3 →   -18 Pro AF Bug xDContest Submission [TLE in Systest] : 25255834 (How did this shit even pass pretests?) After Contest [AC] : 25265826
•  » » 4 years ago, # ^ | ← Rev. 3 →   +6 Your codes are not same and have diffs here :if ((int) colors.size() == neighbours) { break; } "==" instead of ">=" that when there will be a huge vertices with degree of 1 and ans be huge do You will get TLE.
•  » » » 4 years ago, # ^ |   -23 I know that. I was pointing to the subtlety of the bug, and was surprised as to how it passed the first 47 tests.
 » 4 years ago, # | ← Rev. 2 →   +74 Problem B — Spend 1 hours and a half, can't come up with a solutionProblem C — Took me 1 minute to come up with a solution.Moral of today's contest: read all problems' statement first.
•  » » 4 years ago, # ^ |   +21 Exact same situation :(
•  » » 4 years ago, # ^ |   -39 Exactly different situation :(By Technocup onsite results I took C firstProblem C — Spend 1 hours and a half, can't come up with a solutionProblem B — Took me 1 minute to come up with a solution.(Because Binary/Ternary Search is my favorite topic)Moral of today's contest: read all problem's statement in first come first solve manner.
 » 4 years ago, # |   +20 I got wrong answer on case 16 DIV2 D . Can't find the error . Please help !! http://codeforces.com/contest/782/submission/25264212
•  » » 4 years ago, # ^ |   +1 me too and it is really making me angry -_-
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +6 test case : 3 ABA REF ABD AFG ABD OOO My solution : NO actual solution : YES ABR ABA ABO The error was that all the one length vectors(vector of all strings with same shortname1) need to be checked at the last , since only those vectors has 2 possible options. 
•  » » » » 4 years ago, # ^ |   +3 But my solution still gives the right answer :(( and I still have no idea what's wrong
 » 4 years ago, # | ← Rev. 2 →   -13 is it B div2 or B div1 ? http://codeforces.com/problemset/problem/782/B
•  » » 4 years ago, # ^ |   +2 Div.2 B
 » 4 years ago, # |   0 can someone give me a simple implementation for B .. i couldn't implement it well ?
•  » » 4 years ago, # ^ |   0 I understood solution from my friends code, maybe it can help you. My friends code#include #include #include #include #include #include #include #include #include #include #include #define MAXN 100010 #define INF 0 #define PI 3.14159265359 #define pairr pair #define pairrr pair #define f first #define s second #define pb push_back #define ll long long #define MOD 301907 #define IO ios_base::sync_with_stdio(false); cin.tie(); #define PQT pairrr #define PQL priority_queue, less > #define PQG priority_queue, greater > using namespace std; int n,i; double l,r,m1,m2,x[60010],v[60010]; double f(double m) { double res=0;; for (i=0;i>n; for (i=0;i>x[i]; for (i=0;i>v[i]; l=1; r=1000000000; while (r-l>0.000001) { m1=l+(r-l)/3; m2=r-(r-l)/3; if (f(m1)>f(m2)) l=m1; else r=m2; } cout.setf(ios::fixed); cout<
•  » » 4 years ago, # ^ |   +5 here is my solution 25259459I use ternary search for finding a meeting place
•  » » » 4 years ago, # ^ |   0 I used Binary Search on meeting place and keep getting WA at test 24? Could it be Binary Search cannot be used for meeting place?
•  » » » » 4 years ago, # ^ |   -9 Meeting place will not always be an integer. So yes, you cannot use Binary Search for the meeting place.
•  » » » » » 4 years ago, # ^ |   +8 You can use binary search with doubles too...
•  » » » » » » 4 years ago, # ^ |   0 Oh right, I just realized you can manually terminate it after 'x' iterations similar to how ternary search works.
•  » » » » » 4 years ago, # ^ |   0 such a tricky test. Every person stood on the same place. Binary search works out with meeting place. Thank youMy submission: http://codeforces.com/contest/782/submission/25267635
•  » » » » 4 years ago, # ^ |   0 Yes, if you take the limits l = minimum x, r = maximum x you can imagine f(position) begin max(left(position), right(position)). left is the maximum time to get here from the positions to the left and right is from the right. This function is the maximum of an increasing funtion(left) and a decreasing function(right), so it is not always monotonic.
•  » » » » 4 years ago, # ^ |   +3 Check your answer when all the persons are at the same point. I also applied binary search on the distances. Since my upper limit and lower limit were equal from the beginning, my code was failing on test 24.Added an if statement to get AC after the contest.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 I did this: Binary search on the answer. For each value t, you can examine if all of the friends can meet somewhere within t seconds.First, examine what is the minimum xi, such that xi = posi + speedi * t. Then, min(xi) is the best place to meet if we have t seconds of time. Try to examine if everyone positioned after min(xi) can reach min(xi) after t seconds. If yes, it is possible to meet within t seconds; it is not otherwise.
 » 4 years ago, # | ← Rev. 3 →   +20 Why we can't see successful submissions? UPD: Seems it is fixed
 » 4 years ago, # |   +19 Why can't we see the tests ?
 » 4 years ago, # | ← Rev. 3 →   +5 Why can't I see other people submissions? All, not just ones from today's competition.
 » 4 years ago, # |   -18 That one statement ruined everything -.-
 » 4 years ago, # |   +22 I believe we have waited enough for the ratings to be updated :D
 » 4 years ago, # |   0 what's the solution for Div2D?
•  » » 4 years ago, # ^ |   0 Stupid greedy implementation. Try to name the team using the first choice. If you can't, try to name the team using the second choice and rename those that conflict with the new name. If you can't rename those, it means that it is impossible.
•  » » » 4 years ago, # ^ |   0 implemented by choosing second choice first. WA on 6th pretest :(
•  » » 4 years ago, # ^ | ← Rev. 6 →   +11 Maintain a DSU and place all the teams having same team name [first three characters] in a same component and also maintain the size of each component. Now, if there are two teams u , v (u != v) such that both the teams belong to the same component and the short names formed by using second option for both u and v are equal, then the answer is NO. Now, name all the teams in a component having size > 1 by using second option. Teams having only 1 node in its component has two options, either use first option or second, if both the strings are already used then again the answer is NO, else use either of them which isn't used yet.PS- This solution is wrong, test data were weak enough to let this solution pass.Test where it can fail :ABC DDDABD DOGMaximum Bipartite Matching shall be used to assign the shortnames to the teams having only 1 node in its component.
•  » » » 4 years ago, # ^ | ← Rev. 3 →   0 My solution seems correct (it passed). The algorithm is :- First put type 1 name for all. If a name has multiple copies, take type 2 name for all in the conflicting name. If some conflict still exists, change type 1 to type 2 in that conflict. If multiple type 2's in a name, answer doesn't exist. Repeat 3 till no change made. Check if every name is unique. My actual implementation was O(N^2*log(N)), since I used sets, however with hashing, this will be O(N^2).This is so because in step 3, atleast one name is pushed to type 2 for every iteration. Giving maximum N iterations => O(N*(complexity of one iteration)).
 » 4 years ago, # | ← Rev. 2 →   -38 To administrators and problem designers： I am an OIer from China. (Never asking me why I chose Iceland) Every time I and my friends participated in the round, questions which are written in English worried us greatly. This takes us too much time to understand the meanings . As to myself , in this round , I could have worked C out within 5 more seconds . It takes me too much time to understand B and I could have save the time to work C. So , I request you can prepare questions which are written in Chinese in any form ( a file to download or any else ). Maybe this is not that easy to work , or maybe you haven't the translater , or maybe other countries' participants need questions in their language costs you too much time . It doesn't matter . We wish the problem description can be more clear , terse and easy to understand . This will help us greatly . If you can take my suggestion ， I will be deeply grateful.Yours sincerely Real_EnderDragon
•  » » 4 years ago, # ^ | ← Rev. 2 →   +12 There are so many interesting things about competitive programming in chinese websites I wish I could be able to translate at least to english... And english is not even my natural language :(
 » 4 years ago, # |   0 Can some please help me to find bug in my solution for problem B , why i am getting WA in on test 8 . solution Link
 » 4 years ago, # | ← Rev. 2 →   +6 I've tried 2-sat in div2-D but got WA. Is enough to test these four cases?Let option 1 = true, option 2 = false, 'a' and 'b' a team case 1: first (a) == first (b) -> (¬a || ¬a) && (¬b || ¬b) — both second optioncase 2: second (a) == second (b) -> (a || b) && (¬a || ¬b) — a and b must be differentcase 3: first (a) == second (b) -> (¬a || b) case 4: second (a) == first (b) -> (a || ¬b)
•  » » 4 years ago, # ^ |   +8 On case 4 check your condition again. I think it must be (second(a) == FIRST(b)).
•  » » » 4 years ago, # ^ |   0 Ops, you're right, I made a mistake in the description but it's correct in the code, thank you! Any other observation?
•  » » 4 years ago, # ^ |   +18 In case 2, when first(a) != first(b), you can choose option1 for both so it should be only (a||b).
•  » » » 4 years ago, # ^ |   +5 That was it, it worked now, thanks a lot!
 » 4 years ago, # |   +3 waiting and waiting for rate change ...
 » 4 years ago, # | ← Rev. 2 →   -8 Is the ceiling function notation used in the statement of div1.C considered to be general knowledge? I've never seen it before and got a WA on system tests because I thought it was an integer function. It would be nice if the statement always contained definitions of all nontrivial functions used in it (IIRC, they even provide a definition of bitwise operations in TopCoder SRMs. I don't think it hurts anyone).
•  » » 4 years ago, # ^ |   0 I think it's quite common. I've seen it at least in Introduction to Algorithms by Cormen and others and also in Concrete Mathematics by Knuth and others.But agree, that statements should contain definitions. Or maybe we can have some extra page Notation on codeforces like some of the books have, that will cover common cases.
 » 4 years ago, # |   +10 F looks moderately interesting, and there has been no discussion on it, so maybe I'll start with an idea.We binary search on the answer D. Hence, we only need concern ourselves with whether it is possible to achieve synchronization with distance D.Consider the distance between buses 1 and 2 as they around the circuit. Consider a time segment through which neither bus turns a corner. Then the distance function over this segment only has at most 1 turning point, and so will pass D at most twice.In fact, we know if there is a turning point in this segment: the only difficult case is when the buses are travelling perpendicular to each other, in which case, pretending that the line segments extend infinitely into the past and future, the turning point is precisely the point where the buses are equidistant from the intersection of their lines, with one bus moving towards and one bus away from the intersection. This is the only possible turning point of the function.Hence, with some effort, we can find the points where f(x) = D, and hence the intervals where f(x)>D. (I'm fuzzy on this front, but binary division seems like it'll run in time.)Assume we can compute the intervals on which the distance between the 2 buses exceeds D. Then, we can take the union of all these intervals modulo the distance between the 2 buses, ie. treat the time as cyclic with period of (length of route/number of buses). If the entire interval is covered, then D (or at least, D-1e-7) cannot be achieved. Otherwise, D can be achieved, and we can proceed with the binary search.Checking of unions of interval over a line segment can be done using a set, for example.Any errors/simplifications?
•  » » 4 years ago, # ^ |   +15 That's more-or-less what I was implementing, but couldn't find the bugs in time. For each interval where the two buses are moving in a straight line, the vector between them varies linearly, and asking for the two times at which the distance exactly equals D requires solving a quadratic equation. If the determinant is negative then they are never within D of each other, otherwise you get an interval, which then also needs to be clipped to the time interval you're considering.I took intersections of intervals when the distance is at most D rather than unions of the complement, but it's equivalent. It also simplifies things to insert breaks at every multiple of the inter-bus separation (i.e. treat those times as if bus 1 made a turn), so that the intervals you get never wrap around.
 » 4 years ago, # | ← Rev. 2 →   0 Div2 B using while(r-l) > 1e-7 failed system test (time limit) http://codeforces.com/contest/782/submission/25253014using while(r-l) > 1e-6 after the contest accepted http://codeforces.com/contest/782/submission/25265567life is so cruel
•  » » 4 years ago, # ^ | ← Rev. 3 →   0 I used 1e-9 in my submission, 100ms. Life is so kind to me then!
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +5 i think because you used binary search, you always divide by 2 so you will not face numbers like 0.3333(with infinite threes), but i used ternary search (has dividing by three) which will face this kind of numbers, so it will be truncated then due to the double precision and a high probability that r and l will reach a point that they will not change after it in the loop (so infinite loop occurs)this gives me a lesson in the future to include additional check to check that if the calculated numbers (boundaries) in the loop didn't change from the last iteration then break from the loop.
•  » » » » 4 years ago, # ^ |   +5 I also had an infinite loop in ternary search, but my lesson is a bit different. Instead of checking absolute error, I'll just do a loop with a fixed number of iterations: for (int i = 0; i < 200; i++) ... 
 » 4 years ago, # | ← Rev. 2 →   +48 I think Dataset for Div2 D is weak. Say for this case 2 ABC DDD ABD DOG This submission outputs NOAnd The Winner's submission outputs YES.
 » 4 years ago, # | ← Rev. 2 →   0 Hi guys, can you explain me, why this Solution has TLE? Sol when I did another using Boolean tab it has compiled program in 140ms, is this really that big difference?
•  » » 4 years ago, # ^ |   +6 Of course it does. :)Your algorithm implemented with a list is O(N^2) for n = 10^5, this will definitely give a time limit.The other one is O(N) which passes. If that confuses you read about big oh notation, and then see for what input size you can do each one.
 » 4 years ago, # |   0 Div2 D has a very weak test casessome ACC soultion output YES and some output NO in this case 3AAA BBBAAA CCCAAD BBB
 » 4 years ago, # | ← Rev. 3 →   0 I used ternary search finding derivative tending to zero to solve Div2B 25253744As F(position)=time has only one local min, then it is the global one so the only point with derivative=0 is the solution (and both left and right parts of the graph are infinite descending and ascending)Thank you calculus :)
 » 4 years ago, # |   0 Someone with WA16 on Div2D/ Div1B? 25271010
•  » » 4 months ago, # ^ |   0 I know its too late to respond, but i am stuck right there.Could you please help??
 » 4 years ago, # |   0 How can I implement Div2 B using binary search ?
•  » » 4 years ago, # ^ | ← Rev. 3 →   +2 Let the function f(x) return the time to gather to the point x. The domain is [a,b]. a is the leftmost coordinate and b the rightmost one. It turns out that f is first decreasing and then increasing after some X. The task is to find X, at which f attains its minimun.Take the middle point of the current interval.Compute f(mid-eps), f(mid), f(mid+eps). Take eps a very small positive number like 0.0000001.If f(mid-eps) < f(mid) < f(mid+eps), then the answer is in [a,mid].If f(mid-eps) > f(mid) > f(mid+eps), then the answer is in [mid,b].Else the answer is mid itself.Just simply implement with a while loop.
•  » » » 4 years ago, # ^ |   0 I have done exactly that 25253744. Only that I called that difference derivative and my goal was to find when derivative was 0.
•  » » » 4 years ago, # ^ |   0 Good explanation. I managed to get AC based on this. I have some complementary questions though. When you solved this problem on the contest, did you find exact proof for the fact that "f is first decreasing and then increasing after some X"? Or just viewed some example data and presumed that this will hold for all input? How to choose proper epsilon? If I choose too big than relative error will be big also. If I choose too small than maybe I can't get differences in the value of the function. Is it possible to bound the relative error in the value of the function based on epsilon. Is there any exact proof?
•  » » » » 4 years ago, # ^ |   0 I just found it intuitive that while you are getting far from the optimal point the time is only increasing. I don't have any idea about the rigorous proof. Regarding the epsilon I usually take it a bit smaller than the relative error.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 I think in those cases fixed number of iterations is more predictable, more safe, and more practical. Fix on a number of iterations enough big to avoid precision problems, and enough small to avoid TL. usually around 100 satisfies both with margin
•  » » 4 years ago, # ^ |   +3 My approach is a little bit different from the other one.Do binary search for the point in the interval. For a given point, there will be a friend from the north who reaches the point last of all friends from the north, and similarly a friend from the south. If these two are equally slow, you found the answer. Else move towards the slower one.
•  » » 4 years ago, # ^ | ← Rev. 3 →   +3 Binary search (on doubles) for the minimum time t it takes for all the people to meet.For a given time t, note that the set of places person i can reach within time t is the range [pos[i] - v[i]·t, pos[i] + v[i]·t] on the number line. It is possible for all of the people to meet in a given time t if there exists a point inside all the ranges, or if the intersection of all these ranges is not degenerate. To check if the intersection of all these ranges is not degenerate, we can let l be the maximum of the left endpoints of these ranges and r be the minimum of the right endpoints of these ranges. If l ≤ r, it means the intersection of the ranges is not degenerate, while if l > r, the intersection of the ranges is degenerate.
 » 4 years ago, # |   +10 How to solve Div1E?
•  » » 4 years ago, # ^ |   +3 If you can find quickly, given where each ball starts its fall, which platform it lands on, then the rest of the question is easy. There are at most 3e5 such computations to make.Consider processing each of the 3e5 queries from left to right (each query asks, for a starting point, where it ends). For each platform i, there is a maximum height h_i for which it will accept. Consider an array storing h_i's. Then, if we have a ball (index i in array) falling from height H, we simply want to find the minimum index greater than i of the array with entry at least H.We just need to support queries of the form: i) Point update ii) Point update iii) Range query of maximum in rangeThis can be done using a segment tree. Binary searching to find the minimum such index gives O(lg^2 N) every query, but can be sped up to O(lg N) if we build it into the segment tree.
 » 4 years ago, # |   0 How to solve Div2C with BFS? TIA
 » 4 years ago, # |   0 Can I ask something? I was wondering how my rank became 'pupil' ? I wasn't able to solve any problems on div 2 correctly. I was expecting that my rating would be 'newbie'. Why ?
 » 4 years ago, # | ← Rev. 3 →   0 I'm wandering if there will be an official tutorial. Or if anybody could tell me that if is the best time complex for Div1.D? Thanks a lot!
•  » » 4 years ago, # ^ |   0 I think many solution have that complexity as well. (at least mine is)
 » 4 years ago, # |   0 not rigorous DATA FOR YESTERDAY'S 781B Innokenty and a Football League THAT SOMEONE USE WRONG PROGRAM TO PASS THE TEST. WE MAY INSERT TWO DATAS THAT CAN SOLVE IT INPUT 1 3 ABC GGG ABG GCC ABD EEE OUTPUT 1 YES ABC ABG ABD INPUT 2 3 ABC DDD ABD CCC ABD EEE OUTPUT 2 YES 3 ABD ABC ABE
 » 4 years ago, # |   0 How to solve Div1D/Div2F?
•  » » 4 years ago, # ^ | ← Rev. 9 →   +33 Let me define it:f(0,0) = P;f(0,1) = B;f(1,0) = f(0,0) + f(0,1);f(1,0) = f(0,1) + f(0,0);f(i,0) = f(i-1,0) +f(i-1,1); f(i,1) = f(i-1,1)+ f(i-1,0);...Let DP[u][j][x]= (the set of vertices that the vertex u, on the j-th, x-th state of this function can reach);Basically, for each edge u->v,w , you must add: Dp[u][0][w][v]=1; then, for each i until (60) for each vertex u for each i, w of the funcion f , you must calculate the Dp[u][i][w];Remember that we have calculated the Dp[u][i-1][w]! Then , for each vertex v , that you can reach on the state(u,i-1,w) , we have to add the set of vertex that the state(v,i-1,!w).to implement union of sets efficiently you could use a bitset!the complexity: O(n^3*log(10^18)). Your code here... bitset<501> alcance[61][501][2]; int n,m; // 0 = P , 1=B // i-esima string , estando no vertice j, com a string bonita ou nao // quem esse estado alcanca :) int main() { sc2(n,m); for(int i=0;i estado; estado.reset(); estado[1]=1; ll resp=0; bitset<501> prox; int bit=0; for(int i=60;i>=0;i--){ prox.reset(); for(int u=1;u<=n;u++) if(estado[u]){ prox|=alcance[i][u][bit]; } if(prox.count()) { bit=!bit; resp+=(1ll<1e18){ pri(-1); } else{ printf("%lld\n",resp); } return 0; } I hope it helps ! Sorry for my bad english!
•  » » » 4 years ago, # ^ |   0 What is the function f for?
•  » » » » 4 years ago, # ^ |   +10 I think f(I, 0) is the correct sequence obtained after (I + 1)th step and f(I, 1) is the sequence obtained by changing all P's to B and all B's to P in f(I, 0).
•  » » » » » 4 years ago, # ^ |   0 Yeah..thanks. Makes sense now.
•  » » » » » 4 years ago, # ^ |   0 yes! it is !
•  » » » » » » 4 years ago, # ^ |   0 Hi, which is bitset average/worst complexity?
 » 4 years ago, # |   0 Can someone find the mistake in my DIV1 B/DIV2 D , it fails on test case 16 http://codeforces.com/contest/782/submission/25261134
•  » » 4 years ago, # ^ |   +7 It is very difficult to figure out exact problem but I also got WA in pretest for this case first then I corrected it with some small changes in the code. I guess you must be making similar mistake. The second loop that you are using, I guess it should be used n times rather than only one time. The problem is when you make someone switch from first to second option this may create some new conflicts which you have to correct in next iteration. One more thing I can see is you are using the array taken which I think is not necessary, You can just update the map every time (In your second loop). If you still have some problem, Have a look at my solution it is quite similar to yours.
•  » » » 4 years ago, # ^ |   0 thanks for the reply, " The problem is when you make someone switch from first to second option this may create some new conflicts which you have to correct in next iteration."can u give an example for such situation ?
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +1 1 ABB ABD 2 ABB ABE3 ABX ABY4 ABF ABX5 ABE ABFHave a look at this. The first column is first choice and second column is second choice. I guess this is what I am talking.
•  » » » 4 years ago, # ^ |   0 Why loop N times? How does iterating N times completely remove all conflicts?
•  » » » » 4 years ago, # ^ |   0 In 1 loop you at least fix one of the relation. That relation you will never change again. So after n loops all of them will get fixed value. ( Another intuition to this is it is like we are finding a matching using Ford fulkersons and finding the augmenting path in every loop, So after finding n augmenting path, We find a matching)
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Did you find a solution? I'm also struggling with WA on test #16 http://codeforces.com/contest/782/submission/25303767. Did you find a have a simpler failing testset? On:5 ABB D ABB E ABX Y ABF X ABE FI get (correctly):YES ABD ABE ABY ABX ABFEDIT: Oh, forget it, think I found it, I go wrong on:4 AAA B AAA D AAC E AAD C
 » 4 years ago, # |   0 Ohh thanks :D
 » 4 years ago, # |   0 where I can find the editorial to the DIV 2 problems of this contest. Any help please. Apart from that can anyone explain the solution to the second problem i.e. the meeting place can't be changed.
 » 4 years ago, # |   0 In DIV2 B, I get TLE on test 3 http://codeforces.com/contest/782/submission/25283174but if i write functions for min and max , it gets AC http://codeforces.com/contest/782/submission/25283217why is it so ?
•  » » 4 years ago, # ^ |   +1 Your mistake — double d = 1e-9. If you write, for example, double d = 1e-7 you will get AC with both min/max functions. Also you can use long double, it (probably) takes 16 bytes.Double numbers on server (probably) takes 8 bytes, so maximum count of significant decimal digits is about 17.Sorry for my english:)
•  » » » 4 years ago, # ^ |   0 thank you !
 » 4 years ago, # |   +5 Will there be an editorial? Or is there anybody can tell me why simple dfs can work on DIV2-E/DIV1-C and how to prove the correctness? Thanks a lot
•  » » 4 years ago, # ^ |   +25 Basically the idea is that if you solved the problem for k = 1, then you can solve for k > 1 as well since you just take the solution for k = 1, split it into k equal parts and make sure each part is nonempty.To solve for k = 1, you need to go through all vertices in the graph in at most 2n moves. Since the graph is connected, we can find a spanning tree of it. Now, we can just do an euler tour on the spanning tree which contains 2n - 1 vertices. DFS can be used to find the spanning tree.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +5 How quick! I get it, thank you.
 » 4 years ago, # |   +1 For div2/B is there any solution rather than binary/ternary search?
 » 4 years ago, # |   +2 This is the first time to go to blue Expert! Incredibly!!!
•  » » 4 years ago, # ^ |   +27 And this was my 7th time to become Expert... I wish I could be that excited. :)
•  » » » 4 years ago, # ^ |   +2 I just use codeforces one year! :) You dropped down to Expert, I rose to there.... Perhaps next contest will kick my ass dropping down to specialist! ahaha
 » 4 years ago, # |   +10 Edutorial please...
•  » » 4 years ago, # ^ |   0
 » 4 years ago, # | ← Rev. 2 →   +17 Is there an editorial for the contest KAN ?
•  » » 4 years ago, # ^ |   0 Here this is http://codeforces.com/blog/entry/50854
 » 4 years ago, # |   0 In div2D, I want to know the answer of below case. 3 ABC DEF ABD EFG ABE DEFI think the answer is YES(ABC,ABD,ABE), but my source print "NO" although I got an AC.
•  » » 4 years ago, # ^ |   0 my answer is Yes !
 » 4 years ago, # | ← Rev. 2 →   +15 For people who are having trouble with Test case 16 on DIV2 D, consider this test case:4ABD BCDABC DDDABR CDDABR XYYThe answer should be:YESABBABDABCABXMy solution which gives WA on test 16 fails this test too.
 » 4 years ago, # |   0 Solution for Div 1 E ? Anyone ?
 » 4 years ago, # |   0 can anyone help me in understanding of div2B editorial ?
 » 4 years ago, # |   0 can someone please find why i am getting runtime error in python2.7 in problem C div 2?Here is my code, a big thanks in advance