By isaf27, history, 21 month(s) ago,

Hello, Codeforces!

I'm glad to invite you to Grakn Forces 2020, which will be held on Sep/30/2020 17:35 (Moscow time). It will be combined rated round for both divisions.

This round is initiated and supported by Grakn Labs. More information you could find here.

All problems were authored and prepared by 300iq and isaf27. Thanks to growup974, Retired_cherry, QAQAutoMaton, Prakash11, morzer, qlf9, nkamzabek, gdb_18, talibmohd, Dragnoid99, KAN and VladGanzha for testing problems and good advice. Thanks to MikeMirzayanov for great systems Codeforces and Polygon.

You will be given 9 problems and 2 hours 30 minutes to solve them. Please, read all the problems. Good luck, have fun and we wish everyone high ratings!

Thanks to Grakn Labs for the gifts to the participants:

Prizes:

• 1st place = 500 euros
• 2nd place = 250 euros
• 3rd place = 100 euros

Grakn Labs swag pack:

• Stickers
• Grakn Labs t-shirt

Grakn Labs swag pack:

• Stickers
• Grakn Labs t-shirt

Grakn Labs is a team of people driven by a purpose: to solve the world's most complex problems, through knowledge engineering. They are the inventors of the Grakn knowledge graph and the Graql query language. Their technology helps organizations in various industries, including Life Sciences, Defence & Security, Financial Services, and Robotics, to build intelligent systems that will change the world.

Grakn Labs looking for the best to round out their team, if you think this sounds like an interesting chance to work on an innovative technology; they'd love to hear from you.

FILL OUT FORM →

UPD! Scoring distribution: 500 — 1000 — 1250 — 2000 — 2500 — 2500 — 3000 — 3750 — 3750

UPD! Editorial

Congratulations to winners:

Announcement of Grakn Forces 2020

• +506

 » 21 month(s) ago, # |   +657 As a tester, I want contribution
•  » » 21 month(s) ago, # ^ |   +239 ok
•  » » 21 month(s) ago, # ^ |   +142 Let me try my luck as well
•  » » 21 month(s) ago, # ^ |   +47 You deserve it. <3
•  » » 21 month(s) ago, # ^ |   -66 ok
•  » » 21 month(s) ago, # ^ |   -36 Really,u deserve it!!
•  » » 21 month(s) ago, # ^ |   -99 As a tester, I want contribution too :)
•  » » 21 month(s) ago, # ^ |   +12 why not
•  » » 21 month(s) ago, # ^ |   +72 As a tester wasn't it your responsibility to check the bug in B one correctly.. plaese correct me if I am wrong.. I think that is real job of tester is to check there are no bugs in the preparation of the round (intended solution, validator, checker, interactor, etc) rather than asking for contributions..
•  » » » 21 month(s) ago, # ^ |   +86 I'm sorry about this. In fact, I tested the other 8 tasks, but B is a newer task after my testing, they even don't show it to me until the contest start
•  » » 21 month(s) ago, # ^ |   +13 This is an OP way to get contribution.
»
21 month(s) ago, # |
Rev. 4   +22

UPD : Wished seeing a good round without any issue but it was as same as previous (stucking B)

# RIPRating

 » 21 month(s) ago, # | ← Rev. 2 →   -36 .
•  » » 21 month(s) ago, # ^ |   +33 No.. Just like other global rounds.
•  » » 21 month(s) ago, # ^ |   +127 The only ones that possibly lose something more in combined rounds are div1 people that get beat by div2.
•  » » 21 month(s) ago, # ^ |   +4 Let's not think about rating but exprience and learning something
 » 21 month(s) ago, # |   +15 Will this contest be similar to global rounds?
•  » » 21 month(s) ago, # ^ |   +9 Yes
•  » » 21 month(s) ago, # ^ |   0 Yeah,kind of
 » 21 month(s) ago, # |   -48 Whoa! Rush_For_AC you wanted contribution and you got it! (although it is negative) xD xD xD. And now you have edited the comment hahaha
•  » » 21 month(s) ago, # ^ |   +9 well same to you xD
 » 21 month(s) ago, # |   -15 Dragnoid99 Nice to see your name in the contributor's list!!
 » 21 month(s) ago, # |   +66 isaf is the trusted author !!! :hug:
•  » » 21 month(s) ago, # ^ |   +7 :ghosthug:
•  » » » 21 month(s) ago, # ^ |   -21 Shut up mr master
•  » » » » 21 month(s) ago, # ^ |   +67 Shut up mr master
•  » » 21 month(s) ago, # ^ |   +3 I don't understand on which basis you decide which one is trusted and which one is untrusted, which one is interesting and which one is boring?
•  » » » 21 month(s) ago, # ^ |   +3 based on the previous contests of the authors. isaf's 1054F - Electric Scheme is gorgeous!!!!
 » 21 month(s) ago, # |   -29 I want to participate but I have a confusion. It is said that Grakn is distributed knowledge "Graph". So will majority of questions(or all) be related to graph theory in this contest? (I am having this perception because Div1 people also participating along with CMs,Experts, Specialists and Pupil). Please tell.
•  » » 21 month(s) ago, # ^ |   -8 I do also have the same question. Would you like to say something regarding this, isaf27 ?
•  » » 21 month(s) ago, # ^ |   +33 When you use 100% brain.
 » 21 month(s) ago, # |   +267 Me after seeing 300iq is a problem setter.Wrong answer on test case 256.
•  » » 21 month(s) ago, # ^ |   +20 Wrong answer on test case 300*
•  » » » 21 month(s) ago, # ^ |   +17 It actually happend Wrong Answer on test 9 on B*
 » 21 month(s) ago, # |   +411 9 problems again :(That's too many for a short competition, especially with CF scoring (where the speed of solving easy problems matter most). It favors people like me who can do div2 problems quickly and then just are stuck with hard problems.
•  » » 21 month(s) ago, # ^ |   +16 we missed "that's stupid!" in your comment! that's rare! :v
•  » » 21 month(s) ago, # ^ |   +43 Actually not sure about that. Considering that A and B are just one minute tasks, we have a round with 7 problems. With decent problem difficulties it looks like ordinary Div 1 with 5 problems, except that for the hardest task you can choose between 3.
•  » » » 21 month(s) ago, # ^ |   +62 isn't that the point? favours people who can actually do A and B in 1 minute each
•  » » » » 21 month(s) ago, # ^ |   -95 A and B in combined normally aren't the type of problems you EVER get stuck, so no.
•  » » » » » 21 month(s) ago, # ^ | ← Rev. 2 →   +17 i just did it.
•  » » » » » » 21 month(s) ago, # ^ |   -22 I mean I did that too, still I believe my point is valid for high rated users.
•  » » » » » » » 21 month(s) ago, # ^ |   +24 soo 2800 is not high enough?
•  » » » » » » » » 21 month(s) ago, # ^ |   -17 Have you heard about rating inflation? I'm an example of it.
•  » » » 21 month(s) ago, # ^ |   +133 'A and B are just one minute tasks'. This didn't age well
•  » » » » 21 month(s) ago, # ^ | ← Rev. 2 →   +2 I was in even more panic while solving B since I had read this statement lol
•  » » » 21 month(s) ago, # ^ |   0 A,B just one minute task ! i see...
•  » » 21 month(s) ago, # ^ |   0 I'm curious to know how do you approach the situation when you are stuck on a hard problem. Thanks!
•  » » 21 month(s) ago, # ^ |   +35 So now after seeing the actual problem set, where do you draw the line for "easy tasks" for today? A-G? Or do you see it differently?And what do you think about the problem set in general?
•  » » » 21 month(s) ago, # ^ |   +26 I would say that ABC were too easy and I would prefer to just get D+. The first two problems were so artificial and definition-heavy. It's the opposite of what I would want to show to a beginner as a cool problem.If one really wants to use 9 problems, I would expect A and B to be very very easy (more like div3 than div2). So those problems were more difficult than I expected. And if I was a beginner, I would hate the fact that there is almost no programming in ABC.It's also worth noting that the average time of solving problem A is around 3 minutes for high-rated people. It's far away from "A and B are just one minute tasks". It also takes time to open the statement, create a new file, copy samples and submit. Reading and clicking speed matters, hurray.In terms of quality, I didn't like anything about ABCDE, but then F and G were very nice and their difficulty is around div1-C.
•  » » 21 month(s) ago, # ^ |   -10 tourist solved all of it
•  » » 21 month(s) ago, # ^ |   -26 I guess this contest favoured you a lot. Lol
 » 21 month(s) ago, # |   +2 i wish this contest will be a good contest :3
 » 21 month(s) ago, # | ← Rev. 2 →   +26 Not any more.
 » 21 month(s) ago, # |   0 Can anyone tell me what is the level of first 3-4 problems in a combined div1 and div2 rounds like this. I'm a pupil and have solved at most 3 problems in normal div-2 rounds.
•  » » 21 month(s) ago, # ^ |   0 It varies a lot but I think authors try to keep the consistency of first 6 problems the same as div2, ie combined B is around the level of div2B
•  » » 21 month(s) ago, # ^ |   +9 i hope distribution look like div.3(2)+div2(4)+div1(3) kind of distribution, otherwise it seems very unlikely to have contest of 9 problems.
 » 21 month(s) ago, # |   +67 As a tester, I wish you all the best of luck :)
 » 21 month(s) ago, # |   +9 Thanks for bringing Grakn forces contest into codeforces to us! ^_^
 » 21 month(s) ago, # | ← Rev. 2 →   0 Hope this contest will give high delta as compared to the past two contest where rating change as per rank was a bit unusual.UPD: Ah shit! here we go again!
•  » » 21 month(s) ago, # ^ |   0 Yeah
 » 21 month(s) ago, # | ← Rev. 2 →   0 300iq orz
 » 21 month(s) ago, # |   +50 As a tester, give me contribution.
•  » » 21 month(s) ago, # ^ |   -32 come on growup man!
•  » » » 21 month(s) ago, # ^ |   +21 wtf wrong i wrote ............ i thought people at codeforces could understand surcasm
•  » » 21 month(s) ago, # ^ |   0 Done Bro!! Enjoy. Wish us good luck!
 » 21 month(s) ago, # |   0 this post is what I wish the other post was (https://codeforces.com/blog/entry/82787?#comment-704138)
 » 21 month(s) ago, # |   0 I was excited to participate in this unique round, but unfortunately, it conflicts with my first major exam. I hope such contests are held on weekends. I hope you all enjoy the contest.
 » 21 month(s) ago, # |   -35 as someone who didn't do anything, i want contribution
•  » » 21 month(s) ago, # ^ |   +20 *negative
 » 21 month(s) ago, # |   +10 Please note the usual timings of the contest :D
•  » » 21 month(s) ago, # ^ |   0 I literally went to see the time in the blog after seeing this
 » 21 month(s) ago, # | ← Rev. 2 →   -13
 » 21 month(s) ago, # |   -20 Is it rated for div3 people?
•  » » 21 month(s) ago, # ^ |   +1 Yeah,It is rated for every Division.
•  » » » 21 month(s) ago, # ^ |   0 Okay Thanks :)
•  » » » » 21 month(s) ago, # ^ |   0 My pleasure :)
•  » » 21 month(s) ago, # ^ |   -24 are div3 people live on earth?
 » 21 month(s) ago, # |   0 Will problems only in English or both languages are welcome?
 » 21 month(s) ago, # |   0 2h 30min lol
 » 21 month(s) ago, # |   -34 hello. i am dmitry and i am tester. give me contribution. i like sausages.
 » 21 month(s) ago, # |   +4 What will be the difficulty level of A & B problem?
•  » » 21 month(s) ago, # ^ |   +1 500 and 1000 respectively, the post is updated with the score distribution now.
•  » » » 21 month(s) ago, # ^ |   +2 emmm. it is scores, not difficulty
•  » » » » 21 month(s) ago, # ^ |   +6 Oh yeah that's true but it's a rough estimation of a problem difficulty as well isn't it
•  » » » » » 21 month(s) ago, # ^ |   +3 agree
 » 21 month(s) ago, # |   +16 12 more minutes remaining. Wish you all a very good luck!
 » 21 month(s) ago, # | ← Rev. 2 →   +1 Dear Grakn Labs authors,I have some questions, How many people would you admit for Lab internship? And What is your requirement for these positions?thanks for holding a CF's contestregard.
•  » » 21 month(s) ago, # ^ |   +28 Ideally, we are looking for fulltime candidates, but internships are also possible. Regarding the number of candidates: we don't have a fixed number, if there are 2 very strong candidates who both fit, I would imagine we will take both, but hard to say upper limits and it depends on the candidates. And What is your requirement for these positions? We test cognitive abilities, problem-solving skillz, we gonna ask about previous experience, education (are you from STEM or not?, bachelor / master / phd?) but we don't have "must know language A, library B" requirements. Although for a more senior position we gonna expect you to know some specific stuff
 » 21 month(s) ago, # |   +12 Let's hope that there isn't any extreme jump in difficulty lvl...
 » 21 month(s) ago, # |   0 why does more companies don't host contests like these?
 » 21 month(s) ago, # |   +2 after seeing the question i jump into this comment section
 » 21 month(s) ago, # |   +4 What was the problem with B?
 » 21 month(s) ago, # |   +73 bad statements, problems are not easy to understand.
 » 21 month(s) ago, # |   +34 why a physics problem? why?
•  » » 21 month(s) ago, # ^ |   +9 why not?
•  » » » 21 month(s) ago, # ^ |   +1 School's tests are enough.
 » 21 month(s) ago, # | ← Rev. 5 →   +3 Is the round unrated or still rated? I saw a few statements correcting problem B some time ago, and I think they might have mentioned something about rated or not/extended time, but I don't exactly remember.
•  » » 21 month(s) ago, # ^ |   +2 Its rated.
 » 21 month(s) ago, # | ← Rev. 2 →   +2 ..
 » 21 month(s) ago, # |   +14 Oh! What a pathetic round it has been for me today! Feeling ashamed :(
 » 21 month(s) ago, # |   +26 I feel like this round is around Div 1.5
•  » » 21 month(s) ago, # ^ |   +13 I feel like this round is around Div 0.5
 » 21 month(s) ago, # |   +22 Very demotivating round for me, couldn't solve problem B(which is solved by almost 4000+ participants) and afterwards (-_-)
•  » » 21 month(s) ago, # ^ |   0 Don't worry 4000 is gonna get a huge drop after the system tests. Lot of masters and GM are also failing system tests for B, this indicates that pretests were very weak.
•  » » 21 month(s) ago, # ^ |   0 Same here couldn't solve B, I was trying very hard but nothing happened, very ashamed.
•  » » » 21 month(s) ago, # ^ |   0 You don't need to be. At max from your side you can improve your practice and learn new concepts. So please focus on learning new concepts and trying to practice as many questions you can and they should be of difficulty greater than your rating + [100, 300]
•  » » » » 21 month(s) ago, # ^ |   +3 Thanks for your kind words, lot of grandmasters also got this wrong, so i should not worry much and practice as you suggested rating + [100,300]
 » 21 month(s) ago, # |   +22 Start with problem B, I spend 10 mins to figure out why the sample is 3 not 2. Nice contest
 » 21 month(s) ago, # |   0 Can ternary search pass pretests on D?
•  » » 21 month(s) ago, # ^ |   +11 WA11 for me :)
•  » » » 21 month(s) ago, # ^ |   0 I got WA 17 :)
•  » » » » 21 month(s) ago, # ^ |   +15 wow, good job!
 » 21 month(s) ago, # |   +114 What's the point of making easy problems this painful to comprehend?
 » 21 month(s) ago, # |   +17 Looks like combined round is here only to kill me. RIP rating once again.
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   +7 Lol you atleast got B, I gave up on that and started doing D. And didn't get it. Now Imma go cry in a corner. Thought I'll become CM today. Predictor says I'm gonna lose 100. F.
•  » » » 21 month(s) ago, # ^ |   0 Bad day for you bro. But this is the story of me in every combined rounds, complicated statement in B, try to understand the statement thus kill your potential, go to C solve it then come back and try more. Finally get B and then rush for D, get idea before just 10 min of end and rage in corner. This is the thing that dropped me from 1800+ where I never managed to reach till now
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 #MeToo
 » 21 month(s) ago, # |   0 How to solve F? Couldn't figure out how to solve for even small n = 7? Great problems and contest. Thanks
•  » » 21 month(s) ago, # ^ |   +5 Very briefly,For components with size 4,2,1, first merge 1 with one of element in 4[4,2,1] ==> [3,2,2]then merge the two 2s
•  » » 21 month(s) ago, # ^ |   +5 Basically you separate into powers of 2 and greedily merge them.So 7 decomposes into [1,2,3,4], [5,6], [7]. It's pretty easy to get all of those to be equal to each other. Now, merge [4,7] to get [1,2,3], [5,6] and [4,7] as your buckets. Then, merge [5,4] adn [6,7], so you have [1,2,3], [4,5,6,7] as your buckets, which is at most 2 distinct elements, as desired.
•  » » 21 month(s) ago, # ^ |   +44 Notice that if n = 2^k, there will always be a way to make n elements be identical. In general case, we can make elements in [1..2^k] identical and do it one more time with [n-2^k+1, n], k is the largest number that 2^k <= n
 » 21 month(s) ago, # |   +73 When you see that there are a lot of hacks for problem B:
 » 21 month(s) ago, # |   0 How to solve F, and how can there be more people solving F than E ?
•  » » 21 month(s) ago, # ^ |   0 As for me, I couldn't understand E within 20 minutes) So I just skipped it.And F is just seems pretty easy to spend more time on it (and to solve it)
•  » » 21 month(s) ago, # ^ |   +42 You can make $2^k$ elements equal in $k 2^k$ operations, by first making the first $2^{k-1}$ elements and last $2^{k-1}$ elements equal, then applying the operation to the first element of both sides, then the second element of both sides, and so on.To have at most two values, just take the largest k such that $2^k \leq n$, and apply the above process to the first $2^k$ and last $2^k$ elements.
•  » » » 21 month(s) ago, # ^ |   0 Oh seriously????? So stupid me.
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 Let's define $p$ as the largest power of $2$ not greater than $n$. Now merge $[1,p]$, and merge $[n-p+1,n]$.
 » 21 month(s) ago, # |   +26 Almost identical version of today's G: https://acm.timus.ru/problem.aspx?space=1&num=1478.
 » 21 month(s) ago, # |   +232 Did nobody test problem B? How is it possible that a problem with wrong tests, even wrong answers to the sample, gets through?? Did every tester somehow understand the problem wrong in the same way? This wasn't the last problem of div 1 either, every tester should have gotten to div2B o.O
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   +46 When I tested the round there was problem C in place of B.It was added after the testers feedback,so testers are not aware of it.
 » 21 month(s) ago, # | ← Rev. 2 →   +3 How to solve D??, ternary search seems not to work here
•  » » 21 month(s) ago, # ^ |   0 greedy solution worked for me
•  » » » 21 month(s) ago, # ^ |   0 Can you elaborate your greedy solution??
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   +1 For each (robber, projector) pair calculate pair (upMoves, rightMoves). Now sort this list n * m pairs and answer is some prefix of robbers moving up and suffix of robbers moving right. This can be calculated with suffix maximums in O(n * m).
 » 21 month(s) ago, # |   -8 In problem D sample input 4, you have to make 5 right moves to save (7,0) robber from (11,5) light and you have to make 2 up moves to hide (3,5) from (6,6), so the minimum answer should be 7, not 6. I have read problem statement multiple times. There will 5 moves when we increase ai of all robbers and 2 moves where we increase bi to same all of them. I can't understand where I am wrong.
•  » » 21 month(s) ago, # ^ |   +8 You can do 5 moves right and 1 move up.
•  » » 21 month(s) ago, # ^ |   0 But you would have already made those 5 moves if you moved 5 times to the right before or even to the left, remember you move all robbers in 1 move.
 » 21 month(s) ago, # |   0 RIP Rating :(
 » 21 month(s) ago, # |   0 It was a tough contest for me
•  » » 21 month(s) ago, # ^ |   0 double time1 = a[i1] — p1 / s1;Just sharing the reason for my hour shock...double time1 = (a[i1] — p1) / s1;Hope you can feel the difference
 » 21 month(s) ago, # | ← Rev. 2 →   0 Why they wrote it's a div 1 + div 2 ? Rip Rating
 » 21 month(s) ago, # |   +1 How to solve C ?
•  » » 21 month(s) ago, # ^ |   0 I did binary Search
•  » » » 21 month(s) ago, # ^ |   0 Can you elaborate.
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 Binary search for each time T and if the position of x > position of y increase T else decrease it..!! ~~~~~ long double lo=0,hi=l,mid; while(hi-lo > eps){ mid= lo + (hi-lo)/2; long double x=diff(mid,l,a); if(x>=0){ lo=mid; } else{ hi=mid; } } Here diff() function tells the difference of positions (x-y)
•  » » » 21 month(s) ago, # ^ |   0 How are you calculating position of x at time T ?
•  » » » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 ld= long double I calculated x and y separately ld diff(ld time,ld l, vi &a){ ld x=0,y=l; int n=a.size(); ld speed=1,ti=0; for(int i=0;i=time){ x=a[i]+speed*(time-ti); break; } ti+=t; speed++; } if(x==0 && time>0) x=l; speed=1; ti=0; for(int i=n-1;i>0;i--){ ld t=(a[i]-a[i-1])/speed; if(ti+t>=time){ y=a[i]-speed*(time-ti); break; } ti+=t; speed++; } if(y==l && time>0) y=0; return y-x; } 
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 I calculated the flags where they will have already crossed each other so I went 1 flag back with the calculated time for each flag. So now you are in position x____y where car is at x and car b is at y at some time tx and ty and you know the speed of each car so you do some basic physics calculations from there.
 » 21 month(s) ago, # | ← Rev. 2 →   +3 How to solve D? Never saw such a hard D RIP rating T_T PS: After watching editorial I felt it wasn't that hard!
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 Hint: calculate a vector {c[i]-a[j],d[i]-b[j]} then sort it.
•  » » » 21 month(s) ago, # ^ |   0 Thanks :)
•  » » 21 month(s) ago, # ^ |   0 In problem D sample input 4, you have to make 5 right moves to save (7,0) robber from (11,5) light and you have to make 2 up moves to hide (3,5) from (6,6), so the minimum answer should be 7, not 6. I have read problem statement multiple times. There will 5 moves when we increase ai of all robbers and 2 moves where we increase bi to same all of them. I can't understand where I am wrong.
•  » » » 21 month(s) ago, # ^ |   0 i am sure that is a better solution. Do a backtracking if you can't find it on the paper
•  » » » 21 month(s) ago, # ^ |   0 The answer is 6 because we can move 5 times toward right and 1 up move.
•  » » 21 month(s) ago, # ^ |   0 wanna see a hard D...
 » 21 month(s) ago, # |   +4 Combined round==RIP Rating
•  » » 21 month(s) ago, # ^ |   0 true
 » 21 month(s) ago, # |   +37 Problem E is perfect!To work out it need some inspirations.I love this prolbem :)
 » 21 month(s) ago, # |   +1 how to solve C?
•  » » 21 month(s) ago, # ^ |   0 Binary search across time and calculate position for each car, stop when the difference in position is within 1e-6
•  » » 21 month(s) ago, # ^ |   0 Let's say initial positions are 0 and L. Now, assume that the first car will reach the flag closest to it before car 2 reaches the flag closest to it (car 2). So, calculate that time and add it to answer. Also, update the positions of both the cars accordingly, by p1 += time * v1 and p2 -= time * v2 (note time will be same).Do this till you see that there are no flags between them. Then say x is the position where they meet. Solve (x — p1) / v1 = (p2 — x) / v2 (this says that they travel for same time), which gives x = (p2 — p1) / (v1 + v2). Now calculate time and add it to answer.
 » 21 month(s) ago, # |   +8 I can already see solutions of problem B getting WA in system tests :(
 » 21 month(s) ago, # |   +4 Interesting problems, but am I the only one who got really slowed down by Physicsforces C?
•  » » 21 month(s) ago, # ^ |   0 More like arrayforces in A and B
 » 21 month(s) ago, # |   0 what was a 15 test for D?
 » 21 month(s) ago, # |   +9 Can some one tell me what is procedure to solve B & Ci tried for 2hour but i can't find out the solution
•  » » 21 month(s) ago, # ^ |   0 For C, you can do a binary search on time required for both to meet.
•  » » » 21 month(s) ago, # ^ |   0 Can you elaborate The process pleasei Was try but can't find the process
•  » » » » 21 month(s) ago, # ^ |   0 Binary search on the time, and for a given time $T$, you can simulate both cars to see where they end up after time $T$.Iterate over differences between adjacent $a_i$. For the car starting on the left, it has a speed of $i$ when moving from $a_i$ to $a_{i+1}$ (one-indexing), so the amount of time it takes to get through is distance divided by speed, or $(a_{i+1} - a_i) / i$, and you subtract off those time amounts when moving from left to right. The case for the right car is mirrored. At the end, check if the position of the left car is to the right of the right car, since that means the two collided.
 » 21 month(s) ago, # | ← Rev. 3 →   +11 The feeling when you miss submitting a solution by 10 seconds. Arghhh!!Edit: segmentation fault on pretest itself ;_;
•  » » 21 month(s) ago, # ^ | ← Rev. 3 →   +26 Same. Didn't initialize variables in G submitted at 2.48, got wa on pretest 1, fixed and contest over in selecting file to upload. ;_;Edit: AC in practice but after fixing a bug. ;_;
•  » » » 21 month(s) ago, # ^ |   +2 Same. Saved my JavaScript code for A in .java file instead of .js, fixed and contest over in selecting file to upload. ;_;
 » 21 month(s) ago, # |   +3 how to solve problem D?
 » 21 month(s) ago, # |   +1 is submitted code visible for everyone ?
 » 21 month(s) ago, # |   +12 Why submissions are not visible yet?
 » 21 month(s) ago, # |   -175 Problems are of very bad quality!!!Don't like even single problem. Total wastage of time :)You guys should have select problem set according to level of participants. Very disappointed and demotivated after this round. Sorry to say, but it makes no sense to solve such problems.
•  » » 21 month(s) ago, # ^ |   +22 Actually E and F (and maybe above) are insanely good. Just poor preparation for cakewalk problems.
 » 21 month(s) ago, # |   +8 what is the author's solution of B?
 » 21 month(s) ago, # |   +30 What is test 9 in B?!
•  » » 21 month(s) ago, # ^ |   0 Why nobody hacks my B?
•  » » » 21 month(s) ago, # ^ |   0 bcuz chinese got 1000iq
•  » » 21 month(s) ago, # ^ |   0 Something like this 1 5 2 1 1 1 1 1 
 » 21 month(s) ago, # |   0 Is D concluding to range minimum query for all 2000 robbers after some processing of coordinates.. sorted along their x axis same as per lights
 » 21 month(s) ago, # |   0 why other solutions are not available?
 » 21 month(s) ago, # |   +9 I wonder why so much solutions failed on B. I even see grand-masters failing system tests
 » 21 month(s) ago, # |   +4 Gimmmee Editorial Fastttttttttttttt.........
 » 21 month(s) ago, # |   0 What's the idea behind D? I could only think of iterating on the shifts of the X-coordinate and find the minimum Y-coordinate shift needed for each new position. Too slow.
•  » » 21 month(s) ago, # ^ |   0 Hint: calculate a vector {c[i]-a[j],d[i]-b[j]} then sort it.
 » 21 month(s) ago, # |   0 Most of RED coders got system test failed in B and I thought I could be able to solve B :p
 » 21 month(s) ago, # |   0 Can someone give me a hint for problem E?
•  » » 21 month(s) ago, # ^ |   +8 Think of a graph where you have one node per each set and one node per each number occuring.
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   -22 HintMaximum Spanning Tree SolutionCreate m + n vertices and connect i + n and x with cost a[i] + b[x]. Answer is total cost of edges — mst cost.
 » 21 month(s) ago, # |   0 For me, F was easier than D (although last minute submission and still praying). I am still unable to figure out D.
 » 21 month(s) ago, # |   +57 Problem F was so nice!
 » 21 month(s) ago, # |   +10 Anyone solved C with just physics without binary search, or just me?
•  » » 21 month(s) ago, # ^ |   0 Can you explain your solution?
•  » » » 21 month(s) ago, # ^ | ← Rev. 4 →   0 If 2 persons intersect in time t then they will surely intersect in ti,e t +alpha alpha be 0.0000001 also. this was the core concept. now given a time we need to find that these cars will intersect or not. and thus calculate over our binary search.Submission link : 94326719
•  » » » » 21 month(s) ago, # ^ |   0 I got C by binary search. I am interesting in solution with just physics.
•  » » » 21 month(s) ago, # ^ | ← Rev. 4 →   +18 I stored the time both person takes to reach each of the obstacles, in 2 arrays t1 and t2. Iterating through t1, if at any point t1[i]>t2[i] this means that the collision happened between a[i-1] and a[i]. (a is obstacle position array)Now with some maths I find position of 2 when 1 is at a[i-1]. At this point its a well known physics problem. "2 points moving at constant speed in opposite direction, find the time taken for them to collide".Since the time taken to collide for both is same it can be solved by the equation x/s1 = (d-x)/s2 where d is the distance between them and s1 and s2 are their speeds and x is the distance from a[i-1] to collision point. Simplifying it would be d/(s1+s2).
•  » » » » 21 month(s) ago, # ^ |   +3 Thanks a lot for explanation.
•  » » 21 month(s) ago, # ^ |   +4 I solved with just physics
•  » » 21 month(s) ago, # ^ |   +6 By just physics you mean relative velocity?
•  » » » 21 month(s) ago, # ^ |   +1 No by making array of time required to reach each mark from left and right and then checking every adjacent marks if they can meet between them.
•  » » 21 month(s) ago, # ^ |   +1 I got the equation, but decided writing BS is easier than solving the equation :P
•  » » 21 month(s) ago, # ^ | ← Rev. 3 →   -28 i solved by just physics..but final testing pending yet...update: my code fail in final test(WA test-9)
•  » » 21 month(s) ago, # ^ |   0 Yes , i solved it iterating over segment using concept of relative motion . I think majority of people will solve it using physics. It was obvious.
•  » » 21 month(s) ago, # ^ |   0 yep I did. Simple speed = distance / time and 2 pointers
 » 21 month(s) ago, # |   +1 How to solve B?
 » 21 month(s) ago, # |   +24 There is one thing I'm not very clear about in problem B: is it maximum k different numbers across all the arrays, or maximum k different numbers in each array? The way the statement is phrased makes both seem plausible, but I guessed it was the latter.And if it was the former, why does the latter pass pretests :(
•  » » 21 month(s) ago, # ^ |   0 I took K as the maximum in each array and then solved it.
•  » » 21 month(s) ago, # ^ |   +11 I think it's clear from the statement it's for each array. The number of different elements in the array Bi is at most k
•  » » » 21 month(s) ago, # ^ |   0 Ah I see. I was very confused by the sample explanation for test case 4 (which seems to have been later removed), which appears to suggest that it was for all.
 » 21 month(s) ago, # |   -15 Give me some hint for problem B
•  » » 21 month(s) ago, # ^ |   +14 Hint 1Count the number of distinct elements in $a$. Hint 2if the number of distinct elements is less than $k$ then the answer is $1$ . Hint 3if $k = 1$ and number of distinct elements is greater than $1$ then the answer is $-1$. Hint 4Now you need to distribute the distinct elements to $m$ arrays each having at most $k$ elements. Find that $m$. With just a little of paperwork, you will get the answer.
 » 21 month(s) ago, # | ← Rev. 2 →   -6 .
 » 21 month(s) ago, # |   0 And tourist won again.Not sure why but it was fun to check standings (top 20 positions) throughout the contest.
•  » » 21 month(s) ago, # ^ |   0 I sould have done the same, I would have alteast saved my rating
•  » » » 21 month(s) ago, # ^ |   0 Congrats on creating new absolute rating change records!
 » 21 month(s) ago, # |   +10 DSU without path compression or rank heuristics passes in G, lol.
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 Isn't complexity O(N^2logN) both with or without heuristics?Edit: my bad it may blow upto N^3
•  » » » 21 month(s) ago, # ^ |   +3 My function that returns root of the subtree works in $O(depth(v))$, so no.
 » 21 month(s) ago, # | ← Rev. 3 →   +14 Today's problem B has been really confusing!
 » 21 month(s) ago, # |   -9 Confusing problem statements + wrong samples + weak pretests + poor problem quality, I expected a better round :(
 » 21 month(s) ago, # |   +97 Me be like : shit why did I even submit B
•  » » 21 month(s) ago, # ^ |   +5 I would like to ask how can we see the rating change before it gets updated ? Are there any settings for that because I can only see columns upto last question only . There is not rating change column in it . Can anyone tell me why ?
•  » » » 21 month(s) ago, # ^ |   +5 Its actually a google chrome plugin of CF Predictor. Link: Plugin
•  » » » » 21 month(s) ago, # ^ |   0 That's really cool and I didn't knew about it . Thanks mate.
 » 21 month(s) ago, # | ← Rev. 3 →   +1 In the end, I still failed to pass d. I thought of the correct algorithm, but I still couldn't finish it. . I often can't finish writing D. Even if I can pass it, it is at the last moment of the game. How can I change this situation?（Great game, thanks to 300iq and isaf27）upd:Although I didn't play well, I turned blue and I was very happy. If there are more kind people to answer my question, it would be even better. Thank you in advance.
 » 21 month(s) ago, # |   0 Great contest from upsolving point of view XD.
 » 21 month(s) ago, # |   +61
 » 21 month(s) ago, # | ← Rev. 2 →   -43 Now i understand why people edit comment and put a dot ;)
•  » » 21 month(s) ago, # ^ |   -17 damn that's crazy bro... Spoilerbut did I ask?
•  » » » 21 month(s) ago, # ^ | ← Rev. 3 →   -29 (2)
 » 21 month(s) ago, # | ← Rev. 2 →   +4 Stupid mistake in B ruined everythingDon't wanna go back to cyan
•  » » 21 month(s) ago, # ^ |   0 I have followed you. Judging from the prediction of cf predictor, this is impossible. But you may lose 80 points rating, good luck next time.
 » 21 month(s) ago, # |   +1 Huge thanks for the round! It was super fun to solve first problems :)
 » 21 month(s) ago, # |   +27 isaf27 Just curious to know, how come incorrect sample test case for B was not figured out by any tester before contest?
•  » » 21 month(s) ago, # ^ |   +12 Initially, we didn't have this problem and added it closer to the round to make the problem's difficulties more balanced.
•  » » » 21 month(s) ago, # ^ |   +4 I see, but thanks for the round. Most of the problems were really different from the kind of problems we see in normal codeforces round.
•  » » » 21 month(s) ago, # ^ |   +18 Were the author's solution & all testers' solutions wrong? How did anyone pass pretests?
•  » » » 21 month(s) ago, # ^ |   +8 You wrote a sample explanation wrong! How is that possible? Did you generate it somehow? I don't see any way to mess it up unless you were braindead.
•  » » » » 21 month(s) ago, # ^ |   -41 Just wrote a sample explanation for answer $3$ quickly, because I've seen, that the answer to this test case is 3 (from the wrong main solution).I didn't think: "hm, maybe it is possible to do it with 2 arrays", but I definitely should have done that.
•  » » » » » 21 month(s) ago, # ^ |   +60 The sample explanation didn't even add up correctly. It was possible to do in 2 arrays, as you said, but the 3 arrays in the sample added up to [1, 2, 3, 4, 4] instead of [1, 2, 3, 4, 5].
•  » » » » » » 21 month(s) ago, # ^ |   +29 Brute force#include using namespace std; void gen(vector > & ans, vector curr, int n, int k, vector &bou) { if ((int)curr.size() == n) { ans.push_back(move(curr)); return; } int low = curr.empty() ? 0 : curr.back(); for (int x = low; x <= bou[curr.size()]; ++x) { bool is_new = curr.empty() || x != curr.back(); if (k || !is_new) { curr.push_back(x); gen(ans, curr, n, k - is_new, bou); curr.pop_back(); } } } void solve() { int n, k; scanf("%d%d", &n, &k); vector a(n); for (int &x : a) scanf("%d", &x); vector > possible; gen(possible, {}, n, k, a); map , int> dist; dist[vector(n, 0)] = 0; queue> kol; kol.push(vector(n, 0)); while (!kol.empty()) { vector here = kol.front(); int d = dist[here]; kol.pop(); for (vector &x : possible) { vector to = here; for (int i = 0; i < n; ++i) to[i] += x[i]; if (to == a) { printf("%d\n", d + 1); return; } bool valid = true; for (int i = 0; i < n; ++i) if (to[i] > a[i]) valid = false; if (valid) { auto [it, added] = dist.insert(make_pair(to, d + 1)); if (added) kol.push(to); } } } printf("-1\n"); } int main() { int t; scanf("%d", &t); while (t--) solve(); } I took me 8 minutes and 19.5 seconds to implement it and it runs on sample with in a few seconds and points out the answer is wrong. That's what you should have done, and not think: "hm, maybe it is possible to do it with 2 arrays"
 » 21 month(s) ago, # |   +7 Can someone explain problem D in simpler terms , i couldn't understand from editorial .
 » 21 month(s) ago, # | ← Rev. 3 →   -16 .
•  » » 21 month(s) ago, # ^ |   +8 b must be non-decreasing
•  » » » 21 month(s) ago, # ^ |   0 Ohhh, Got it. Thanks
•  » » 21 month(s) ago, # ^ |   -14 Above answer is incorrect, it is mentioned B should be non-decreasing. Is B1 non decreasing in your above solution? And correct answer should be 8.
•  » » » 21 month(s) ago, # ^ |   0 Problem B was same as your cf dp. LOL
 » 21 month(s) ago, # |   +23 Quite late, but here's my fun screencast with commentaries + solutions + playing chesss during contest :)
•  » » 21 month(s) ago, # ^ |   +46 Why did you play chess in the middle of a contest?
•  » » » 21 month(s) ago, # ^ | ← Rev. 2 →   +21 At that time felt very overwhelmed, so with Chess wanted kinda to refresh my brain :D
•  » » » » 21 month(s) ago, # ^ |   +35 Wow. You spent around 40 minutes during the contest playing chess and still got positive rating difference. Congrats.
•  » » » 21 month(s) ago, # ^ |   +121 You truly are an enigma. First you complain about too many easy problems being an advantage to you, and now you complain that your competitors don't try their best? Next will you complain that someone handed you free money?
 » 21 month(s) ago, # |   +21 Vovuh looking lonely in the Top Contributors :(
 » 21 month(s) ago, # |   +6 The system test is a little bit weak. I hacked myself in D after the contest.
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   +3 My solution is $O(nm\log n)$ with huge constant factors (because I used unnecesary multisets).The reason I passed D in contest may be the small optimization: If two robbers' position $(a,b),(c,d)$ satisfy $a\le c,b\le d$ then $(c,d)$ surely won't effect the answer. For the searchlights if two $(a,b),(c,d)$ satisfy $a\le c,b\le d$ then $(a,b)$ can be deleted. After the deleting, the real number of $n$ and $m$ become so small that I passed in only 60ms. (fixed a typo)
•  » » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 Can you hack me too? Thanks.Edit: I used the generator from your blog post and it didn't hack my solution (https://codeforces.com/contest/1408/hacks/669242). I was surprised because I also used a similar heuristic as you (though I applied it to the pair differences).
 » 21 month(s) ago, # |   -48 I hate problems
 » 21 month(s) ago, # |   -12 How did you solve problem C — O(n*logn) or O(n)?
•  » » 21 month(s) ago, # ^ |   0 My solution was O(n), got it accepted at the last minute after 2 WA's, it was super intense
•  » » 21 month(s) ago, # ^ |   0 O(n) using two pointers
•  » » 21 month(s) ago, # ^ |   0 It is obviously that two cars meet the other between two flags(or flag and end point). Therefore, you can store the time reach to each flag of each car. Then find the suitable range where two cars will meet by considering each point.
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   -8 binary search! O(nlogn)
 » 21 month(s) ago, # |   +1 Wow, maroonrk, ksun48, ainta, Egor all reached their highest Max Rating in this contest!Congrats and orz
 » 21 month(s) ago, # |   0 I have solved 1 question in this contest but there is a message showing that my solution coincided with another solution. It is a mere coincidence that our solution are alike as I don't know anything about the other person. I have not used any online source for solution it was an original solution. Can any one help how i can proof the same?
 » 21 month(s) ago, # |   0 Why my solution of A is incorrect?First, $p_1 = a_1$$i \in { 2 \sim n }$if $p_{i-1} \ne a_i ,p_i = a_i$if $p_{i-1} \ne b_i ,p_i = b_i$if $p_{i-1} \ne c_i ,p_i = c_i$where is wrong?
•  » » 21 month(s) ago, # ^ |   +1 you could end up having $p_n = p_1$
•  » » 21 month(s) ago, # ^ |   0 fix the positions where u cant change anything like ai = 2, bi = 2, ci = 2 ! u must take 2 in this case! this may help!
 » 21 month(s) ago, # |   +12 Why is the rating change after this contest suddenly reverted? Did the contest become unrated all on a sudden? Did this happen with others too?
•  » » 21 month(s) ago, # ^ |   0 Me too.
•  » » 21 month(s) ago, # ^ |   +1 There is no confirmation of round being unrated. So i think ratings will be back after some time.
•  » » » 21 month(s) ago, # ^ |   +1 I hope so. I got a +100 in it! XD
•  » » » » 21 month(s) ago, # ^ |   0 Kudos! Mate
 » 21 month(s) ago, # | ← Rev. 2 →   +9 I am new to codeforces. I participated in this contest, solved one problem and my rating had increasd by about 400 pts. But now, my profile shows unrated again. what could be the possible reasons??[contest:1408][problem:1408A][submission:94311182]
•  » » 21 month(s) ago, # ^ |   +7 The ratings changes of the last round is reverted for everyone because either the authority has not finished catching cheaters or there are some serious issues. isaf27 is the writer of the contest. The writer is not responsible for ratings update or rollback. Headquarter is responsible for this. You can ask Mike. He can give us updated information.
•  » » » 21 month(s) ago, # ^ |   +1 i dont think asking mike is a good idea! like asking help from zuckerburg in getting fb id hacked!
•  » » » » 21 month(s) ago, # ^ |   +5 It won't be a good idea if it was unethical like hacking. But I think a contestant has some minimum right to know why ratings update was rolled back and why wasn’t returned in a rated contest.
•  » » 21 month(s) ago, # ^ |   0 Ratings changes is back.
 » 21 month(s) ago, # |   +1 it was hard contest
 » 21 month(s) ago, # | ← Rev. 2 →   -10 deleted
 » 20 months ago, # |   +1 I want to work in Grakn Labs.
 » 20 months ago, # |   0 Orz QAQAutoMaton