Автор isaf27, история, 4 года назад, перевод, По-русски

Привет, Codeforces!

grakn

Я рад пригласить вас поучаствовать в Grakn Forces 2020, который состоится 30.09.2020 17:35 (Московское время). Он будет рейнтинговым и открытым для обоих дивизионов.

Этот раунд проводится по инициативе и поддержке компании Grakn Labs. Больше информации можно найти здесь.

Все задачи были придуманы и подготовлены 300iq и isaf27. Большое спасибо coderz189, Retired_cherry, QAQAutoMaton, Prakash11, morzer, qlf9, nkamzabek, gdb_18, talibmohd, Dragnoid99, KAN и VladGanzha за тестирование раунда и отличные советы, а так же MikeMirzayanov за системы Codeforces и Polygon.

Участникам будет предложено 9 задач и 2 часа 30 минут на их решение. Пожауйста, прочтите условия всех задач. Всем успешного раунда и повышения в рейтинге!

Спасибо компании Grakn Labs за подарки участникам:

Денежные призы:

  • 1е место = 500 евро
  • 2е место = 250 евро
  • 3е место = 100 евро

Дополнительные призы:

Топ 50 получат:

Комплект подарков от Grakn Labs:

  • Стикеры
  • Футболка "Grakn Labs"

50 участников, выбранных случайным образом среди занявших с 51-го по 250-е место, так же получат:

Комплект подарков от Grakn Labs:

  • Стикеры
  • Футболка "Grakn Labs"

Grakn Labs — это команда единомышленников, движимых одной целью: решать самые сложные мировые проблемы с помощью инженерии знаний. Флагманскими технологиями Grakn Labs являются граф знаний Grakn и язык запросов Graql. Эти технологии помогают организациям в различных отраслях, включая сферу жизнеобеспечения, обороны, финансовых услуг и робототехники, создавать интеллектуальные системы, которые изменят мир.

Grakn Labs ищут лучших, чтобы пополнить свою команду. Если вы думаете, что это звучит как интересный шанс поработать над инновационной технологией, то они с радостью рассмотрят вашу кандидатуру.

Заполните форму →

UPD! Разбалловка: 500 — 1000 — 1250 — 2000 — 2500 — 2500 — 3000 — 3750 — 3750

UPD! Разбор

Поздравления победителям:

  1. tourist
  2. Benq
  3. maroonrk
  4. Egor
  5. ecnerwala
Анонс Grakn Forces 2020
  • Проголосовать: нравится
  • +506
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +657 Проголосовать: не нравится

As a tester, I want contribution

»
4 года назад, # |
Rev. 4   Проголосовать: нравится +22 Проголосовать: не нравится

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

RIPRating

»
4 года назад, # |
Rev. 2   Проголосовать: нравится -36 Проголосовать: не нравится

.

»
4 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

Will this contest be similar to global rounds?

»
4 года назад, # |
  Проголосовать: нравится -48 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +66 Проголосовать: не нравится

isaf is the trusted author !!! :hug:

»
4 года назад, # |
  Проголосовать: нравится -29 Проголосовать: не нравится

I want to participate but I have a confusion. It is said that Grakn is distributed knowledge "Graph". So will majority of questions(or all) be related to graph theory in this contest? (I am having this perception because Div1 people also participating along with CMs,Experts, Specialists and Pupil). Please tell.

»
4 года назад, # |
  Проголосовать: нравится +267 Проголосовать: не нравится

Me after seeing 300iq is a problem setter.

Wrong answer on test case 256.

»
4 года назад, # |
  Проголосовать: нравится +411 Проголосовать: не нравится

9 problems again :(

That's too many for a short competition, especially with CF scoring (where the speed of solving easy problems matter most). It favors people like me who can do div2 problems quickly and then just are stuck with hard problems.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +43 Проголосовать: не нравится

    Actually not sure about that. Considering that A and B are just one minute tasks, we have a round with 7 problems. With decent problem difficulties it looks like ordinary Div 1 with 5 problems, except that for the hardest task you can choose between 3.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +35 Проголосовать: не нравится

    So now after seeing the actual problem set, where do you draw the line for "easy tasks" for today? A-G? Or do you see it differently?

    And what do you think about the problem set in general?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +26 Проголосовать: не нравится

      I would say that ABC were too easy and I would prefer to just get D+. The first two problems were so artificial and definition-heavy. It's the opposite of what I would want to show to a beginner as a cool problem.

      If one really wants to use 9 problems, I would expect A and B to be very very easy (more like div3 than div2). So those problems were more difficult than I expected. And if I was a beginner, I would hate the fact that there is almost no programming in ABC.

      It's also worth noting that the average time of solving problem A is around 3 minutes for high-rated people. It's far away from "A and B are just one minute tasks". It also takes time to open the statement, create a new file, copy samples and submit. Reading and clicking speed matters, hurray.

      In terms of quality, I didn't like anything about ABCDE, but then F and G were very nice and their difficulty is around div1-C.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится -26 Проголосовать: не нравится

    I guess this contest favoured you a lot. Lol

»
4 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

i wish this contest will be a good contest :3

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +26 Проголосовать: не нравится

Not any more.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone tell me what is the level of first 3-4 problems in a combined div1 and div2 rounds like this. I'm a pupil and have solved at most 3 problems in normal div-2 rounds.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It varies a lot but I think authors try to keep the consistency of first 6 problems the same as div2, ie combined B is around the level of div2B

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    i hope distribution look like div.3(2)+div2(4)+div1(3) kind of distribution, otherwise it seems very unlikely to have contest of 9 problems.

»
4 года назад, # |
  Проголосовать: нравится +67 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +50 Проголосовать: не нравится

As a tester, give me contribution.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится -35 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Please note the usual timings of the contest :D

»
4 года назад, # |
  Проголосовать: нравится -20 Проголосовать: не нравится

Is it rated for div3 people?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

2h 30min lol

»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Разбалловка?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    будет объявлена ближе к началу раунда

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      Я умею читать.... Вот только Время ''близкое к началу раунда'' уже наступило

»
4 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

Dear Grakn Labs authors,

I have some questions, How many people would you admit for Lab internship? And What is your requirement for these positions?

thanks for holding a CF's contest

regard.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +28 Проголосовать: не нравится

    Ideally, we are looking for fulltime candidates, but internships are also possible. Regarding the number of candidates: we don't have a fixed number, if there are 2 very strong candidates who both fit, I would imagine we will take both, but hard to say upper limits and it depends on the candidates.

    And What is your requirement for these positions?

    We test cognitive abilities, problem-solving skillz, we gonna ask about previous experience, education (are you from STEM or not?, bachelor / master / phd?) but we don't have "must know language A, library B" requirements. Although for a more senior position we gonna expect you to know some specific stuff

»
4 года назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

after seeing the question i jump into this comment section

»
4 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

What was the problem with B?

»
4 года назад, # |
  Проголосовать: нравится +73 Проголосовать: не нравится

bad statements, problems are not easy to understand.

»
4 года назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится

why a physics problem? why?

»
4 года назад, # |
Rev. 5   Проголосовать: нравится +3 Проголосовать: не нравится

Is the round unrated or still rated? I saw a few statements correcting problem B some time ago, and I think they might have mentioned something about rated or not/extended time, but I don't exactly remember.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

..

»
4 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

I feel like this round is around Div 1.5

»
4 года назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Don't worry 4000 is gonna get a huge drop after the system tests. Lot of masters and GM are also failing system tests for B, this indicates that pretests were very weak.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      You don't need to be. At max from your side you can improve your practice and learn new concepts. So please focus on learning new concepts and trying to practice as many questions you can and they should be of difficulty greater than your rating + [100, 300]

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        Thanks for your kind words, lot of grandmasters also got this wrong, so i should not worry much and practice as you suggested rating + [100,300]

»
4 года назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can ternary search pass pretests on D?

»
4 года назад, # |
  Проголосовать: нравится +114 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

    Lol you atleast got B, I gave up on that and started doing D. And didn't get it. Now Imma go cry in a corner. Thought I'll become CM today. Predictor says I'm gonna lose 100. F.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Bad day for you bro. But this is the story of me in every combined rounds, complicated statement in B, try to understand the statement thus kill your potential, go to C solve it then come back and try more. Finally get B and then rush for D, get idea before just 10 min of end and rage in corner. This is the thing that dropped me from 1800+ where I never managed to reach till now

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    #MeToo

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Very briefly,

    For components with size 4,2,1, first merge 1 with one of element in 4

    [4,2,1] ==> [3,2,2]

    then merge the two 2s

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Basically you separate into powers of 2 and greedily merge them.

    So 7 decomposes into [1,2,3,4], [5,6], [7]. It's pretty easy to get all of those to be equal to each other. Now, merge [4,7] to get [1,2,3], [5,6] and [4,7] as your buckets. Then, merge [5,4] adn [6,7], so you have [1,2,3], [4,5,6,7] as your buckets, which is at most 2 distinct elements, as desired.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +44 Проголосовать: не нравится

    Notice that if n = 2^k, there will always be a way to make n elements be identical. In general case, we can make elements in [1..2^k] identical and do it one more time with [n-2^k+1, n], k is the largest number that 2^k <= n

»
4 года назад, # |
  Проголосовать: нравится +73 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    As for me, I couldn't understand E within 20 minutes) So I just skipped it.
    And F is just seems pretty easy to spend more time on it (and to solve it)

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +42 Проголосовать: не нравится

    You can make $$$2^k$$$ elements equal in $$$k 2^k$$$ operations, by first making the first $$$2^{k-1}$$$ elements and last $$$2^{k-1}$$$ elements equal, then applying the operation to the first element of both sides, then the second element of both sides, and so on.

    To have at most two values, just take the largest k such that $$$2^k \leq n$$$, and apply the above process to the first $$$2^k$$$ and last $$$2^k$$$ elements.

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +232 Проголосовать: не нравится

Did nobody test problem B? How is it possible that a problem with wrong tests, even wrong answers to the sample, gets through?? Did every tester somehow understand the problem wrong in the same way? This wasn't the last problem of div 1 either, every tester should have gotten to div2B o.O

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +46 Проголосовать: не нравится

    When I tested the round there was problem C in place of B.

    It was added after the testers feedback,so testers are not aware of it.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    greedy solution worked for me

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    For each (robber, projector) pair calculate pair (upMoves, rightMoves). Now sort this list n * m pairs and answer is some prefix of robbers moving up and suffix of robbers moving right. This can be calculated with suffix maximums in O(n * m).

»
4 года назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

In problem D sample input 4, you have to make 5 right moves to save (7,0) robber from (11,5) light and you have to make 2 up moves to hide (3,5) from (6,6), so the minimum answer should be 7, not 6. I have read problem statement multiple times. There will 5 moves when we increase ai of all robbers and 2 moves where we increase bi to same all of them. I can't understand where I am wrong.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

RIP Rating :(

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

Rip Rating

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

How to solve C ?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I did binary Search

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Binary search for each time T and if the position of x > position of y increase T else decrease it..!! ~~~~~

    long double lo=0,hi=l,mid;
    while(hi-lo > eps){
        mid= lo + (hi-lo)/2;
        long double x=diff(mid,l,a);
        if(x>=0){
           lo=mid;
        }
        else{
           hi=mid;
        }
    }
    

    Here diff() function tells the difference of positions (x-y)

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      How are you calculating position of x at time T ?

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        ld= long double I calculated x and y separately

        ld diff(ld time,ld l, vi &a){
        	ld x=0,y=l;
        	int n=a.size();
        	ld speed=1,ti=0;
        	for(int i=0;i<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;
        }
        
»
4 года назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

How to solve D? Never saw such a hard D RIP rating T_T PS: After watching editorial I felt it wasn't that hard!

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    In problem D sample input 4, you have to make 5 right moves to save (7,0) robber from (11,5) light and you have to make 2 up moves to hide (3,5) from (6,6), so the minimum answer should be 7, not 6. I have read problem statement multiple times. There will 5 moves when we increase ai of all robbers and 2 moves where we increase bi to same all of them. I can't understand where I am wrong.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    wanna see a hard D...

»
4 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Combined round==RIP Rating

»
4 года назад, # |
  Проголосовать: нравится +37 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

how to solve C?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Let's say initial positions are 0 and L. Now, assume that the first car will reach the flag closest to it before car 2 reaches the flag closest to it (car 2). So, calculate that time and add it to answer. Also, update the positions of both the cars accordingly, by p1 += time * v1 and p2 -= time * v2 (note time will be same).

    Do this till you see that there are no flags between them. Then say x is the position where they meet. Solve (x — p1) / v1 = (p2 — x) / v2 (this says that they travel for same time), which gives x = (p2 — p1) / (v1 + v2). Now calculate time and add it to answer.

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

what was a 15 test for D?

»
4 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Can you elaborate The process please

      i Was try but can't find the process

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Binary search on the time, and for a given time $$$T$$$, you can simulate both cars to see where they end up after time $$$T$$$.

        Iterate over differences between adjacent $$$a_i$$$. For the car starting on the left, it has a speed of $$$i$$$ when moving from $$$a_i$$$ to $$$a_{i+1}$$$ (one-indexing), so the amount of time it takes to get through is distance divided by speed, or $$$(a_{i+1} - a_i) / i$$$, and you subtract off those time amounts when moving from left to right. The case for the right car is mirrored. At the end, check if the position of the left car is to the right of the right car, since that means the two collided.

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

»
4 года назад, # |
Rev. 3   Проголосовать: нравится +11 Проголосовать: не нравится

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

Edit: segmentation fault on pretest itself ;_;

  • »
    »
    4 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +26 Проголосовать: не нравится

    Same. Didn't initialize variables in G submitted at 2.48, got wa on pretest 1, fixed and contest over in selecting file to upload. ;_;
    Edit: AC in practice but after fixing a bug. ;_;

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +2 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

how to solve problem D?

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

is submitted code visible for everyone ?

»
4 года назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Why submissions are not visible yet?

»
4 года назад, # |
  Проголосовать: нравится -175 Проголосовать: не нравится

Problems are of very bad quality!!!

Don't like even single problem. Total wastage of time :)

You guys should have select problem set according to level of participants. Very disappointed and demotivated after this round.

Sorry to say, but it makes no sense to solve such problems.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +22 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

what is the author's solution of B?

»
4 года назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

What is test 9 in B?!

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is D concluding to range minimum query for all 2000 robbers after some processing of coordinates.. sorted along their x axis same as per lights

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

why other solutions are not available?

»
4 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What's the idea behind D? I could only think of iterating on the shifts of the X-coordinate and find the minimum Y-coordinate shift needed for each new position. Too slow.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone give me a hint for problem E?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится -22 Проголосовать: не нравится
    Hint
    Solution
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +57 Проголосовать: не нравится

Problem F was so nice!

»
4 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can you explain your solution?

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

      If 2 persons intersect in time t then they will surely intersect in ti,e t +alpha alpha be 0.0000001 also. this was the core concept. now given a time we need to find that these cars will intersect or not. and thus calculate over our binary search.

      Submission link : 94326719

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 4   Проголосовать: нравится +18 Проголосовать: не нравится

      I stored the time both person takes to reach each of the obstacles, in 2 arrays t1 and t2. Iterating through t1, if at any point t1[i]>t2[i] this means that the collision happened between a[i-1] and a[i]. (a is obstacle position array)

      Now with some maths I find position of 2 when 1 is at a[i-1]. At this point its a well known physics problem. "2 points moving at constant speed in opposite direction, find the time taken for them to collide".

      Since the time taken to collide for both is same it can be solved by the equation x/s1 = (d-x)/s2 where d is the distance between them and s1 and s2 are their speeds and x is the distance from a[i-1] to collision point. Simplifying it would be d/(s1+s2).

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    I solved with just physics

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    By just physics you mean relative velocity?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      No by making array of time required to reach each mark from left and right and then checking every adjacent marks if they can meet between them.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
    Rev. 3   Проголосовать: нравится -28 Проголосовать: не нравится

    i solved by just physics..

    but final testing pending yet...

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

How to solve B?

»
4 года назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

There is one thing I'm not very clear about in problem B: is it maximum k different numbers across all the arrays, or maximum k different numbers in each array? The way the statement is phrased makes both seem plausible, but I guessed it was the latter.

And if it was the former, why does the latter pass pretests :(

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    I think it's clear from the statement it's for each array.

    The number of different elements in the array Bi is at most k

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Ah I see. I was very confused by the sample explanation for test case 4 (which seems to have been later removed), which appears to suggest that it was for all.

»
4 года назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

Give me some hint for problem B

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится
    Hint 1
    Hint 2
    Hint 3
    Hint 4
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

And tourist won again.

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

»
4 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 3   Проголосовать: нравится +14 Проголосовать: не нравится

Today's problem B has been really confusing!

»
4 года назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +97 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    I would like to ask how can we see the rating change before it gets updated ? Are there any settings for that because I can only see columns upto last question only . There is not rating change column in it . Can anyone tell me why ?

»
4 года назад, # |
Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

In the end, I still failed to pass d. I thought of the correct algorithm, but I still couldn't finish it. . I often can't finish writing D. Even if I can pass it, it is at the last moment of the game. How can I change this situation?(Great game, thanks to 300iq and isaf27)upd:Although I didn't play well, I turned blue and I was very happy. If there are more kind people to answer my question, it would be even better. Thank you in advance.

»
4 года назад, # |
  Проголосовать: нравится +61 Проголосовать: не нравится

»
4 года назад, # |
Rev. 2   Проголосовать: нравится -43 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I have followed you. Judging from the prediction of cf predictor, this is impossible. But you may lose 80 points rating, good luck next time.

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

      I see, but thanks for the round. Most of the problems were really different from the kind of problems we see in normal codeforces round.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +18 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      You wrote a sample explanation wrong! How is that possible? Did you generate it somehow? I don't see any way to mess it up unless you were braindead.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится -41 Проголосовать: не нравится

        Just wrote a sample explanation for answer $$$3$$$ quickly, because I've seen, that the answer to this test case is 3 (from the wrong main solution).

        I didn't think: "hm, maybe it is possible to do it with 2 arrays", but I definitely should have done that.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +60 Проголосовать: не нравится

          The sample explanation didn't even add up correctly. It was possible to do in 2 arrays, as you said, but the 3 arrays in the sample added up to [1, 2, 3, 4, 4] instead of [1, 2, 3, 4, 5].

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится +29 Проголосовать: не нравится
            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"

»
4 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 3   Проголосовать: нравится -16 Проголосовать: не нравится

.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    b must be non-decreasing

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится -14 Проголосовать: не нравится

    Above answer is incorrect, it is mentioned B should be non-decreasing. Is B1 non decreasing in your above solution? And correct answer should be 8.

»
4 года назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

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

Link.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +46 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +21 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +121 Проголосовать: не нравится

      You truly are an enigma. First you complain about too many easy problems being an advantage to you, and now you complain that your competitors don't try their best? Next will you complain that someone handed you free money?

»
4 года назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

Vovuh looking lonely in the Top Contributors :(

»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    My solution is $$$O(nm\log n)$$$ with huge constant factors (because I used unnecesary multisets).

    The reason I passed D in contest may be the small optimization: If two robbers' position $$$(a,b),(c,d)$$$ satisfy $$$a\le c,b\le d$$$ then $$$(c,d)$$$ surely won't effect the answer. For the searchlights if two $$$(a,b),(c,d)$$$ satisfy $$$a\le c,b\le d$$$ then $$$(a,b)$$$ can be deleted. After the deleting, the real number of $$$n$$$ and $$$m$$$ become so small that I passed in only 60ms.

    (fixed a typo)

»
4 года назад, # |
  Проголосовать: нравится -48 Проголосовать: не нравится

I hate problems

»
4 года назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

Congrats and orz

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why my solution of A is incorrect?

First, $$$p_1 = a_1$$$

$$$i \in { 2 \sim n }$$$

if $$$p_{i-1} \ne a_i ,p_i = a_i$$$

if $$$p_{i-1} \ne b_i ,p_i = b_i$$$

if $$$p_{i-1} \ne c_i ,p_i = c_i$$$

where is wrong?

»
4 года назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Why is the rating change after this contest suddenly reverted? Did the contest become unrated all on a sudden? Did this happen with others too?

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

I am new to codeforces. I participated in this contest, solved one problem and my rating had increasd by about 400 pts. But now, my profile shows unrated again. what could be the possible reasons??[contest:1408][problem:1408A][submission:94311182]

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    The ratings changes of the last round is reverted for everyone because either the authority has not finished catching cheaters or there are some serious issues. isaf27 is the writer of the contest. The writer is not responsible for ratings update or rollback. Headquarter is responsible for this. You can ask Mike. He can give us updated information.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        It won't be a good idea if it was unethical like hacking. But I think a contestant has some minimum right to know why ratings update was rolled back and why wasn’t returned in a rated contest.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Ratings changes is back.

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

it was hard contest

»
4 года назад, # |
Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

deleted

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

I want to work in Grakn Labs.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится