Блог пользователя Psychotic_D

Автор Psychotic_D, 9 месяцев назад, По-английски

"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
  • Проголосовать: нравится
  • +487
  • Проголосовать: не нравится

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

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 ;)

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

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

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

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

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

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

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

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

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

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

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

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

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

As a tester, may positive delta be with you.

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

as a tester i can assure that problems are very nice

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

OMG! Another Psychotic_D round!

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

so many testers !

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

Adding tibinyte as newbie tester should be illegal 🤥

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

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

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

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

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

OMG! k1r1t0 is tester!

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

Good luck to all!

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

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

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

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

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

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

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

amenotiomoi orz tester <3

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

vikram108 sir orzzzzz

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

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)!

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

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

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

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!

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

Once in FOUR years

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

.

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

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

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

OMG! Another Psychotic_D round!

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

The interactive problem is for div1 or for both division?

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

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

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

How so pro Psychotic_D ser?

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

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

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

Damn, I thought chromate was bot.

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

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

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

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

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

grecozo will win the round, pin this.

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

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

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

    and the loop continues..

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

It's too early for that.

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

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

And also Good luck for everyone!

»
9 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Spoiler
»
9 месяцев назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Abhishek_Srivastava , the tester , orz

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

Is there a photo of MagicalFlower?

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

Orz chromate00 for being a problemsetter.

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

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

OMG! They are mewing!

Spoiler
»
9 месяцев назад, # |
Rev. 2   Проголосовать: нравится -21 Проголосовать: не нравится

deleted

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

I loved the way you thanked the participants.

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

Goodbye, cyan ;(

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

Hope I will reach to 1400+

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

Is MagicalFlower the up right one on the photo?

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

No offence to anyone.

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

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

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

HAPPY LEAP DAY 2024 ROUND.

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

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

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

chromate00 be like :)

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

Downforces incoming

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

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

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

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

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

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

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

looking forward to photo of MagicalFlower. very handsome

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

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

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

B is bad

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

whats wrong with this round??

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

One of the worst Div. 2 ever

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

What is wrong with the third problem goddamn

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

try something other than creating contests

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

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

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

Binaryforces.

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

Maybe I have forgotten how to make correct submissions to problems

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

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.

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

Bitwiseforces

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

Nice problem C

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

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

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

      string hashing

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

      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

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

Too Hard.

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

observation force

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

why so hard b

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

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

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

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).

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

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

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

      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.

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

    how to implement B

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

      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

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

    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.

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

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

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

submit C in last 10 second phew~

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

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

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

ez minus delta

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

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

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

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

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

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

»
9 месяцев назад, # |
Rev. 3   Проголосовать: нравится +80 Проголосовать: не нравится
  • »
    »
    9 месяцев назад, # ^ |
      Проголосовать: нравится +22 Проголосовать: не нравится

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

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

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.)
  • »
    »
    9 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Which has produced the maximum OR thus far*

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

    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.

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

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

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

    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.

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

    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.

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

    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
»
9 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone pls explain an approach to Div 2 C?

  • »
    »
    9 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    • 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.

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

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

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

      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}$$$

      • »
        »
        »
        »
        9 месяцев назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
        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.

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

    find the i that is max value in a permutitation

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

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

    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.

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

    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

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

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

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

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

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

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!!

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

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

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

      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.

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

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

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

          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 :)

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

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

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

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

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

It's NOT Div2, it's Div 1.5

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

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

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

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

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

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.

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

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.

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

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.

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

Is it possible to solve Div2B with dp?

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

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

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

    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

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

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

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

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).

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

    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).

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

Does this contest allow hacking?

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

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

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

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

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

      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.

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

        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 ...

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

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

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

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)

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

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

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

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

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

Div2 is so difficult. I dont like it.

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

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

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

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

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

    Answer your own queries

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

      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

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

        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.

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

    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.

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

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

My trial: Submission Div2B

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

i changed my mind

its bad contest ....

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

Any idea why this fails for Div2 C? 248972248

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

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

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

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

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

    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.

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

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. :)

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

Can the System Testing be resumed?

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

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

Why did the system test STOP

Are Mike playing Genshin Impact ???

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

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

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

I want to upsolve

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

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 >.<

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

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

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

The system testing is resuming.

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

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.

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

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

Can somebody provide insights? Thanks

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

    string addition is O(n)

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

    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 ;/

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

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

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

Nice contest and Nice problem C.

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

3 rd question in div 2 was not anything but nuisance

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

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. 🙃

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

was a similar problem to div2d on IMO?

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

It's a nice Div.499122177

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

Wonderful round!I became master!

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

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

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

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

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

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.

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

Thanks a lot for the round.

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

I think contest going to be greattt!!

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

Done.

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

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.

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

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

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

    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.

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

Nice Round..

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

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

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

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.

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

lol

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

LOL