mazihang2022's blog

Codeforces Round #858 (Div. 2)
By mazihang2022, 13 months ago, In English

Hi Codeforces!

Talaodi, YunQian, xukai and I mazihang2022 are excited to invite everyone to participate in Codeforces Round 858 (Div. 2), which will be held on Mar/18/2023 15:05 (Moscow time). Please note the unusual start time.

This round will be rated for participants with rating lower than 2100. We will be pleased to see the participants with a higher rating to take part in our round unofficially as well!

You will be given 6 problems to solve, one of which contains subtasks. You will have 2 hours and 15 minutes to solve them. Scoring distribution will be announced later.

We would like to thank everyone who helped with this round:

We are looking forward to your participation. Good luck and Have fun!

UPD1: Score distribution: $$$500-1000-1750-2000-2250-(2500+1500)$$$

UPD2: Editorial

UPD3: Congratulations to the winners!

Official winners:

  1. MoFalkmusic
  2. Goldenglowo
  3. 2021_yes
  4. Terry2022
  5. gajar.nouka

Unofficial winners:

  1. BucketPotato
  2. MoFalkmusic
  3. Goldenglowo
  4. tute7627
  5. 2021_yes
  • Vote: I like it
  • +70
  • Vote: I do not like it

Comments Comments (166)
| Write comment?
»
13 months ago, # |
  Vote: I like it +88 Vote: I do not like it

as the mascot, give me contribution!

→ Reply
»
13 months ago, # |
  Vote: I like it +26 Vote: I do not like it

As a tester, I liked to test this round, and hope you will have fun participating :)

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

    As a participant, I want to thank you for the contest!

    → Reply
»
13 months ago, # |
  Vote: I like it +42 Vote: I do not like it

As a grey tester I can say that div3 div4 participants will like the round.
Glhf!

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

    Gray tester

    Spoiler
    → Reply
»
13 months ago, # |
  Vote: I like it +20 Vote: I do not like it

As a tester, I hope you enjoy the problems as much as I did.

→ Reply
  • »
    »
    13 months ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

    Tomorrow is the birthday of my most beloved and only uncle. I want to congratulate him on the gift and good deltas after the contest!

    milind0110 orz!

    → Reply
»
13 months ago, # |
  Vote: I like it +25 Vote: I do not like it

As a tester, I enjoyed testing the round. Good luck to participants!

→ Reply
»
13 months ago, # |
  Vote: I like it +17 Vote: I do not like it

My first contest as an expert. Definitely not dropping back to specialist

Spoiler
→ Reply
»
13 months ago, # |
  Vote: I like it +25 Vote: I do not like it

Perfect time for Chinese people

→ Reply
»
13 months ago, # |
  Vote: I like it +41 Vote: I do not like it

As a tester, I must say that this contest has a problem that got into my favorite problems list. You should definitely participate in it.

→ Reply
»
13 months ago, # |
  Vote: I like it -16 Vote: I do not like it

As a user, this contest is one of the codeforces contests.

→ Reply
»
13 months ago, # |
  Vote: I like it +36 Vote: I do not like it

As GPT-4, I will be participating in this Round :) Get Ready Humans.

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

    I'll focus on your performance.

    → Reply
  • »
    »
    13 months ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    Division 2 is still hard for GPT. What's funny is that GPT is eager to solve hard problems than problem A. For example having a potential solution for problem E which got finally TLE, than coming up with some basic logic for problem A. P.S. I wasn't able to use GPT-4 all the time, even with the paid subscription, it's still limited to 25 requests per 3 hours, LoL...

    → Reply
  • »
    »
    13 months ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    Got positive delta at least :)

    → Reply
»
13 months ago, # |
  Vote: I like it +2 Vote: I do not like it

first time a round in which I know so many testers :hype:

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what can be reason to increase contest duration by 15 minutes than usual 2 hour duration ?

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

As a contestant, I anticipate this Chinese Round to be great one seeing the authors!

→ Reply
»
13 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Hope to become master again!..

→ Reply
»
13 months ago, # |
  Vote: I like it +2 Vote: I do not like it

ooh there are a contest again...i feel i have got long time without any contest ... ....actually when you get hacked in two consecutive contest you will need more contests to get your lost point again . i hope ,i have no hacked problems in this contest :)

→ Reply
»
13 months ago, # |
  Vote: I like it +2 Vote: I do not like it

I wish I could do well in this div

→ Reply
»
13 months ago, # |
  Vote: I like it +3 Vote: I do not like it

CN round, rating recycling round

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

    HOW DO YOUR E'S SOLUTION WORK? I GET 10* TLE ON 10 NOW! TERRIBLE!

    → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

OH,a bad time for me QWQ

→ Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it -7 Vote: I do not like it

damn Dominater069 & milind0110 as testers But VIP tester must be Codula

→ Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it +12 Vote: I do not like it

18o3 orz

→ Reply
»
13 months ago, # |
  Vote: I like it +3 Vote: I do not like it

feecle6418 orz

→ Reply
»
13 months ago, # |
  Vote: I like it +12 Vote: I do not like it

omg subtask for problem F round

→ Reply
»
13 months ago, # |
  Vote: I like it +15 Vote: I do not like it

Another round with problem C of 1750 score

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope rating ++ in Chinese rounds! Good luck!

→ Reply
»
13 months ago, # |
  Vote: I like it +46 Vote: I do not like it
My predictions to this contest
→ Reply
»
13 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Hope rating++

→ Reply
»
13 months ago, # |
  Vote: I like it +1 Vote: I do not like it

good luck!

→ Reply
»
13 months ago, # |
  Vote: I like it +4 Vote: I do not like it

WOW the score distribution...

→ Reply
»
13 months ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

Good luck everybody!Hopefully i will become pupil again.

→ Reply
»
13 months ago, # |
  Vote: I like it +14 Vote: I do not like it

Masterforces!

→ Reply
»
13 months ago, # |
  Vote: I like it +3 Vote: I do not like it

I think I am going to have fun after solving A,B good luck in C am not interested :D

→ Reply
»
13 months ago, # |
← Rev. 4   Vote: I like it +1 Vote: I do not like it

speedforces is back !

→ Reply
»
13 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Now, this was completely opposite to today's Mathura ICPC prelims. :(
Tooooo Tough.

→ Reply
»
13 months ago, # |
  Vote: I like it +37 Vote: I do not like it

Hardest div2 C ever :)

→ Reply
»
13 months ago, # |
  Vote: I like it +5 Vote: I do not like it

I saw names of all problems , ans i was like.....isn't it masters' round?!?!?! :)

→ Reply
»
13 months ago, # |
  Vote: I like it +17 Vote: I do not like it

I can't solve Problem.B :(

and I will 掉大分

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

C hurts :(

→ Reply
»
13 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Dumbest C ever lol. So many cases

→ Reply
»
13 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I couldn't even solve the subtask for C, generating any array that satisfies the condition, let alone a minimum distance one. All I could think of was an array of all 0's.

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

    if n is not odd then you can generate one number n, and all other -1

    → Reply
    • »
      »
      »
      13 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Is there any optimization for the odd case? Or is it just [0, 0, 0, 0...]?

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

        Then all q should be 0, however, only when n=1 then the answer is abs(p[0]-p[1])

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

      what if n is odd then?

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

        then q should be all 0s

        → Reply
        • »
          »
          »
          »
          »
          13 months ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          Damn, I got this right. Not sure why still WA.

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

            I think for n==1 abs(v[0]-v[1]) should be good enough because abs(v[0]-v[1]) gives the optimal solution for every case. Maybe you missed something else.

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

              I realized I missed {0,0,0,0} for n==2. I only considered {2,2,2,2} and {-1,-1,-1,2} I am so mad now.

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

      so if n is odd except n=1 ,all the a[i] is 0?

      → Reply
      • »
        »
        »
        »
        13 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        For every n we try 0,0,0,...,0. Corner case n = 1, for n = 2 try 2,2,2,2. and for n % 2 == 0 we got also -1, -1, -1, ..., -1, -1, n

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

      I got this by brute forcing on 3rd test case but how do we prove that this is sufficient for the given question?

      → Reply
»
13 months ago, # |
  Vote: I like it +17 Vote: I do not like it

Let's face it. I solved D by finding patterns using pure brute force. I don't even know what the hell this problem is all about. But i passed it:)

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

    orz

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

    I think you are the luckiest person on the planet for a moment.Can you describe how you have done.

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

      I observed the sample and found that 2=1*2, 7=2*3+1, 31=7*4+3, 167=31*5+12, 1002=167*6, 7314=1002*7+300, 60612=7314*8+2100. Then I found the pattern of the number behind.

      However, it is not correct at first, so I wrote a brute force program:

      Code

      I found about the 0 cases and finally developed the right pattern. When I finished testing, i got pretest passed.

      → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How C & E?

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I like problem D, thanks.

→ Reply
»
13 months ago, # |
  Vote: I like it +25 Vote: I do not like it

I think we should exchange D and E

→ Reply
»
13 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Hooooooow toooooooo sooooolllllllllvvvvvvveeeeeeeee EEEEEEEEEEEEE TwT too hard

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm not sure if i understood C wrong, depending on what i have understood the output in sample 3,4 is impossible. that was a mind F*** for me. from what i understood this condition should be met the product of n elements of the array must equal the sum of the same n elements because we should exclude and include the same elements but HOW. it's either 4 elements 2 2 2 2 or if it's more i didnt find other than array filled with zeros. im sure there is a usage for negative and positive numbers bullshit but couldnt find it

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

    [-1,-1,-1,2] works

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

      god damn it i literally thought of every thing except this.

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

    If n is divisible by 2, then the array of length 2n: [-1, -1, ..., -1, n] satisfies the condition.

    → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C? I went through all possible patterns but still WA.

→ Reply
  • »
    »
    13 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    if n is not odd then [-1,-1,-1...,-1,n] works otherwise [0,0,0...] is one possible solution for all arrays. You also need to take care of corner cases for n==1 and n==2. For n==2, [2,2,2,2] works.

    → Reply
»
13 months ago, # |
  Vote: I like it +3 Vote: I do not like it

I had a stroke trying to comprehend the problem statement of D. The entire time I solved a completely different problem because I misunderstood the task

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone tell me why my approach for B isn't right all i did was count the no of zeros and non zero elements . by this i made sure if i can't make all zeros disappear i'll take the smallest non zero element as answer

 if(cntzero == 0 )
        {
        	out.println(0);
        }
        else if(cntnon_zero == 0)
        {
            out.println(1);
        }
        else if( cntzero-cntnonzero > 1)
        {
            out.println(min(non_zero);
        }
        else if(cntzero-cntononzero <= 1)
        {
        	out.println(0);
        }
→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    the smallest non zero element as answer

    But if you have numbers 0 3 0 0, then clearly answer is 1, not 3.

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

      i even put one instead of min and still didn't pass just one doubt the answer is always 1 or 0 right

      → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice contest, I liked all tasks I tried (A, B, C, E)

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Seems like Mo's algorithm was not enough for E (at least for me).

→ Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

One of the toughest Div2 for me.

Anyone, please help me in B?

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

    if the number of zeros is <= the number of notZeros+1, you can arrange them (for example) like this: 0 2 0 7 0 2 0 5 0... Here, all the sums of adjacent numbers are >0, therefore, you can pick 0

    else if the greatest number is greater than 1, you can arrange it like this: 0 0 0 0 0 7 5 2 2 (there is a sequence of 0s and then the other numbers are sorted backwards) Here, all the sums of adjacent numbers will never be 1, therefore you can pick 1

    if the greatest number is 1, you can arrange it like this: 0 0 0 1 0 0 1 0 1 (where no 1's are adjacent) Here, all the sums of adjacent numbers are either 0 or 1, therefore you can pick 2

    if the greatest number is 0, you can obviously just pick 1

    → Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

In problem D Can someone explain why p=[2,1] and a=[0,1] has score 1?

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For D, I don't think the answer for case
3
0 1
is 2. for p = {1, 2} we have 2->1->3, and {2, 1} we have 3->2<-1. The total sum of vertex 1's incoming edges is 1.Yet in the case 2 the answer is
1 2 7 31 167 1002 7314 60612
for case
9
0 1 0 0 0 1 0 0
when k = 2 the answer is 2 instead of 1. Why is that?

→ Reply
»
13 months ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve F1?

→ Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

I had to generate all possible sequence to figure out the last sample of C.

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My first contest as a specialist!
Definitely not dropping back to pupil!

Spoiler
→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you can try CF-Predictor on Chrome to get the estimated rating changing

    → Reply
»
13 months ago, # |
← Rev. 3   Vote: I like it +8 Vote: I do not like it

Can anyone share some thought for problem E?

What I did in the contest was:

  1. Set a constant B

  2. Compute DP-ish the answer of all f(u, v) when the number of the vertices in that depth is <= B, compute additional answer when needed.

  3. Do the same as in query.

I thought the complexity should be like O(n^(3/2)) when B ~ n^(1/2). Got a TLE though.

Was there a O(n log(n)) or O(n) answer? I was also thinking about some smart way to precompute stuff, but didn't come out with one.

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

    There is a Mo's Algorithm on Trees solution, you can check this blog if you are not familiar with the algorithm.

    → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What the fuck is the brute force solution of E with just memorizing the queries getting pretests passed?

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

    how? i have tried using both map and unordered_map but failed.

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

    What's wrong with that?

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

    It can be proved that the complexity of it is O(n*sqrt(n)).

    Consider the set of vertices of the same depth. We call Si as the set of depth i. If the size of Si is below sqrt(n), then we can calculate the answer of each pair in it using the answer of Si-1. Otherwise, we ignore it. Because the size of Si is below sqrt(n), the size of the set of their parents is below sqrt(n), too. So, we can calculate the answer of each pair of their parents. You will find that you calculate the answer of min(sqrt(n),size)^2 pairs in one depth, so the complexity of it is O(n*sqrt(n)).

    When we answer a question of (x,y), let i be the depth of them. If the size of Si is below sqrt(n), we can use the answer that we have calculated. Otherwise, we use brute force algorithm until we find the answer of (x,y) is calculated. You will find that the process will happen only if the size of Si is above sqrt(n). The number of those i is below sqrt(n), so we do this process at most sqrt(n) times in one query.

    You will find that the brute force solution of E with just memorizing the queries is the same as my algorithm.

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

      You are right, I thought it was Mo's.

      → Reply
»
13 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Am i true that E is sqrt decomposition?

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Approach for C :

if n is 1 then just abs(p[0] — p[1]) else if n is 2 then consider {2, 2, 2, 2} and {2, -1, -1, -1} else if n is even then consider {n, -1, -1, -1 ... (2n — 1) times}

I don't know the proof :(

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Awful contest. The letter number of problems should be A-C-D-F-E-G1-G2. How did testers test this contest?

Solved A-C and E. Maybe I could solve D if I've consumed less time on some wrong approaches of E, but I don't have enough time for it.

A: The number of first operation (+1, +1) is d-b, and second operation (-1, 0) is a+d-b-c. The answer is their sum if both are non-negative.

B: Let c0=count of zeros in the array. Then if c0<=floor(n/2), we can arrange numbers such that every 2 occurences of zero are non-adjacent, then every pair of adjacent numbers will have positive sum, so MEX=0. Otherwise, we could put zeros on the left and other number on the right, if there's some number >=2, we put it on the boundary of zeros and positive numbers, so every non-zero sums will be >=2, so MEX=1. Otherwise, there are only 0 and 1 in the array, and because the count of zeros is strictly more than ones, we can arrange them like 01010...0100...00, then MEX=2.

C: By brute force for n<=4 we can conjecture that:

  • if n=1, good arrays are [a, a] where a can be any integer.

  • if n=2, good arrays are [0, 0, 0, 0], [2, 2, 2, 2], [-1, -1, -1, 2] (and its permutations).

  • if n>2 and n is odd, only [0, ..., 0] is good array.

  • if n>2 and n is even, good arrays are [0, ..., 0] and [-1, -1, ..., -1, n] (and its permutations).

E: Mo's algorithm on tree. For each depth d we need to record nodes with depth d on the current path, and if there are 2 nodes (u, v) with depth d, they contribute a[u]*a[v] to the answer. And we need to add dp[lca(x, y)] for each query additionally, where dp[i] is the sum of a[j]^2 over all nodes on the path from 1 to i.

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

    For C:

    If $$$n=2$$$, why $$$[-1,-2,-1,3]$$$ isn't good array?

    If $$$n=3$$$, why $$$[0,x,-x,0,-x,x]$$$ isn't good array?

    Have I misunderstood the meaning of good?

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

      Condition should hold for every subsequence, and -2*3 != -1 + -1

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

        Thank you, I thought that subsequence means that elements need to be continuous.

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

    Hi just wanted to give my perspective as a tester

    i solved abcde however c got changed and i solved the new c too in 20mins.

    for C : there is really cute algebra solution, no need of bruteforce; first take any random set S1 and its complement S2, write equation, swap one element from S1 with one element from S2

    Rewrite the equation, and cancel variables, you will easily get the necessary stuff

    D : this problem has a complicated statement but i didnt expect it to become this hard. Quite a few testers solved it and most upsolved it atleast.

    E : this problem also has a neat sqrt solution, you can check my submission

    → Reply
»
13 months ago, # |
  Vote: I like it +13 Vote: I do not like it

problem C was harder than usually, even two last examples were unclear for me

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

wtf..

Can anyone explain the solution for Problem C..

was it at all a constructive or observation based Problem too?..

→ Reply
»
13 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Can someone please explain why am I getting MLE in A? Submission: 197908525

This works perfectly fine in 256MB, so why would it give MLE with a higher memory limit?

→ Reply
»
13 months ago, # |
  Vote: I like it +27 Vote: I do not like it

score = -roundNumber

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

problems are a bit more difficult than div2 before.

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

waiting for editorial

→ Reply
»
13 months ago, # |
  Vote: I like it +2 Vote: I do not like it

thanks for contest!!!this contest's C is harder than normal div2 C.F1 and F2 is excellent problem.

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I had submitted my answer for problem B and it got accepted but now it is showing in queue . please fix it.

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

As a participant, akash bhora tara........:)

→ Reply
»
13 months ago, # |
  Vote: I like it +6 Vote: I do not like it

please rejudge https://codeforces.com/contest/1806/submission/197938565, test 25 is pretest but i can't pass it in maintest.

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

    It may be the fluctuation of the evaluation machine. Please test it several times. thank you!

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

    Problem E has a very tight time limit, which I think is unreasonable

    → Reply
»
13 months ago, # |
  Vote: I like it +2 Vote: I do not like it

My brute force solution for E got passed. submission: 197969099 The approach is: for every query (x,y) with depth d, brute force the first sqrt(n) pairs. Then memorize the rest d-sqrt(n) pairs. Unfortunately, I don't know how to prove or disprove it.

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

unordered_map is so slow that I got TLE in problem E.

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

    I mean I got TLE with map.

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

      i'm so sad , i know it can be solved by hash ,and tried with unordered map i'v tried lots of times but TLE which waste my time and i know i may pass it if i write a hash instead of using STL at the last 3 minutes

      → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C is a very interesting constructive problem.

→ Reply
»
13 months ago, # |
  Vote: I like it +3 Vote: I do not like it

excuse me, for problem C what is the answer of this input? " 1 3 1 2 3 1 2 3 "

→ Reply
»
13 months ago, # |
← Rev. 3   Vote: I like it +31 Vote: I do not like it

I tried to read D after contest and couldnt understand the statement. So i asked someone to explain it to me, only to then notice that they also didn't understand the statement, lol.

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

    So how can the statement be improved while being understandable for someone who does not know of DSU while not being ambiguous?

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

      I think it would help if the statement was worded in a way that gave a more intuitive idea of what is happening.

      For example, you could first say that the leader of a vertex is the vertex in its weakly connected component with no outgoing edges, and then say that the match will go out between $$$leader(p_i)$$$ and $$$leader(p_{i+1})$$$.

      This way you show that $$$u$$$ and $$$v$$$ are a function of $$$p_i$$$ (which is important because at that point they could be 2 numbers that are given on input) and there is an intuitive interpretation of "leader" that can make you understand the statement even if something is unclear to you

      You could also drop the graph definition entirely and go 100% ludical, for example by saying that when leader $$$a$$$ wins a game against another leader $$$b$$$, $$$a$$$ becomes the leader of $$$b$$$ as well as all the people that $$$b$$$ was a leader of, and then define which games would happen based on the $$$a$$$ and $$$p$$$ sequences.

      Another thing that would certainly help was if the animated gif explaining the problem had a bigger example, what is happening is still very ambiguous even when looking at it.

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

        You could also drop the graph definition entirely and go 100% ludical, for example by saying that when leader a wins a game against another leader b, a becomes the leader of b as well as all the people that b was a leader of, and then define which games would happen based on the a and p sequences.

        I actually wanted to to with this.

        alternate statement draft

        But testers did not like because they claimed the current statement does not look like a mess of random operations.

        Regarding the part about intuitiveness, I thought the title was a big hint into what the process was doing as we tried to explain DSU process in the most concise way possible.

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

          Well, a lot of problems with topics on the title tend to have nothing to do with that topic so I typically don't consider that.

          Anyways I also don't like that draft as well. I think the core problem is that the operations do have a very pretty and intuitive interpretation but it is hard to decode from the statement (someone is the leader of a group and if they win the game they become the leader of the group they won against).

          For example, this was what that person that explained the problem to me said:

          Spoiler

          Even though there is little to no mathematical rigor (and technically being wrong, as they also missed that it was the sum for 1 and not the overall winner), it helped me looking at the definitions of the original statement and saying stuff like "ahhh, that's why we have a permutation here" and "it makes sense now that we care about the vertice with no outgoing edges".

          Just to be clear, I don't think that example should be the statement of the problem verbatim. However I think adding flavor text to problems like this helps a lot. That's why a lot of statements say stuff like "We're doing X. Formally, we will have Y." Instead of just saying the mathematical definition head on.

          → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

If someone is interested, I have explained my $$$O\left(n \cdot q\right)$$$ solution for problem 1806E - Tree Master in this comment under the editorial.

→ Reply
»
13 months ago, # |
  Vote: I like it +55 Vote: I do not like it

Problem E is exactly the same as this problem.

→ Reply
»
13 months ago, # |
  Vote: I like it +10 Vote: I do not like it

I think the solution of E is a little rigid.But we can still learn something good from the contest.

→ Reply
»
13 months ago, # |
  Vote: I like it +24 Vote: I do not like it

You are wrong.Here is why.

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You don't need to control the constant for problem E, you can set the threshold to around 100, and you can run fast.
Here

→ Reply