By isaf27, history, 8 months 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 growup974, _cherry_, QAQAutoMaton, Prakash11, morzer, qlf9, gege, 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

»
8 months ago, # |
  Vote: I like it +657 Vote: I do not like it

As a tester, I want contribution

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

    ok

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

    Let me try my luck as well

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

    You deserve it. <3

  • »
    »
    8 months ago, # ^ |
      Vote: I like it -66 Vote: I do not like it

    ok

  • »
    »
    8 months ago, # ^ |
      Vote: I like it -36 Vote: I do not like it

    Really,u deserve it!!

  • »
    »
    8 months ago, # ^ |
      Vote: I like it -99 Vote: I do not like it

    As a tester, I want contribution too :)

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

    why not

  • »
    »
    8 months 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..

    • »
      »
      »
      8 months 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

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

    This is an OP way to get contribution.

»
8 months 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

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

.

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

    No.. Just like other global rounds.

  • »
    »
    8 months 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.

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

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

»
8 months ago, # |
  Vote: I like it +15 Vote: I do not like it

Will this contest be similar to global rounds?

»
8 months ago, # |
  Vote: I like it -48 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it -15 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it +66 Vote: I do not like it

isaf is the trusted author !!! :hug:

»
8 months 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.

»
8 months 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.

»
8 months 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.

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

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

  • »
    »
    8 months 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.

    • »
      »
      »
      8 months 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

      • »
        »
        »
        »
        8 months 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.

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

          i just did it.

          • »
            »
            »
            »
            »
            »
            8 months 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.

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

              soo 2800 is not high enough?

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

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

    • »
      »
      »
      8 months 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

      • »
        »
        »
        »
        8 months 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

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    8 months 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!

  • »
    »
    8 months 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?

    • »
      »
      »
      8 months 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.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    tourist solved all of it

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

    I guess this contest favoured you a lot. Lol

»
8 months ago, # |
  Vote: I like it +2 Vote: I do not like it

i wish this contest will be a good contest :3

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

Not any more.

»
8 months 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.

  • »
    »
    8 months 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

  • »
    »
    8 months 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.

»
8 months ago, # |
  Vote: I like it +67 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it +9 Vote: I do not like it

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

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

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!

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

300iq orz

»
8 months ago, # |
  Vote: I like it +50 Vote: I do not like it

As a tester, give me contribution.

»
8 months 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)

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
8 months ago, # |
  Vote: I like it -35 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Please note the usual timings of the contest :D

»
8 months ago, # |
Rev. 2   Vote: I like it -13 Vote: I do not like it
»
8 months ago, # |
  Vote: I like it -20 Vote: I do not like it

Is it rated for div3 people?

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Will problems only in English or both languages are welcome?

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

2h 30min lol

»
8 months ago, # |
  Vote: I like it -34 Vote: I do not like it

hello. i am dmitry and i am tester. give me contribution. i like sausages.

»
8 months ago, # |
  Vote: I like it +4 Vote: I do not like it

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

  • »
    »
    8 months 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.

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

      emmm. it is scores, not difficulty

      • »
        »
        »
        »
        8 months 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

»
8 months ago, # |
  Vote: I like it +16 Vote: I do not like it

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

»
8 months 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.

  • »
    »
    8 months 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

»
8 months 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...

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it +2 Vote: I do not like it

after seeing the question i jump into this comment section

»
8 months ago, # |
  Vote: I like it +4 Vote: I do not like it

What was the problem with B?

»
8 months ago, # |
  Vote: I like it +73 Vote: I do not like it

bad statements, problems are not easy to understand.

»
8 months ago, # |
  Vote: I like it +34 Vote: I do not like it

why a physics problem? why?

»
8 months 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.

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

..

»
8 months 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 :(

»
8 months ago, # |
  Vote: I like it +26 Vote: I do not like it

I feel like this round is around Div 1.5

»
8 months 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 (-_-)

  • »
    »
    8 months 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.

  • »
    »
    8 months 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.

    • »
      »
      »
      8 months 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]

      • »
        »
        »
        »
        8 months 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]

»
8 months 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

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can ternary search pass pretests on D?

»
8 months ago, # |
  Vote: I like it +114 Vote: I do not like it

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

»
8 months 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.

  • »
    »
    8 months 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.

    • »
      »
      »
      8 months 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

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

    #MeToo

»
8 months 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

  • »
    »
    8 months 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

  • »
    »
    8 months 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.

  • »
    »
    8 months 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

»
8 months 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:

»
8 months 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 ?

  • »
    »
    8 months 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)

  • »
    »
    8 months 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.

  • »
    »
    8 months 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]$$$.

»
8 months 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.

»
8 months 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

  • »
    »
    8 months 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.

»
8 months 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

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    greedy solution worked for me

  • »
    »
    8 months 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).

»
8 months 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.

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

    You can do 5 moves right and 1 move up.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

RIP Rating :(

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It was a tough contest for me

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
8 months 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

»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve C ?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did binary Search

  • »
    »
    8 months 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)

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How are you calculating position of x at time T ?

      • »
        »
        »
        »
        8 months 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;
        }
        
  • »
    »
    8 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

»
8 months 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!

  • »
    »
    8 months 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.

  • »
    »
    8 months 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.

    • »
      »
      »
      8 months 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

    • »
      »
      »
      8 months 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.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    wanna see a hard D...

»
8 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Combined round==RIP Rating

»
8 months 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 :)

»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

how to solve C?

  • »
    »
    8 months 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

  • »
    »
    8 months 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.

»
8 months 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 :(

»
8 months 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?

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what was a 15 test for D?

»
8 months 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

  • »
    »
    8 months 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.

    • »
      »
      »
      8 months 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

      • »
        »
        »
        »
        8 months 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

»
8 months 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 ;_;

  • »
    »
    8 months 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. ;_;

    • »
      »
      »
      8 months 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. ;_;

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

how to solve problem D?

»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

is submitted code visible for everyone ?

»
8 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Why submissions are not visible yet?

»
8 months 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.

  • »
    »
    8 months 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.

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

what is the author's solution of B?

»
8 months ago, # |
  Vote: I like it +30 Vote: I do not like it

What is test 9 in B?!

»
8 months 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

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why other solutions are not available?

»
8 months 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

»
8 months ago, # |
  Vote: I like it +4 Vote: I do not like it

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

»
8 months 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.

  • »
    »
    8 months 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.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Most of RED coders got system test failed in B and I thought I could be able to solve B :p

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone give me a hint for problem E?

  • »
    »
    8 months 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.

  • »
    »
    8 months ago, # ^ |
    Rev. 2   Vote: I like it -22 Vote: I do not like it
    Hint
    Solution
»
8 months 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.

»
8 months ago, # |
  Vote: I like it +57 Vote: I do not like it

Problem F was so nice!

»
8 months ago, # |
  Vote: I like it +10 Vote: I do not like it

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

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain your solution?

    • »
      »
      »
      8 months 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

      • »
        »
        »
        »
        8 months 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.

    • »
      »
      »
      8 months 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).

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

    I solved with just physics

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

    By just physics you mean relative velocity?

    • »
      »
      »
      8 months 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.

  • »
    »
    8 months 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

  • »
    »
    8 months 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)

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve B?

»
8 months 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 :(

  • »
    »
    8 months 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.

  • »
    »
    8 months 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

    • »
      »
      »
      8 months 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.

»
8 months ago, # |
  Vote: I like it -15 Vote: I do not like it

Give me some hint for problem B

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it
    Hint 1
    Hint 2
    Hint 3
    Hint 4
»
8 months ago, # |
Rev. 2   Vote: I like it -6 Vote: I do not like it

.

»
8 months 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.

  • »
    »
    8 months 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

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Congrats on creating new absolute rating change records!

»
8 months ago, # |
  Vote: I like it +10 Vote: I do not like it

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

  • »
    »
    8 months 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

    • »
      »
      »
      8 months 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.

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

Today's problem B has been really confusing!

»
8 months 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 :(

»
8 months ago, # |
  Vote: I like it +97 Vote: I do not like it

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

  • »
    »
    8 months 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 ?

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

      Its actually a google chrome plugin of CF Predictor. Link: Plugin

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        That's really cool and I didn't knew about it . Thanks mate.

»
8 months 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.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Great contest from upsolving point of view XD.

»
8 months ago, # |
  Vote: I like it +61 Vote: I do not like it

»
8 months 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 ;)

»
8 months 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

  • »
    »
    8 months 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.

»
8 months 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 :)

»
8 months 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?

  • »
    »
    8 months 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.

    • »
      »
      »
      8 months 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.

    • »
      »
      »
      8 months 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?

    • »
      »
      »
      8 months 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.

      • »
        »
        »
        »
        8 months 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.

        • »
          »
          »
          »
          »
          8 months 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].

          • »
            »
            »
            »
            »
            »
            8 months 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"

»
8 months 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 .

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

.

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

    b must be non-decreasing

  • »
    »
    8 months 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.

»
8 months 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.

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

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

    • »
      »
      »
      8 months 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

      • »
        »
        »
        »
        8 months 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.

    • »
      »
      »
      8 months 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?

»
8 months ago, # |
  Vote: I like it +21 Vote: I do not like it

Vovuh looking lonely in the Top Contributors :(

»
8 months 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.

  • »
    »
    8 months 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)

»
8 months ago, # |
  Vote: I like it -48 Vote: I do not like it

I hate problems

»
8 months ago, # |
  Vote: I like it -12 Vote: I do not like it

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

  • »
    »
    8 months 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

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    O(n) using two pointers

  • »
    »
    8 months 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.

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

    binary search! O(nlogn)

»
8 months 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

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
8 months 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?

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

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

  • »
    »
    8 months 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!

»
8 months 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?

»
8 months 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]

  • »
    »
    8 months 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.

    • »
      »
      »
      8 months 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!

      • »
        »
        »
        »
        8 months 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.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ratings changes is back.

»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

it was hard contest

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

deleted

»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I want to work in Grakn Labs.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it