When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

By isaf27, history, 3 years ago, In English

Hello, Codeforces!

grakn

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 coderz189, 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

Additional Prizes:

Top 50 receive:

Grakn Labs swag pack:

  • Stickers
  • Grakn Labs t-shirt

Random 50 from 51-250 receive:

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:

  1. tourist
  2. Benq
  3. maroonrk
  4. Egor
  5. ecnerwala
Announcement of Grakn Forces 2020
  • Vote: I like it
  • +506
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it +657 Vote: I do not like it

As a tester, I want contribution

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +239 Vote: I do not like it

    ok

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +142 Vote: I do not like it

    Let me try my luck as well

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +47 Vote: I do not like it

    You deserve it. <3

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    why not

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +72 Vote: I do not like it

    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..

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +86 Vote: I do not like it

      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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    This is an OP way to get contribution.

»
3 years ago, # |
Rev. 4   Vote: I like it +22 Vote: I do not like it

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

RIPRating

»
3 years ago, # |
Rev. 2   Vote: I like it -36 Vote: I do not like it

.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

    No.. Just like other global rounds.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +127 Vote: I do not like it

    The only ones that possibly lose something more in combined rounds are div1 people that get beat by div2.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Let's not think about rating but exprience and learning something

»
3 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Will this contest be similar to global rounds?

»
3 years ago, # |
  Vote: I like it -48 Vote: I do not like it

Whoa! AyanoGod you wanted contribution and you got it! (although it is negative) xD xD xD. And now you have edited the comment hahaha

»
3 years ago, # |
  Vote: I like it -15 Vote: I do not like it

Dragnoid99 Nice to see your name in the contributor's list!!

»
3 years ago, # |
  Vote: I like it +66 Vote: I do not like it

isaf is the trusted author !!! :hug:

»
3 years ago, # |
  Vote: I like it -29 Vote: I do not like it

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.

»
3 years ago, # |
  Vote: I like it +267 Vote: I do not like it

Me after seeing 300iq is a problem setter.

Wrong answer on test case 256.

»
3 years ago, # |
  Vote: I like it +411 Vote: I do not like it

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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    we missed "that's stupid!" in your comment! that's rare! :v

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +43 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +62 Vote: I do not like it

      isn't that the point? favours people who can actually do A and B in 1 minute each

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it -95 Vote: I do not like it

        A and B in combined normally aren't the type of problems you EVER get stuck, so no.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
          Rev. 2   Vote: I like it +17 Vote: I do not like it

          i just did it.

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it -22 Vote: I do not like it

            I mean I did that too, still I believe my point is valid for high rated users.

            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
                Vote: I like it +24 Vote: I do not like it

              soo 2800 is not high enough?

              • »
                »
                »
                »
                »
                »
                »
                »
                3 years ago, # ^ |
                  Vote: I like it -17 Vote: I do not like it

                Have you heard about rating inflation? I'm an example of it.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +133 Vote: I do not like it

      'A and B are just one minute tasks'. This didn't age well

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 2   Vote: I like it +2 Vote: I do not like it

        I was in even more panic while solving B since I had read this statement lol

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      A,B just one minute task ! i see... Screenshot-78.png

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'm curious to know how do you approach the situation when you are stuck on a hard problem. Thanks!

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +35 Vote: I do not like it

    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?

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +26 Vote: I do not like it

      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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it -26 Vote: I do not like it

    I guess this contest favoured you a lot. Lol

»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

i wish this contest will be a good contest :3

»
3 years ago, # |
Rev. 2   Vote: I like it +26 Vote: I do not like it

Not any more.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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.

»
3 years ago, # |
  Vote: I like it +67 Vote: I do not like it

As a tester, I wish you all the best of luck :)

»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Thanks for bringing Grakn forces contest into codeforces to us! ^_^

»
3 years ago, # |
  Vote: I like it +50 Vote: I do not like it

As a tester, give me contribution.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

this post is what I wish the other post was (https://codeforces.com/blog/entry/82787?#comment-704138)

»
3 years ago, # |
  Vote: I like it -35 Vote: I do not like it

as someone who didn't do anything, i want contribution

»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Please note the usual timings of the contest :D

»
3 years ago, # |
  Vote: I like it -20 Vote: I do not like it

Is it rated for div3 people?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

2h 30min lol

»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

What will be the difficulty level of A & B problem?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    500 and 1000 respectively, the post is updated with the score distribution now.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      emmm. it is scores, not difficulty

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        Oh yeah that's true but it's a rough estimation of a problem difficulty as well isn't it

»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

12 more minutes remaining. Wish you all a very good luck!

»
3 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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 contest

regard.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    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

»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Let's hope that there isn't any extreme jump in difficulty lvl...

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why does more companies don't host contests like these?

»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

after seeing the question i jump into this comment section

»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

What was the problem with B?

»
3 years ago, # |
  Vote: I like it +73 Vote: I do not like it

bad statements, problems are not easy to understand.

»
3 years ago, # |
  Vote: I like it +34 Vote: I do not like it

why a physics problem? why?

»
3 years ago, # |
Rev. 5   Vote: I like it +3 Vote: I do not like it

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.

»
3 years ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

..

»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Oh! What a pathetic round it has been for me today! Feeling ashamed :(

»
3 years ago, # |
  Vote: I like it +26 Vote: I do not like it

I feel like this round is around Div 1.5

»
3 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Very demotivating round for me, couldn't solve problem B(which is solved by almost 4000+ participants) and afterwards (-_-)

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same here couldn't solve B, I was trying very hard but nothing happened, very ashamed.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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]

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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]

»
3 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Start with problem B, I spend 10 mins to figure out why the sample is 3 not 2. Nice contest

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can ternary search pass pretests on D?

»
3 years ago, # |
  Vote: I like it +114 Vote: I do not like it

What's the point of making easy problems this painful to comprehend?

»
3 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Looks like combined round is here only to kill me. RIP rating once again.

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +7 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    #MeToo

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F? Couldn't figure out how to solve for even small n = 7? Great problems and contest. Thanks

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +44 Vote: I do not like it

    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

»
3 years ago, # |
  Vote: I like it +73 Vote: I do not like it

When you see that there are a lot of hacks for problem B:

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F, and how can there be more people solving F than E ?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +42 Vote: I do not like it

    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.

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Let's define $$$p$$$ as the largest power of $$$2$$$ not greater than $$$n$$$. Now merge $$$[1,p]$$$, and merge $$$[n-p+1,n]$$$.

»
3 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Almost identical version of today's G: https://acm.timus.ru/problem.aspx?space=1&num=1478.

»
3 years ago, # |
  Vote: I like it +232 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +46 Vote: I do not like it

    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.

»
3 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

How to solve D??, ternary search seems not to work here

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    greedy solution worked for me

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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).

»
3 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

RIP Rating :(

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Why they wrote it's a div 1 + div 2 ?

Rip Rating

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve C ?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did binary Search

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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)

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How are you calculating position of x at time T ?

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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<n-1;i++){
        		ld t=(a[i+1]-a[i])/speed;
        		if(ti+t>=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;
        }
        
»
3 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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!

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Hint: calculate a vector {c[i]-a[j],d[i]-b[j]} then sort it.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i am sure that is a better solution. Do a backtracking if you can't find it on the paper

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The answer is 6 because we can move 5 times toward right and 1 up move.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    wanna see a hard D...

»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Combined round==RIP Rating

»
3 years ago, # |
  Vote: I like it +37 Vote: I do not like it

Problem E is perfect!To work out it need some inspirations.I love this prolbem :)

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

how to solve C?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Binary search across time and calculate position for each car, stop when the difference in position is within 1e-6

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I can already see solutions of problem B getting WA in system tests :(

»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Interesting problems, but am I the only one who got really slowed down by Physicsforces C?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    More like arrayforces in A and B

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what was a 15 test for D?

»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Can some one tell me what is procedure to solve B & C

i tried for 2hour but i can't find out the solution

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For C, you can do a binary search on time required for both to meet.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you elaborate The process please

      i Was try but can't find the process

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        Submission: https://codeforces.com/contest/1408/submission/94351795

»
3 years ago, # |
Rev. 3   Vote: I like it +11 Vote: I do not like it

The feeling when you miss submitting a solution by 10 seconds. Arghhh!!

Edit: segmentation fault on pretest itself ;_;

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it +26 Vote: I do not like it

    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. ;_;

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      Same. Saved my JavaScript code for A in .java file instead of .js, fixed and contest over in selecting file to upload. ;_;

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

how to solve problem D?

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

is submitted code visible for everyone ?

»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Why submissions are not visible yet?

»
3 years ago, # |
  Vote: I like it -175 Vote: I do not like it

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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    Actually E and F (and maybe above) are insanely good. Just poor preparation for cakewalk problems.

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

what is the author's solution of B?

»
3 years ago, # |
  Vote: I like it +30 Vote: I do not like it

What is test 9 in B?!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why other solutions are not available?

»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

I wonder why so much solutions failed on B. I even see grand-masters failing system tests

»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Gimmmee Editorial Fastttttttttttttt.........

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hint: calculate a vector {c[i]-a[j],d[i]-b[j]} then sort it.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone give me a hint for problem E?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Think of a graph where you have one node per each set and one node per each number occuring.

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it -22 Vote: I do not like it
    Hint
    Solution
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For me, F was easier than D (although last minute submission and still praying). I am still unable to figure out D.

»
3 years ago, # |
  Vote: I like it +57 Vote: I do not like it

Problem F was so nice!

»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Anyone solved C with just physics without binary search, or just me?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain your solution?

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 4   Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I got C by binary search. I am interesting in solution with just physics.

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 4   Vote: I like it +18 Vote: I do not like it

      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).

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    I solved with just physics

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    By just physics you mean relative velocity?

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I got the equation, but decided writing BS is easier than solving the equation :P

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it -28 Vote: I do not like it

    i solved by just physics..

    but final testing pending yet...

    update: my code fail in final test(WA test-9)

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yep I did. Simple speed = distance / time and 2 pointers

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve B?

»
3 years ago, # |
  Vote: I like it +24 Vote: I do not like it

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 :(

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I took K as the maximum in each array and then solved it.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
3 years ago, # |
  Vote: I like it -15 Vote: I do not like it

Give me some hint for problem B

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it
    Hint 1
    Hint 2
    Hint 3
    Hint 4
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

And tourist won again.

Not sure why but it was fun to check standings (top 20 positions) throughout the contest.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I sould have done the same, I would have alteast saved my rating

»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

DSU without path compression or rank heuristics passes in G, lol.

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Isn't complexity O(N^2logN) both with or without heuristics?
    Edit: my bad it may blow upto N^3

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      My function that returns root of the subtree works in $$$O(depth(v))$$$, so no.

»
3 years ago, # |
Rev. 3   Vote: I like it +14 Vote: I do not like it

Today's problem B has been really confusing!

»
3 years ago, # |
  Vote: I like it -9 Vote: I do not like it

Confusing problem statements + wrong samples + weak pretests + poor problem quality, I expected a better round :(

»
3 years ago, # |
  Vote: I like it +97 Vote: I do not like it

1 Me be like : shit why did I even submit B

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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 ?

»
3 years ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

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.

»
3 years ago, # |
  Vote: I like it +61 Vote: I do not like it

»
3 years ago, # |
Rev. 2   Vote: I like it -43 Vote: I do not like it

Now i understand why people edit comment and put a dot ;)

»
3 years ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

Stupid mistake in B ruined everything
Don't wanna go back to cyan

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Huge thanks for the round! It was super fun to solve first problems :)

»
3 years ago, # |
  Vote: I like it +27 Vote: I do not like it

isaf27 Just curious to know, how come incorrect sample test case for B was not figured out by any tester before contest?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Initially, we didn't have this problem and added it closer to the round to make the problem's difficulties more balanced.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      Were the author's solution & all testers' solutions wrong? How did anyone pass pretests?

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it -41 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +60 Vote: I do not like it

          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].

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it +29 Vote: I do not like it
            Brute force

            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"

»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Can someone explain problem D in simpler terms , i couldn't understand from editorial .

»
3 years ago, # |
Rev. 3   Vote: I like it -16 Vote: I do not like it

.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    b must be non-decreasing

  • »
    »
    3 years ago, # ^ |
      Vote: I like it -14 Vote: I do not like it

    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.

»
3 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Quite late, but here's my fun screencast with commentaries + solutions + playing chesss during contest :)

Link.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +46 Vote: I do not like it

    Why did you play chess in the middle of a contest?

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it +21 Vote: I do not like it

      At that time felt very overwhelmed, so with Chess wanted kinda to refresh my brain :D

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +35 Vote: I do not like it

        Wow. You spent around 40 minutes during the contest playing chess and still got positive rating difference. Congrats.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +121 Vote: I do not like it

      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?

»
3 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Vovuh looking lonely in the Top Contributors :(

»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

The system test is a little bit weak. I hacked myself in D after the contest.

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    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)

»
3 years ago, # |
  Vote: I like it -48 Vote: I do not like it

I hate problems

»
3 years ago, # |
  Vote: I like it -12 Vote: I do not like it

How did you solve problem C — O(n*logn) or O(n)?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My solution was O(n), got it accepted at the last minute after 2 WA's, it was super intense

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    O(n) using two pointers

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it -8 Vote: I do not like it

    binary search! O(nlogn)

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Wow, maroonrk, ksun48, ainta, Egor all reached their highest Max Rating in this contest!

Congrats and orz

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    you could end up having $$$p_n = p_1$$$

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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!

»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Me too.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    There is no confirmation of round being unrated. So i think ratings will be back after some time.

»
3 years ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

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]

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      i dont think asking mike is a good idea! like asking help from zuckerburg in getting fb id hacked!

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ratings changes is back.

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

it was hard contest

»
3 years ago, # |
Rev. 2   Vote: I like it -10 Vote: I do not like it

deleted

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I want to work in Grakn Labs.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it