Psychotic_D's blog

Codeforces Round 930 (Div. 1, Div. 2)
By Psychotic_D, 2 years ago, In English

"You are braver than you believe, stronger than you seem, and smarter than you think." — A.A. Milne

Hello Codeforces!

I have the pleasure of inviting you to participate in Codeforces Round 930 (Div. 1) and Codeforces Round 930 (Div. 2), which will start on Feb/29/2024 17:35 (Moscow time).

You will be given 6 problems and 2 hours to solve them in both divisions.

One of the problems may be interactive. So, please refer to the guide on interactive problems if you are unfamiliar with them.

The problems were prepared and authored by wuhudsm, chromate00, Psychotic_D and MagicalFlower.

We would like to thank :

Good luck, and may the code be with you!

UPD: Score distribution:

Div.1: $$$500 - 1000 - 1500 - 2000 - 2500 - 2750$$$

Div.2: $$$500 - 1000 - 1500 - 2000 - 2500 - 3250$$$

UPD2: Let's continue the streak of announcements with photos of the authors and coordinator.

Codeforces_round_930_authors

UPD3: Editorial is out.

UPD4: Top Performers

Div.1

Rank Name
1 Radewoosh
2 zhoukangyang
3 ugly2333
4 tourist
5 998batrr

Div.2

Rank Name
1 JiaY19
2 kizaru
3 Midnights
4 SATSKYnerfed
5 VTloBong
  • Vote: I like it
  • +487
  • Vote: I do not like it

Comments Comments (229)
| Write comment?
»
2 years ago, hide # |
 
Vote: I like it +41 Vote: I do not like it

Yet another TheForces official round!

Be sure to take part in this round, the authors have put a lot of efforts to prepare the round as balance as possible ;)

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +54 Vote: I do not like it

As a problemsetter, I hope everyone will enjoy the contest. May the $$$\Delta$$$ be with you!

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +33 Vote: I do not like it

As a brave tester I can assure that problems are very good

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +19 Vote: I do not like it

First time testing an official round! Hope the problems will be interesting for all of you!

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +36 Vote: I do not like it

As a tester, I assure that your Leap Day is going to be fun!

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +24 Vote: I do not like it

Finally, $$$6$$$ months have passed since the last official round of TheForces community, another official round! I hope you enjoy this round :)

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

As a tester, problems are really nice. Please do participate and get high ∆

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +21 Vote: I do not like it

As a tester, may positive delta be with you.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +27 Vote: I do not like it

as a tester i can assure that problems are very nice

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +30 Vote: I do not like it

OMG! Another Psychotic_D round!

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +9 Vote: I do not like it

so many testers !

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +47 Vote: I do not like it

Adding tibinyte2006 as newbie tester should be illegal 🤥

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

All this testers!. i think the contest is going to be great.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

Yay finally a div1 that takes place when I'm actually available.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

OMG! k1r1t0 is tester!

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +10 Vote: I do not like it

I want to become CM for the first time. I am so excited!!!

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +16 Vote: I do not like it

As a tester, this is definitely one of the rounds of all time

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +7 Vote: I do not like it

As a tester, problems are nice, recommend everyone to participate!

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +34 Vote: I do not like it

amenotiomoi orz tester <3

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

vikram108 sir orzzzzz

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

As a tester, problems are interesting, hope your delta be >0, and have fun when solving the problems, especially the interactive one(if there's one in your division)!

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

So many testers that only the "As a tester" comments would make the normal comments count. XD

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

As a green tester, the text inside the problems are not green. It's black.

But still, very clear statements all around and hope y'all enjoy the rounds!

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +70 Vote: I do not like it

Once in FOUR years

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

.

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

Illegal newbie lying face testing xD... Real Psychotic :p

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

The interactive problem is for div1 or for both division?

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it +11 Vote: I do not like it

    It may be only in Div1 or Div2 or in both Div1 and Div2, you will see it after the round starts:)

    → Reply
»
2 years ago, hide # |
 
Vote: I like it +16 Vote: I do not like it

How so pro Psychotic_D ser?

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

It'd be good if you continue the streak of announcements with photos of the authors :)

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +20 Vote: I do not like it

Damn, I thought chromate was bot.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

One problem will be based on Leap day or Leap year I guess

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

Thanks for continuing streak of putting authors pictures on the contest blog

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

grecozo will win the round, pin this.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +43 Vote: I do not like it

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

It's too early for that.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

As a parcipicant, this round will happen again in 4 years

And also Good luck for everyone!

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

Abhishek_Srivastava , the tester , orz

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +77 Vote: I do not like it

Is there a photo of MagicalFlower?

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +12 Vote: I do not like it

Orz chromate00 for being a problemsetter.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +85 Vote: I do not like it

→ Reply
»
2 years ago, hide # |
← Rev. 2  
Vote: I like it -21 Vote: I do not like it

deleted

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

I loved the way you thanked the participants.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Goodbye, cyan ;(

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

Hope I will reach to 1400+

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Is MagicalFlower the up right one on the photo?

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +70 Vote: I do not like it

No offence to anyone.

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

HAPPY LEAP DAY 2024 ROUND.

vecteezy-happy-leap-day-on-29-february-with-cute-frog-in-flat-style-15449916-1

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +32 Vote: I do not like it

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +7 Vote: I do not like it

chromate00 be like :)

→ Reply
»
2 years ago, hide # |
 
Vote: I like it -9 Vote: I do not like it

Downforces incoming

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

Psychotic_D We would have been more happy if today's contest named was Happy Leap DAY 2024

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Absolutely love the quotes that they have started putting at the start of these announcements.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Back after long time hope to solve 2-3 problems.

→ Reply
»
2 years ago, hide # |
← Rev. 2  
Vote: I like it +16 Vote: I do not like it

looking forward to photo of MagicalFlower. very handsome

→ Reply
»
2 years ago, hide # |
 
Vote: I like it -38 Vote: I do not like it

B is bad

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +7 Vote: I do not like it

whats wrong with this round??

→ Reply
»
2 years ago, hide # |
 
Vote: I like it -21 Vote: I do not like it

try something other than creating contests

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +77 Vote: I do not like it

Shout-out to all my div1 homies who submit a problem when they know for sure that they will lose rating if they become a participant after making a submission

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +10 Vote: I do not like it

Binaryforces.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +18 Vote: I do not like it

Maybe I have forgotten how to make correct submissions to problems

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +42 Vote: I do not like it

For div1, it is so painful to get -50 for each dirt, since the total score is not very high. rk30 ~ rk60 only has a score difference around 100, but the ranking doubled.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

Nice problem C

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    how to solve B, i only got the lexicographically smallest string but could not figure out how to get no.of ways

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

      The key observation is: If you go down at some point, then you have to go to the right for the rest of the operations.

      So the way I handle is to build an array b, which indicates that for a position i, if I go down, can I get the lexicographically smallest string? Then, for each position i, you have two choices: go to the right or go down. If you go down, check if b[i] = 1, then you can increase your result. If you go to the right, you have to make sure the current string you got is matching with the lexicographically smallest one.

      Submission

      → Reply
»
2 years ago, hide # |
 
Vote: I like it +14 Vote: I do not like it

Too Hard.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it -10 Vote: I do not like it

observation force

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

why so hard b

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

The first three problems were one of the best in a while, especially problem C, but the last three were too hard.

→ Reply
»
2 years ago, hide # |
← Rev. 2  
Vote: I like it +22 Vote: I do not like it

Div1B — ImplementationForces

Div1C — StandardForces, if you put it at Div1B it would easily have 500-600 solves.

I spent like 10 mins combined to think of the solutions and around an hour to implement them :).

Div1A legitimately required more thinking than Div1B and Div1C combined (and was actually a pretty cool problem).

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    What to do in problem C? I have no idea.

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

      Sort values of each attribute in non-decreasing order and add edges between adjacent attribute values "nodes" to make a line graph of their values. Going "up" in value costs 0, going "down" costs the change in value. This corresponds to the "increase power" operation. This uses $$$2 \cdot (n - 1)$$$ edges per attribute, or $$$2 \cdot (n - 1) \cdot m$$$ edges in total.

      Then add edges between attribute value nodes and pokemon nodes. The edge to the pokemon corresponds to summoning them and has a cost of $$$c_{\text{pokemon_idx}}$$$ while the edge the other way has no cost. This uses $$$2 \cdot m$$$ edges per pokemon, or $$$2 \cdot n \cdot m$$$ in total.

      Then you can just dijkstra from pokemon $$$1$$$ and find the min cost to reach pokemon $$$n$$$ in $$$O(n \cdot m \log(n \cdot m))$$$ time.

      → Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    how to implement B

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

      My solution at least is painfully long, so just going to roughly describe each step:

      1. Calculate the number of '>' to the left and '<' to the right of each pos. These represent positions where we might turn around during this operation.

      2. Based on these counts and $$$s_i$$$, we can figure out how many values we'll bounce off to the left and right. It will be either min of the count of the above two values, possibly 1 lower. We can also figure out which direction we'll leave the grid in, I just add that time to my answer here since its convinent.

      3. Now, we can keep track of prefix / suffix sums of these (one at a time) as we iterate. Then if we known we will make $$$x$$$ bounces to the left, we want the sum of distances to the last $$$x$$$ bounces. This can be represented as $$$(i \cdot x) - (\text{position_prefix_sum}_{end} - \text{position_prefix_sum}_{end - x})$$$. Don't forget to multiply this two since we bounce and come back to the center.

      Code — 248943453

      → Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    How to modify the Dijkstra for Div1C? I couldn't figure out how to quickly calculate if a pokemon would beat the other one where one is modified for in its attribute.

    → Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it +11 Vote: I do not like it

    Actually there exist easier way to solve B, my submission only takes < 30 lines

    → Reply
»
2 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

submit C in last 10 second phew~

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can someone explain why this wouldn't work for problem C ?? 248966532

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

ez minus delta

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

Why is there a 20-minute penalty for every wrong submission, when it's only two hours of competition.QAQ

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +9 Vote: I do not like it

wtf bruh :(, never seen this hard Div2.B, all aside but I enjoyed the contest. Thanks

→ Reply
»
2 years ago, hide # |
← Rev. 2  
Vote: I like it +34 Vote: I do not like it

The problems are really good, but they felt a bit harder for their position.

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

1B = https://mirror.codeforces.com/contest/733/problem/E?

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it +22 Vote: I do not like it

    It is exact the same. I modified my code for 1B, turnning 'U' into '>' and 'D' into '<' and it just passed 733E here.

    → Reply
»
2 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Can someone please explain the flaw in my logic for C?

  1. In the first n-1 queries, find the index with the maximum number from 0...n-1. (done by querying "? a a b b")
  2. Once you have found the maximum, simply OR it with the rest of the indices and output the one which gives the best results. (done by querying ? maximum best maximum current, where current is the current index being handled and best the one which has been the maximum thus far.)
→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    ah no way I didn't even think about oring them with each other. I think the flaw is that or includes duplicate bits and so it would make for a suboptimal XOR.

    → Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it +9 Vote: I do not like it

    for 0,1,2,3 3 will give maximum or with all 4 index, how'll you handle it?

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

    You have to handle the case when the ORs are the same, then take the smaller element. For example, n = 8, 7|6 == 7|0, your solution would return the positions of 7 and 6.

    → Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    Note that the solution requires the maximum XOR. So there are multiple indexes that give the best results with OR with the maximum element, but only one of them gives the best result when XORed with the maximum, which we output as solution.

    → Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    There are potentially multiple indices i such that max value OR i yields the maximum answer. Think about which of these indices will yield the maximum answer for XOR.

    Spoiler
    → Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can someone pls explain an approach to Div 2 C?

→ Reply
  • »
    »
    2 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it
    • Find x such that a[x] is maximum
    • Find all y such that a[x] | a[y] is maximum, store all those y in a vector
    • Among all y you found, find the smallest a[y]

    The answer is x and y.

    → Reply
    • »
      »
      »
      2 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      That is pretty clever, I didn't even consider oring the same element lol. Thanks

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

      can you share the intuition behind this

      1.We can use n-1 to find max value

      2.how do you handle for multiple ORs when they are equal a[x]|a[y]

      3.why do we need x&y where a[y] is smallest

      W can have max ans as $$${2^{(msb+1)}-1}$$$

      → Reply
      • »
        »
        »
        »
        2 years ago, hide # ^ |
        ← Rev. 2  
        Vote: I like it 0 Vote: I do not like it
        1. Just handle the case when the jury response us with '='
        2. Among all y where a[x] | a[y], we need minimum a[y] because, let's think about those elements in binary representation.

        For example a[x] = 1001. Then there are only two a[y]: 0110, 0111. As you can see, those a[y] | a[x] produce the same result (which is 1111) but we choose the smallest ay as the answer because it has the SMALLEST NUMBER OF SET BIT. This is important because we could prevent 1 XOR 1 in some positions.

        → Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    I guess since we know all values (permutation 0..n-1) we can find the max xor, and then find values which give that target xor.

    → Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    The thing is, if you look at binary presentation of (n-1), and !(n-1) easy (not during the contest) to see, that !(n-1)<n-1 (we dont look at the bits greater than greatest bit of n-1), so if !(n-1) !(n-1) exist in permutation. Also easy to see that (n-1)^(!(n-1)) is the maximal xor we can get, and all what we must do it find n-1 and such index that (n-1)^p[index] maximal, we proved that p[index] = !(n-1). I think so

    → Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Nice problem Div2C/Div1A. Got the solution with 2 minutes remaining :(

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Solved Div1B in last 10 seconds. How can I improve my implementation?

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

Ok simple question for PROBLEM-B

if I had 2 paths previously and 3 NEW paths were found, what is the total no of possibilities?

A) 2+3=5
B) 2*3=6
C) 2^idk
D) Think outside the box

Testcase -
7
1111111
1101110

Ans is 11101110 probably, please HELP

My code Thanks!!

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    once you go down a thing you can do is go right

    → Reply
    • »
      »
      »
      2 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      This idea is genius!!

      Find Lex string and for each index
      check if top left+bottom right==lex string
      Implemented its code and it's working perfectly. Too bad I can't submit to check it.

      Thanks a lot, I can sleep peacefully now.

      → Reply
      • »
        »
        »
        »
        2 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        I'm pretty sure that idea of string comparison for each index will give you TLE though...

        → Reply
»
2 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

1B=https://mirror.codeforces.com/problemset/problem/733/E

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

It's NOT Div2, it's Div 1.5

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +20 Vote: I do not like it

So I guess Blogewoosh #5 (+ golden search to squeeze it) isn't intended for F?

→ Reply
»
2 years ago, hide # |
 
Vote: I like it -30 Vote: I do not like it

Terrible contest.I don't think this kind of competition is very interesting, even if the question setter feels that they have come up with something interesting.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

The problems are good, but I'm totally confused about what happend with cin in code 248946386, which I got TLE. When I replace cin with handwrite fast io in code 248950473 my program just run 249ms.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Is it possible to solve Div2B with dp?

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

can someone please check my code, gives error on pretest 2 248969661

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    if it helps, loop1 : i i j j to search a[ i ] = n-1; loop2: query (i j i cc) to find j such that (i or j is max) and a[j] in minimum among all such j

    → Reply
»
2 years ago, hide # |
← Rev. 6  
Vote: I like it +19 Vote: I do not like it

D1A/D2C: First query for the largest element, let it's index be i0, then query for indexes j such that (a[i0]|a[j]) is the maximum, finally in these j we find j0 such that a[j0] is the minimum, then (i0, j0) is the answer.

D1B/D2D: WLOG assume s[i]='<', then we do something like this: go left find the first '>' --> go right find the first '<' --> and so on... So if cnt1= the number of '>' to the left of i, cnt2= the number of '<' to the right of i, then if cnt1<=cnt2, we will turn back at all positions of '>' to the left and first cnt1 positions of '<' to the right, if cnt1>cnt2, we will turn back at all positions of '<' to the right, and first cnt2+1 positions of '>' to the left. Then we can calculate the answer by the sum of positions of points we turn back. (The contribution factor of points we turn back at left is -2, points we turn back at right is +2, and the start point is +1, the end point is +1 (if end at right border) or -1 (if end at left border))

D1C/D2E: Build a graph of n*(m+1) nodes with index (i, j) (1<=i<=n, 0<=j<=m). Then for all 1<=i<=n, 1<=j<=m, we add edges (i, 0) --> (i, j) with cost 0, (i, j) --> (i, 0) with cost c[i]. For each 1<=j<=m, we sort [1, n] by the value of a[i][j], and for adjacent (i1, i2) in the sorted array, we add edges (i1, j) --> (i2, j) with cost 0, (i2, j) --> (i1, j) with cost a[i2][j]-a[i1][j]. (So distance from (u, j) to (v, j) is the cost to let pokemon v to win pokemon u by attribute j) Therefore, go along the path (u, 0) -> (u, j) -> (v, j) -> (v, 0) means we let pokemon v beat pokemon u, then the answer is the distance from (1, 0) to (n, 0).

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

    D1D/D2F: This uses segment tree idea described here. The idea is that there are only $$$O(\log A)$$$ number of distinct prefix ORs/suffix ORs. so we will all of the possible suffix and prefix ors, along with the maximum of the other array in those positions (which corresponds to maximum of the shortest prefix/suffix with equal or). We can merge nodes suffix and prefix while keeping them distinct, and update the answer for node with brute force in $$$O(\log^2 A)$$$ resulting in $$$O(q \log n \log^2 A)$$$ but if we use two pointers to update the answer, the overall complexity will be $$$O(q \log n \log A)$$$ and this is fast enough to pass. Beware that creating too many vector<pair<int,int>>s could be too slow, that's why it's better to use basic_string (I described this here).

    → Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Does this contest allow hacking?

→ Reply
»
2 years ago, hide # |
 
Vote: I like it -16 Vote: I do not like it

(The problem) is very well done, don't do it next time.

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it +15 Vote: I do not like it

    at least write your real opinions about the problems instead of taunting the authors :/

    → Reply
    • »
      »
      »
      2 years ago, hide # ^ |
       
      Vote: I like it +1 Vote: I do not like it

      I was only joking, and if this offended you, I sincerely apologize. Additionally, it's just a humble opinion of mine that if a competition were to rank based on the speed of solving easy problems, due to the presence of highly difficult problems acting as a divide, it might be considered somewhat biased.

      → Reply
      • »
        »
        »
        »
        2 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        Actually you're right, we received feedbacks from the testers that the problemset is even easier than usual CF rounds, and we never expected this level of difficulty for the participants ...

        → Reply
»
2 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

I'm sorry but is Div.1 B similar to contest 733 problem E?(✺ω✺)

→ Reply
»
2 years ago, hide # |
← Rev. 2  
Vote: I like it +16 Vote: I do not like it

would have been great to have subtask for Div1B which allows n^2 solution. then participants can decide whether they spend time implementing full solution on not. being forced to implement this is not great experience... (yeah yeah i know im bad in implementation, but IMO this change would have improved contest experience for a lot of participants)

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

tourist might come back to top 10 rated today :) :)

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

Div2 is so difficult. I dont like it.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

what is the best way to test my interactive problem's code.

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    make a function to calculate the responses for your queries and then comment the function while submitting.

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

    Answer your own queries

    → Reply
    • »
      »
      »
      2 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      DuongNeverAlone Bro if i want to reach expert in 6-8 months! What should be my strategy? how many questions per day i have to solve? (i started c++ last year) I'm ok-ok at implementation, basic maths, and techniques like pfsum, sliding window etc

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

        It's not really important how many problems you solve per day. I mean, it is still good if you manage to solve such huge problems in a day, but it is more crucial to concentrate on problems which are higher than your current level, then you can study more topics from those. Otherwise, solving easy problems literally give you nothing much.

        By the way, if you want to give you an exact numbers, I think 5 to 6 problems should be fine.

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

    Make a template with something like

    void solve<I>() {
  if I::query(a,b,c,d) == ...;
}

struct Mock {
  permutation = ...
  static int query(a,b,c,d) {
   return a|b > c|d;
  }
}

struct Codeforces() {
  static int query(a,b,c,d) {
    cout << "? " << a <<...;
    cin >> response;

    return ...;
  }
}

int main() {
  solve<Mock>();
  // solve<Codeforces>();
}

    Example in rust.

    → Reply
»
2 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Can div2B be solved with DP to find the path's string?

My trial: Submission Div2B

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Any idea why this fails for Div2 C? 248972248

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +26 Vote: I do not like it

wait...so div1B/div2D and CF733E are completely equal?

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +9 Vote: I do not like it

Wanted to thank all the authors for coming up with a very nice problem set. Especially problem C, which helped me realize that similar to MinMaxFlow, Dijkstra too is quite powerful when combined with carefully constructed graphs. Thank you for taking time to produce these problems. :)

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +19 Vote: I do not like it

Can the System Testing be resumed?

I am really curious how bad my F code would fail.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Why did the system test STOP

Are Mike playing Genshin Impact ???

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +9 Vote: I do not like it

I want to upsolve

→ Reply
»
2 years ago, hide # |
← Rev. 2  
Vote: I like it +10 Vote: I do not like it

For F you can binary search and check nonemptiness of disks intersection. How to do this in the simplest possible way? You recall the simplest possible algorithm to nonemptiness of halfplanes intersection https://blog.mitrichev.ch/2016/07/a-half-plane-week.html?m=1 and generalize it to circles. That is, take random order of circles and maintain the rightmost point of their intersection. If a new circle contains it, then we are good. If not, then this point is on this circle and we intersect it with all previous ones in O(i) time (where we are considering i-th circle right now). Amounts to O(n) time, so with binary search on top O(n log n) for the full problem

And of course such problem had to be on a round in which I wanted to participate, but forgot >.<

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

No one told me that it will be Div 1.25 ;/

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Why does this give tle for problem B is it O(n^2) because of the iterators? 248960076

Can somebody provide insights? Thanks

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Funny how i misread C's statement and solved it for increasing jumps and still got AC

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Nice contest and Nice problem C.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it -13 Vote: I do not like it

screwed up too badly on b, spend an hour and half on hashing string & bitset & dp shit. endup +6 wrong submission until finally realize [spoiler] and receive 300/1000pt. 🙃

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

was a similar problem to div2d on IMO?

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

It's a nice Div.499122177

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

Wonderful round!I became master!

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

Solved ABC. Thanks a lot for the round wuhudsm chromate00 Psychotic_D MagicalFlower and all testers!

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

$$$O(n)$$$ two pointer simple solution for D1B/D2D. https://mirror.codeforces.com/contest/1937/submission/249021364

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

In this contest https://mirror.codeforces.com/contest/1936/problem/B and https://mirror.codeforces.com/problemset/problem/733/E are a question.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Nice Round..

→ Reply
»
21 month(s) ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

LOL

→ Reply