Psychotic_D's blog

Codeforces Round 930 (Div. 1, Div. 2)
By Psychotic_D, 8 months 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 orzdevinwang
3 ugly2333
4 tourist
5 998kover

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

»
8 months ago, # |
  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
»
8 months ago, # |
  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
»
8 months ago, # |
  Vote: I like it +33 Vote: I do not like it

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

→ Reply
»
8 months ago, # |
  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
»
8 months ago, # |
  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
»
8 months ago, # |
  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
»
8 months ago, # |
  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
»
8 months ago, # |
  Vote: I like it +21 Vote: I do not like it

As a tester, may positive delta be with you.

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

as a tester i can assure that problems are very nice

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

OMG! Another Psychotic_D round!

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

so many testers !

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

Adding tibinyte as newbie tester should be illegal 🤥

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

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

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

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

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

OMG! k1r1t0 is tester!

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

Good luck to all!

→ Reply
»
8 months ago, # |
  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
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I hope to welcome you to cyan!

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

      Thank you so much my friend. Its good to know that I am always loved no matter where I am or what my color is. I hope to see you green after this contest!

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

    Wake up to ... hm hm. Wish you good luck!

    → Reply
»
8 months ago, # |
  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
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    No. This is two of the rounds of all time.

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

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

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

amenotiomoi orz tester <3

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

vikram108 sir orzzzzz

→ Reply
»
8 months ago, # |
← 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
»
8 months ago, # |
  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
»
8 months ago, # |
  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
»
8 months ago, # |
  Vote: I like it +70 Vote: I do not like it

Once in FOUR years

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

.

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

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

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

OMG! Another Psychotic_D round!

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

The interactive problem is for div1 or for both division?

→ Reply
  • »
    »
    8 months ago, # ^ |
      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
»
8 months ago, # |
  Vote: I like it +16 Vote: I do not like it

How so pro Psychotic_D ser?

→ Reply
»
8 months ago, # |
  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
»
8 months ago, # |
  Vote: I like it +20 Vote: I do not like it

Damn, I thought chromate was bot.

→ Reply
»
8 months ago, # |
  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
»
8 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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

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

grecozo will win the round, pin this.

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

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

    *gets a negative delta and again "sadness,boredom,depression,loneliness,social-anxiety"

    and the loop continues..

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

It's too early for that.

→ Reply
»
8 months ago, # |
  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
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it
Spoiler
→ Reply
»
8 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Abhishek_Srivastava , the tester , orz

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

Is there a photo of MagicalFlower?

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

Orz chromate00 for being a problemsetter.

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

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

OMG! They are mewing!

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

deleted

→ Reply
  • »
    »
    8 months ago, # ^ |
    ← Rev. 5   Vote: I like it -15 Vote: I do not like it

    I'm sorry about that

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

      memes are called memes because many people share them. If you are against this, go to a platform where you can hold copyrights. Let us have fun as the codeforces community.

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

I loved the way you thanked the participants.

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

Goodbye, cyan ;(

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

Hope I will reach to 1400+

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

Is MagicalFlower the up right one on the photo?

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

No offence to anyone.

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

    Nah nah bro, The Russians should be: I will make a Div.1 round.

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

I'm waiting for this. Scoring by points is more interesting than giving penalties :)

→ Reply
»
8 months ago, # |
← 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
»
8 months ago, # |
  Vote: I like it +32 Vote: I do not like it

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

    dark theme looks so good awwwwwwwww,how did you get that!!

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

      There is an extension for chrome, dark reader.

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

chromate00 be like :)

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

Downforces incoming

→ Reply
»
8 months ago, # |
← 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
»
8 months ago, # |
  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
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

looking forward to photo of MagicalFlower. very handsome

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

An interactive problem in Div.2 C? How rude!

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

B is bad

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

whats wrong with this round??

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

One of the worst Div. 2 ever

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

What is wrong with the third problem goddamn

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

try something other than creating contests

→ Reply
»
8 months ago, # |
  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
»
8 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Binaryforces.

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

Maybe I have forgotten how to make correct submissions to problems

→ Reply
»
8 months ago, # |
  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
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Bitwiseforces

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

Nice problem C

→ Reply
  • »
    »
    8 months ago, # ^ |
      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
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      string hashing

      → Reply
    • »
      »
      »
      8 months ago, # ^ |
      ← 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
»
8 months ago, # |
  Vote: I like it +14 Vote: I do not like it

Too Hard.

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

observation force

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

why so hard b

→ Reply
»
8 months ago, # |
  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
»
8 months ago, # |
← 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
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
        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
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how to implement B

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
      ← 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
  • »
    »
    8 months ago, # ^ |
      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
  • »
    »
    8 months ago, # ^ |
      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
»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

submit C in last 10 second phew~

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

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

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

ez minus delta

→ Reply
»
8 months ago, # |
  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
»
8 months ago, # |
  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
»
8 months ago, # |
← 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
»
8 months ago, # |
← Rev. 3   Vote: I like it +80 Vote: I do not like it

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

→ Reply
  • »
    »
    8 months ago, # ^ |
      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
»
8 months ago, # |
  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
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Which has produced the maximum OR thus far*

    → Reply
  • »
    »
    8 months ago, # ^ |
      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
  • »
    »
    8 months ago, # ^ |
      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
  • »
    »
    8 months ago, # ^ |
      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
  • »
    »
    8 months ago, # ^ |
      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
  • »
    »
    8 months ago, # ^ |
      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
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone pls explain an approach to Div 2 C?

→ Reply
  • »
    »
    8 months ago, # ^ |
    ← 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
    • »
      »
      »
      8 months ago, # ^ |
        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
    • »
      »
      »
      8 months ago, # ^ |
      ← 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
      • »
        »
        »
        »
        8 months ago, # ^ |
        ← 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
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    find the i that is max value in a permutitation

    then find the min(j) that i|j is maximum.

    → Reply
  • »
    »
    8 months ago, # ^ |
      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
  • »
    »
    8 months ago, # ^ |
      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
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

→ Reply
»
8 months ago, # |
← 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
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
        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
      • »
        »
        »
        »
        8 months ago, # ^ |
          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
        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yeah, I checked out other solutions and now I understand how to compare indices instead of the entire string.

          Man this was tough for me, doubt I could come up with such a slick solution in the contest.
          Well learned something new so cool :)

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

          you can use string hashing to to compare each index in O(1)

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

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

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

It's NOT Div2, it's Div 1.5

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

My Screencast for A and B problems: https://youtube.com/live/IU6Zqy5LGB4 This was private during the contest. Hope it helps someone.

→ Reply
»
8 months ago, # |
  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
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

A -> find nearest power of 2 which is <=n

b -> find first index where mat[0][i]=='1'&&mat[1][i-1]=='0', this means we have to move from up to down before this index let's call it as x. Now iterate from x to 0 and check if mat[0][x]==mat[1][x-1] then we increase the cnt and if we find a index where mat[0][x]=='0'&&mat[1][x-1]=='1' then we stop iterating.

→ Reply
»
8 months ago, # |
  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
»
8 months ago, # |
  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
»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Is it possible to solve Div2B with dp?

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

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

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

      Is the problem solvable by doing just simple dfs?Just expanding the path if it is giving lexicographically smaller ?

      → Reply
»
8 months ago, # |
← 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
  • »
    »
    8 months ago, # ^ |
    ← 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
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Does this contest allow hacking?

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

    You can only hack during contest time in div. 2 if it is not educational round

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

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

→ Reply
  • »
    »
    8 months ago, # ^ |
      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
    • »
      »
      »
      8 months ago, # ^ |
        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
      • »
        »
        »
        »
        8 months ago, # ^ |
          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
»
8 months ago, # |
  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
»
8 months ago, # |
← 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
»
8 months ago, # |
← Rev. 3   Vote: I like it +15 Vote: I do not like it

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

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

can someone tell me why my solution didn't work 248971756

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

Div2 is so difficult. I dont like it.

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

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

→ Reply
  • »
    »
    8 months ago, # ^ |
      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
  • »
    »
    8 months ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    Answer your own queries

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

      DuongForeverAlone 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
      • »
        »
        »
        »
        8 months ago, # ^ |
        ← 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
  • »
    »
    8 months ago, # ^ |
    ← 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
»
8 months ago, # |
  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
»
8 months ago, # |
  Vote: I like it -17 Vote: I do not like it

i changed my mind

its bad contest ....

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

    why?

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

      B div 2 should be C i think its hard to B

      because every one is going to think about dp

      and for gready takes alot of thinking

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

        i was thinking about dp too :"(

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

          that is what i am saying

          problem can be solved dp or gready should be C not B

          and D should be interactive

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

Any idea why this fails for Div2 C? 248972248

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

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

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

    exactly, just change "U" with ">" and D with "<"

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

    The experience was not good. :(

    Within a few minutes after the end of this round , I saw many people saying that they are identical problems.

    → Reply
»
8 months ago, # |
  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
»
8 months ago, # |
  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
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why did the system test STOP

Are Mike playing Genshin Impact ???

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

    I think he is not playing genshin impact, but maybe he is playing Honkai: Star Rail right now!

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

Stuck system testing is giving me anxiety rn. Just wishing that B passes.

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

I want to upsolve

→ Reply
»
8 months ago, # |
← 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
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Skill issue, bro

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

    actually we had that in one of our tester's solutions, it gets WA due to not sufficient precision and/or bad epsilon evil laugh

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

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

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

The system testing is resuming.

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

What would be the expected ratings for B and C today? For someone who solved B it felt like a 1200 to 1300 rated problem to me.

→ Reply
»
8 months ago, # |
  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
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    string addition is O(n)

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

    Aww man, this is a nice solution! But, within the loop, constructing the string s1 takes O(n) time because it involves creating substrings.

    Try alternate methods, don't add string, rather try to "Append" them. I'll see if I can provide you with a solution by tomorrow. I have an exam in a few hours ;/

    → Reply
»
8 months ago, # |
  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
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice contest and Nice problem C.

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

3 rd question in div 2 was not anything but nuisance

→ Reply
»
8 months ago, # |
  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
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

was a similar problem to div2d on IMO?

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

It's a nice Div.499122177

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

Wonderful round!I became master!

→ Reply
»
8 months ago, # |
  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
»
8 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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

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

Very weak pretest of Div2 B, my solution failed system test just because i didn't declare the array globally. It should have atleast one pretest where n = 200000.

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

Thanks a lot for the round.

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

I think contest going to be greattt!!

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

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

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

Done.

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

I have received a message from system that I have submitted solution of problem 1937B similar to many other users. I want to assure that I have done no copying in my senses if solutions are similar they might be due to same logic application I am also receiving message that my password has been compromised of which I will attach screen shot , it may have happened due to it. Although my rating has not been decreased but I do not want to be out of contest. I have made solution with lot of effort if it has been taken due to password breach or some other issue I don't want to get out of contest link to my solution is https://codeforces.net/contest/1937/submission/248943702 please do not do me out of contest @MikeMirzayanov.I do not want my account to get banned too.I have also solved 3rd problem of that contest and no fingers have been raised to its solution if I copy 2nd problem of div 2 how could I have solved 3rd on my own despite it being much tougher.

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

It was a coincidence that has occurred that our both codes have come out similar. There was no Intentional sharing of code or leakage happening

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

    This is inline with the message that I recieved for the solution of problem 1937B that it is similar with other users. The solution was thought of completely by me and I am ready to explain it as well and the thought process behind getting it. It took effort to make this solution, please do not remove from the contest @MikeMirzayanov.

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

Nice Round..

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

It's also about helping others, I can't do anything from here

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

I don't know why ,first I got plagiarized and then got rated for the same contest.

[contest:https://codeforces.net/contest/1937]

If my contest got skipped why I got -145 rating . Please help me , if it is a bug please let me know.

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

lol

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

LOL

→ Reply