When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

Kuroni's blog

By Kuroni, history, 3 years ago, In English

"Love" is a violent word.
"I love that about you..." Doesn't that just mean "If that changed, I wouldn't love you anymore?"
"Love" is a word that binds you.
— Touko Nanami —

Hi Codeforces!

Ari and I are pleased to invite you to participate in Codeforces Round 715 (Div. 1) and Codeforces Round 715 (Div. 2), which will be held at Apr/16/2021 17:35 (Moscow time). Each division will have 6 problems and 2 hours and 15 minutes to solve them.

Big thanks to the following people:

The round will be themed around Yagate Kimi ni Naru, which is a romantic anime/manga series. If you haven't picked up the series yet, I highly recommend you to do so after the round ;)

Please do read all of the problems, stay hydrated during the round, and solve as many as you can! Good luck have fun to everyone!

Here are the scoring distributions:

  • Div. 2: 500 — 1000 — 1500 — 2250 — 2500 — 3000
  • Div. 1: 750 — 1000 — 1500 — 2250 — 2250 — 4000

UPD1: The round has concluded! Congratulations to the winners from both divisions:

  • Div. 1:
  1. ecnerwala
  2. ksun48
  3. tourist
  4. Radewoosh
  5. maroonrk
  • Div. 2:
  1. wannahavealife (solved all problems!)
  2. traxex2
  3. _su1sen
  4. I_love_Ilya_Krasnov
  5. tsugu

UPD2: Editorial is up!

Thanks to everyone for participating in this contest, this has been a wild ride from start to finish. See you all next time!

  • Vote: I like it
  • +1371
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it +537 Vote: I do not like it

As a tester, they shoved weeb propaganda down my throat. I recommend participation.

»
3 years ago, # |
  Vote: I like it +144 Vote: I do not like it

As a tester, the problems are very elegant and you should participate in the round.

»
3 years ago, # |
  Vote: I like it +164 Vote: I do not like it

anime propaganda? i'll skip.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +539 Vote: I do not like it

    Round rotavirus skips -> good round

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

      are the rounds, in which rotavirus participates, bad?

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +18 Vote: I do not like it

        you've participated in his rounds so ...

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +30 Vote: I do not like it

        The implication is one-directional: there exist good rounds you participate in. But if a round is bad, then you necessarily participate in it.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +24 Vote: I do not like it

          But if a round is bad, then you necessarily participate in it.

          I'll participate in this one then

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          nah this is not interesting.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +29 Vote: I do not like it

          contrapositive geniosity

  • »
    »
    3 years ago, # ^ |
      Vote: I like it -40 Vote: I do not like it

    Anime is shit, change my opinion!

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    this was a wise decision....but XD

»
3 years ago, # |
Rev. 2   Vote: I like it -151 Vote: I do not like it

Wtf.Yagate Kimi ni Naru is a Shoujo Ai Anime. Shoujo ai is something related to yuri and yuri means Lesbian.

»
3 years ago, # |
  Vote: I like it +70 Vote: I do not like it

Now this is called a complete round, This round gives you anime recommendation(Yagate Kimi ni Naru) for dealing with post contest depression or celebration.

»
3 years ago, # |
  Vote: I like it +95 Vote: I do not like it

These bleeding weebs lmao

»
3 years ago, # |
  Vote: I like it +73 Vote: I do not like it

i never expected a timeline where bloom into you is getting a competitive programming adaptation

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +215 Vote: I do not like it

    Neither did I so I made it myself.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    completely shocked when I entered the main page, haha

»
3 years ago, # |
  Vote: I like it +29 Vote: I do not like it

Looks like anime will soon takeover the world :D

»
3 years ago, # |
  Vote: I like it +19 Vote: I do not like it

I like this round already

»
3 years ago, # |
  Vote: I like it +56 Vote: I do not like it

See the series "after the round". Given the round is based on this series, isn't there high chances that not that great memory would be associated with this series after the round is over? Kuroni

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +130 Vote: I do not like it

    The problems will be very good so no bad memories will be associated :sunglasses:

»
3 years ago, # |
  Vote: I like it +35 Vote: I do not like it

I confirm that Yagate Kimi in Naru is a wonderful lesbian/yuri Japen comic, I highly recommend it too :(

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the early score distribution : )

»
3 years ago, # |
  Vote: I like it +50 Vote: I do not like it

WEEB IN!!!

»
3 years ago, # |
  Vote: I like it +34 Vote: I do not like it

I think I need to code for counting the number of a's in neko_nyaaaaaaaaaaaaaaaaa

»
3 years ago, # |
  Vote: I like it +49 Vote: I do not like it

You say weebs, but all I see are people of culture. Respect!

»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Hope to perform my best till now, in this round!

»
3 years ago, # |
  Vote: I like it +66 Vote: I do not like it

So, when are we getting a round themed around AOT?

»
3 years ago, # |
  Vote: I like it +76 Vote: I do not like it

As a Japanese otaku, this is why I cannot retired from CF!
I hope the tasks are as amazing as Yagakimi.

»
3 years ago, # |
  Vote: I like it +71 Vote: I do not like it

Honestly saying I dont like of idea of round being theme based, I hope statements would be clear as daylight and wont involve these characters. From my side if one wants to make a round theme based simply name the problems as your fav anime/manga whatever and people will get the propoganda nothing more than that.

»
3 years ago, # |
  Vote: I like it +42 Vote: I do not like it

Oh, Vietnamese authors. Good job! Keep going your contributions. I hope that one day I can write a contest. Of course, I need to be purple at least first.

»
3 years ago, # |
  Vote: I like it +23 Vote: I do not like it

I think something went wrong here. In the post, it says that the contest last 2 hours and 15 minutes. In the register page, it says that just 2 hours.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    I believe the registration page is not updated yet. I will contact to fix the issue :)

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

As a "noob" tester. This round is very "balance" and very good. Wish all the participants have a positive rating! :)

»
3 years ago, # |
  Vote: I like it +35 Vote: I do not like it

.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

A round with anime propaganda? I'm in.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am very excited for this codeforces round because the Problemsetters are Ari and Kuroni.

»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

im trying to understand the blog & comments but i have no clue : (

»
3 years ago, # |
Rev. 3   Vote: I like it +14 Vote: I do not like it

Hope the Aquaman in me wakes up for some time during the contest instead of Aqua sama.

»
3 years ago, # |
  Vote: I like it -36 Vote: I do not like it

sir why does contest have lessbyan cartoon theme?????

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    You should be judged by KAMI SAMA for addressing an Anime as a cartoon :D

»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Being an otaku , very excited for this round.

I hope we will get more episodes of these kind of round XD

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Colorful testers :)

»
3 years ago, # |
  Vote: I like it -16 Vote: I do not like it

From Vietnam ưith love!

»
3 years ago, # |
  Vote: I like it -78 Vote: I do not like it

The comment is hidden because of too negative feedback, click here to view it

»
3 years ago, # |
  Vote: I like it +25 Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +19 Vote: I do not like it

A round? I prefer two matches in Dota 2.

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

    I prefer a positive delta change of > +50 in an Anime theme round XD

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

    you definitely mean one match of Dota 2 with Techies

»
3 years ago, # |
  Vote: I like it +30 Vote: I do not like it

I love how the scoring distribution is released so early. +1 from me. I also have another quote for you:

LOVE

"

»
3 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

HAPPY ANIME DAY!!!(15th April)

»
3 years ago, # |
  Vote: I like it +31 Vote: I do not like it

YagaKimi is brilliant. Contest setter has good taste.

»
3 years ago, # |
Rev. 2   Vote: I like it -86 Vote: I do not like it

.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Kuroni do you play Pokemon Planet? I once saw someone selling stuff in the trade chat named Kuroni and I was wondering if it was you. The anime theme of the contest further makes me think it might actually be you.

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

Haven't seen this many upvotes for a contest blog in ages . This contest was great.

»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Although I'm having a history exam on the next day, I can't wait to participate in this round! Hope that I could collaborate with you in future rounds Kuroni, maybe as a tester? Anyway, wish this round will goes perfectly!

»
3 years ago, # |
  Vote: I like it +30 Vote: I do not like it

Kuroni's stand be like

Meme
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

A romantic contest ... I like it

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Don't judge a book by it's cover.

    Spoiler
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I just started that anime ... Seems pretty good

»
3 years ago, # |
  Vote: I like it -24 Vote: I do not like it

Finally a contest with Div2 B = 1000 score! No Alan Turing level mathematics I expect!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope I remain EXPERT after this contest!.

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

Score of Div2. D is scaring me !!

Spoiler
»
3 years ago, # |
  Vote: I like it +22 Vote: I do not like it

How many problems are common between both divisions?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    According to the score distribution seems that Div2 D = Div1 A

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How can it be compared from score distribution?

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The usual score distribution is: 500 — 1000 — 1500 — 2000 — ...

        in this round Div2 D = 2250 and Div1 A = 750

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    Div2 D = Div1 A

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

hlw guys plz tell me how to make a user my friend???

»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Hopefully I will become pupil after this contest.

»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

I wish i would solve atleast 3 to 4 problems in this contest ;-;

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

A contest on Naruto also:)

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

All the best every one.

»
3 years ago, # |
  Vote: I like it -6 Vote: I do not like it

I am Sooooooooooooo Excited ❤

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Dmitry cdkrot Sayutin likes this post 'cause it's propaganda for two girls to participate in SIS.

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I hope they make an Attack on Titan round when the last episode airs next year >.>

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    chapter 139 had me in tears ngl,eremika forever!!

»
3 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Have a great Rating Change :)

»
3 years ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

sdfoiSF

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

WA on pretest 5

»
3 years ago, # |
  Vote: I like it +15 Vote: I do not like it

I got to say the pictures that explain the examples are lovely.

»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

what the heck is pretest 5 of div2C

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how to solve div2C?

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

      I solve it using dp,i sort the distinct value of all input,then we consider the last operation we can make , neither we put the max or min value , then dp[i][j] = min(dp[i+1][j] + count[value[i]] * diff,dp[i][j-1] + count[value[i]] * diff),here is my code: dp solution

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

    It is the place where green's rest.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    try 8 1 2 4 4 5 9 9 10

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Same! I simply traversed a sorted circular array n times for each i and a reverse sorted circular array. Thought it was right, but got stuck on pretest 5

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve Div 1 A ( Binary Literature ) ?

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

    Choose two strings which have at least $$$n$$$ zeros or ones in common (clearly at least one such pair must exist). Take $$$n$$$ of these common, then just place the remaining $$$2 \times n$$$ elements in the same relative order.

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

    Out of the 3 strings, you can find a pair of strings such that both have >= n zeroes or both have >= n ones. Treat the 0s (or 1s in other case) as common subsequence. Now you can combine these 2 strings (Leaving this as an exercise).

»
3 years ago, # |
  Vote: I like it +15 Vote: I do not like it

I feel like I have been getting better and then I fail to Div 2C? How to solve D2 C?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    DP

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Can be solved using DP. At the end of the altered array you have two options either max(1--n) or min(1--n) for optimal ans. So at each step you have two options. Lets make a vector of all speeds in a sorted manner and solve the dp,

    dp(l,r) = min(dp(l+1,r), dp(l, r-1)) + v[r]-v[l]; ans = dp(0, n-1);

    Submission Link

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

    Since it is about the differences we can need to sort a[].

    dp[i][j] is min cost to have runner i to j of the sorted list started in any order.

    dp[i][i]=0;

    for all i+1<=j:

    dp[i][j]=min(dp[i+1][j]+a[j]-a[i], dp[i][j-1]+a[j]-a[i])

    So, we start with any runner, and take as next the next faster or slower one.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    At each point you've to either place group of smallest elements of group of largest elements in the end (try to prove yourself).

    So you do a dp[l][r] on the sorted list of distinct elements and at each point decide to place either all a[l]s or all a[r]s in the end of the final list and then do l++ or r-- and continue

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sort the speeds then compute the minimum cost to include racers with speeds si...sj.

    • Initialize dp[i][i] = 0 for all i (cost of including single racer is 0)
    • At each step k, dp[i][i+k] is the minimum cost of including all racers between i and i+k, which can be computed from the previous dp[i][i+(k-1)] and dp[i+1][(i+1)+(k-1)]
    • You can actually use 1D DP because at any given k you're only using the results from k-1 before overwriting them.
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I solve it using dp,i sort the distinct value of all input,then we consider the last operation we can make , neither we put the max or min value , then dp[i][j] = min(dp[i+1][j] + count[value[i]] * diff,dp[i][j-1] + count[value[i]] * diff),here is my code: dp solution

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can some one please explain how to solve Div2 problem D

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it +6 Vote: I do not like it

    Suppose there are two strings $$$a$$$,$$$b$$$ such that number of zeros in $$$a$$$ and $$$b$$$ are greater than $$$50$$$%. Then we can choose string $$$a$$$ and insert number of $$$1$$$'s in string $$$b$$$ in string $$$a$$$ such that $$$b$$$ is substring of whole string.

    Same case when number of $$$1$$$'s in $$$a$$$ and $$$b$$$ are greater than $$$50$$$%.

    When both $$$1$$$ and $$$0$$$ are equal to $$$50$$$% in both $$$a$$$ and $$$b$$$ then also it can be solved with same logic.

    Let say $$$a=11111100,b=11110000$$$ then final string will be $$$111100001100$$$

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Since there are 3 strings, we can always pick 2 out of them, such that either both of them have at least n times 0 or both of them have ar least n times 1. Let's call this the mode. It is 0 in the first case and 1 in the second case. Then we can create a string with n times the mode. Now we matched at least n characters from the first string, and at least n characters from the second string. We are left with n characters from the first and n characters from the second string. We can simply add them by traversing both strings to get a string of length at max 3n.

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

    we can prove the at least there two strings which is have at least n characters are same , '0' or '1',for any case ,we assume it is '1',we just can replace n '1' in any string with another string ' s '1',don't change the order of other characters ,we can make it;here is my code: my code

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Div2B?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Couldn't participate in the contest today. But upon reading , you just traverse through the string and check that at no point , the count of M should be greater than the count of T. then repeat the same thing , while going backwards , that is from n-1 to 0. And then just see if the count of T is 2 times the count of M. If the string satisfies all the above conditions , print yes

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Yes, saw some solutions. But, why does this works?

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        while traversing from start..for every M..there must be atleat one T before it..similarly while traversing from back

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Sent you a message. Cause I am unrated , its not allowing to comment more than once in 10 mins

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        What special about "TMT", for every M there is one T to the left and 1 T to the right. So if we check that count of Ts is twice the count of Ms and check whether each M has a T to the right and left by traversing the string both ways, we will have the answer.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    we can check two pass from left to right and from right to left,every pass ,we must make every m can get a t in it's front ,otherwise we can't make it ,by the way ,we always have the number of 'T' is two times of the number of 'M'

»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Was DIV2 D much easier than DIV2 C ? It was just case analysis right ? If we have two strings with 50% 0 and 50% 1 then we are done . Or else if we have two strings with number of 0 greater than 50% then also we can combine them.

I read it in last moment and found that implementation was bit difficult else it was easier than DIV2 C.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    I feel like implementation is the biggest pain in Div2D / Div1A, took 5-10 mins to come up with the solution, 20-30 mins to code it correctly. Maybe I'm just bad at implementation.

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

      I think an easy implementation can be done with two pointers. Once we find pair of strings with a bit appearing $$$>= n$$$ times, iterate both string. If the bit match, append the bit to the answer and advance both pointers. Else append the bit that appears $$$<= n$$$ times, and advance its pointer.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      agree with you,c is much easier to code

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Read every submission from jiangly and your implementation will become CLEAN and FAST.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Thanks, I will follow him. I also think that removing fear from mind that "i cannot solve D if i can't solve C" is also very important. If i would have read D well before time i would have got positive delta.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone help with div2 D? Couldn't get it working during contest.

  • »
    »
    3 years ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    Hints: There must have 2 string where no of 0/1 in both two string >=n.

    approach:

    when any of two string no of 0/1 >=n. Then take one string fully , so other string n element already taken, so taken the rest <=n elements of the other string with some tricks which was not common. its always <=3n operation.

    implementation

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone can tell me why my solution for D/Div2 get WA?

113255849

»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Aw hell, I wasted so much in C. I knew the main idea right away — find unassigned connected components, if they don't form a forest then compress them into vertices and find the weight of MST there, otherwise build the tree and add min(XOR, for each unassigned edge the smallest weight of a non-MST edge that crosses it). I just didn't go for the straightforward implementation that uses $$$N \lt 900$$$ and finds those smallest weights of non-MST edges crossing all MST paths, but tried other things that I thought would be simpler and fast. Got a lot of WAs and wasted like an hour, only to implement that $$$O(N^2)$$$ in the end.

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

    A simpler solution (at least in my mind) with complexity $$$O(m\log m)$$$:

    • If $$$\frac{n(n-1)}{2}-m\ge n$$$, answer is just MST.

    • Else, $$$n=O(\sqrt{m})$$$. Naively process will give $$$O(m\sqrt{m}\operatorname{dsu}(n))$$$, but note that only $$$n$$$ out of these $$$m$$$ edges are useful (run MST with only fixed edges, only used edges are useful). Now the complexity is $$$O(n^2\operatorname{dsu}(n))=O(m\operatorname{dsu}(n))$$$.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Tbh my solution is simple — build MST with $$$N-1$$$ edges, list all paths in the form $$$(root,v,parent(v),depth(v))$$$, sort them by depth = length, make a table $$$W_{u,v}$$$ for minima of weights of non-MST edges crossing paths $$$(u,v)$$$ and do $$$W_{par(v),v} = min(W_{par(v),v}, W_{root,v})$$$ for all paths.

      What I was going for was more like print cost of MST + min(XOR, minimum of non-MST edges), which failed, but it's not obvious to me why it failed because I tried making a simple counterexample and found out it wasn't a counterexample.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The same general approach succeeded for me, although I used a different method for finding the minimum non-MST edge (just find LCA and check how many non-assigned edges are on the path to LCA). So maybe it was just a bug.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I made a multiset of weights strictly smaller than XOR, then removed weights as I was building the MST. Hard to make a mistake there, it's like 5 lines and I avoided obvious pitfalls like empty multiset or removing by value instead of by element.

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            The exact approach worked for me. So the answer is MST + min(XOR, minimum of non-MST edges). Except for non-MST edges you have to check that there is at least 1 added edge ( e.g. edge not present in the original graph ) , for that I used a similar approach to the one KADR mentioned, I have LCA with binary jumping which keeps the minimum weight edge from a node to its parent in MST.

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

              EDIT: Found my mistake.

            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
                Vote: I like it -18 Vote: I do not like it

              Sounds like your "exact approach" needs more effort than anything I tried. If you simplify DFS/DP-ing all paths into one formula and then complexify that simple formula into LCA with binary jumping, you didn't simplify...

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

                I meant the exact idea for solution. anyway...

              • »
                »
                »
                »
                »
                »
                »
                »
                3 years ago, # ^ |
                Rev. 3   Vote: I like it 0 Vote: I do not like it

                Regarding the "simplifying", personally I think it is better (easier) to copy paste binary jumping and use it, since you need to modify just a few lines, rather than trying to code something unusual that makes use of the specific constraints of the problem. Also, who says I am trying to simplify, I am trying to solve the problem with less code or alternatively with less effort.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Well, writing something well-known is the right approach and the one I didn't take until near the end. However, why start with deciding for a formula, then figure out that there's an exception to that formula and you need to use some more standard code-y approach, when you can ignore the formula and do the standard code-y approach from the start...

                  Note that I'm just repeating my first post now.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Because that s the first thing that came to mind in contest. Also I think you might be comparing oranges and apples here, “the standard code-y approach” part of my solution is mostly copy paste.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Doesn't really matter if copypaste or quickly written from memory, the difference I'm focusing on is nice solution vs boring solution, specifically that I tried a nice solution and failed so I had to go with a boring one.

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

      Oh so you mean for the unweighted O(N) edges, we just need to iterate on the MST of the given edges? PS : Also I think O(M sqrt(M) * alpha) might pass cause alpha might be quite small for union find.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did this:

    Apply Prim/Kruskal with the difference that unassigned edges' weights will be assigned "on the go".

    On each iteration, if there is more than one available edge which is unassigned, it gets value 0. If there is exactly one edge which is unassigned, it gets value XOR.

    I got WA for my submission :( but I'm not sure if I have a bug or the idea is wrong.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That doesn't sound right at first glance.

»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

The hardest part of Div2-C is

Spoiler
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    I don't think that figuring out that it was dp was the hardest part since it was somehow obvious from constraint. Figuring out how to do the transitions was hardest.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      So you are saying that you can know whether a problem is brute force or dp by just looking at the constraint.

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

        No, but we can give few minutes to think if this problem can be solved by DP or brute force.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Have u even attempted this question , cuz i can't find any submission

»
3 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Nice round! Love the animated sample explanations.

»
3 years ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

Me before contest- "Hope I'll become expert today for the first time"
Me after contest- "Nevermind! I'll regain my specialist in next contest" (-_-)

»
3 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Thank you for the contest. Really liked problems B and C even though I messed up and wasted an hour on C. Towa Maji Tenshi!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The most upset moment is that I always get TLE for problem C in div2 even I can do this. Time limit exceeded in Pretest 13 (for pypy3)

»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Can anyone tell what bug is there in this code ? div2D/div1A (Binary Literature)

Code Link

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

Is it just me or B's are getting harder these days? its heartbreaking after a year of hard work T_T

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why problem C use dp ? I think it should be greedy。

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Why is the following algo wrong:? Given $$$s1$$$ and $$$s2$$$, if they have $$$x$$$ positions having different characters => number of same characters $$$2*n - x$$$

from i = 0 to 2*n:
    if s1[i] == s2[i]:
        print(s1[i])
    else
        print("01")

if $$$x <= n$$$, the string printed above has $$$length <= 3*n$$$. It can be proved. Getting WA on pretest 5 :(

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    0101
    1010
    Your algo will print 01010101 (length 8 and 3*n = 6)

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

      The third-string will be used here. At least one of 0101 and 1010 has x<=n different characters with the third-string. Edit : This assumption is wrong. vioalbert has given an counter example.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Did anyone else solve B by figuring the minimum and maximum possible positions of each character 'M'? I thought that was really interesting! Also, the problems were fun, although I felt that the gap b/w C and D was a bit too much. Nevertheless, kudos to the authors!

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

is true in div2C? each number is all either the maximum of the remaining or the minimum

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

How to solve B ? I took lot of time coming up with right solution. I want to know if there is some better method.

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

    Key observation is, that we can use the first n/3 Ts as first T, and all other Ts as second T.

    Then you count the first Ts, the Ms and the second Ts. If at any point the number of Ms is bigger than the first Ts, or the second Ts is bigger than the Ms, then ans=NO.

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

    My observation was that there must be at least one T on the left side of one M. For example, going from the left, "MMT" doesn't work, neither does "TTMMM". However, this only solves the left side "TM" of "TMT", so we'd need to iterate the string again from the right. If nothing fishy like the number of M exceeds the numbers of T in both directions, then we are sure that there is a solution for sure. Prior to doing all of the above, I made sure that the number of T:s are exactly twice as many as the M:s.

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

    You can just iterate over the string from left to right and from right to left and count Ts' and Ms'

    If at any moment counter of M > counter of T the answer is No

»
3 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Guys how to get started with DP ? Can we learn it before graphs,trees,and other such topics . Please help

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do problem C?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    First sort the s_i in increasing order. Let us find dp[l][r] = the answer for the array s[l...r]. Clearly, dp[i][i] = 0 for all 1 <= i <= n

    Now look at the process backwards, and convince yourself that we must remove either the maximum or the minimum process from s[l...r]. This gives us the recursion,

    dp[l][r] = s[r] - s[l] + min(dp[l+1][r], dp[l][r-1]).

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please elaborate a bit on how you made this observation?

      "Convince yourself that we must remove either the maximum or the minimum process"

      Thanks

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Maximum difference in any subarray will be max-min, so if you pick max and min in a subarray before you will add the maximum difference to the cost many times which is for sure not optimal.

»
3 years ago, # |
  Vote: I like it +51 Vote: I do not like it

I have fucking brain damage

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

awesome contest guys thx

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

problems were nice! Good round.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1509/submission/113246060 What's wrong with my approach ? Div 2 problem B

»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Best round I've seen in a long period!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Kuroni (previous revision, new revision, compare).

»
3 years ago, # |
  Vote: I like it -40 Vote: I do not like it

MikeMirzayanov it's a bit annoying that during the round to check how many pretests are there we have to use m1.codeforces.com. Could you please do something so it's also visible in the main website?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +54 Vote: I do not like it

    Pretests Passed(X)

    Isn't X the number of pretests? It is available on the main website.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Is the number after "accepted" not the number of pretests?

»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Can we have a notification when editorials are out and your participated in that round? As it is quite tiring to check for editorials again and again.

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve problem E? (I have a $$$\mathcal{O}(n \log^2 n)$$$ solution with HLD and treaps, but it TLEs :( )

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    So the first observation to be made is that is there's an answer, then you can obtain the order of the children immediately by sorting each node's children by its value.

    After this, I suppose you went the simulating way, but there's another observation that makes it much more easier: you can visualize the operations as pushing the label $$$u$$$ towards a leaf, and that leaf happens to be the node where $$$u$$$ is its post-order! (in other words, at the end where there are no operations to be made, the labels form the post-order of the tree). So you can additionally create the post-order of the tree, and from that you can do side-by-side checking.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Kuroni (previous revision, new revision, compare).

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

how did you guess that C is dp? i tried everything except dp

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

    This may sound like cheating, but notice the constraints allows O(N^2) so you should think of DP. If a problem at this level(for example first half in div2) is greedy then it is likely that the complexity should be linear or NlgN. The fact that it allows O(N^2) highly suggests that naive greedy would fail on some edge cases.

    Not a good idea though. Try finding why your greedy(I assume you use greedy?) is wrong helps you improve.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The problem was tagged greedy for Div2C, would greedy work? I spent an hour implementing a greedy version, which seems like it would not work :(.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The greedy tag refers to the fact that for dp(i,j), either i or j should be the last one to enter, so you don't need to try j-i+1 possibilities. Sometimes dp requires some observations (like greedy), but greedy can not solve this problem as a whole.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          The greedy tag refers to the fact that for dp(i,j), either i or j should be the last one to enter, so you don't need to try j-i+1 possibilities

          Nice Observation, this statement makes a lot of sense.

          For a moment, I was left surprised when we only considered the min/max as the last one to enter, so we are definitely considering the choice of the last position as a greedy choice.

          I will take note of this!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Weebs' round. I love it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can any of you help me understand the verdict for DIV2.D?

Submission: 113250060

Verdict(pretest 3): "wrong output format Unexpected end of file — token expected (test case 1)"

Has it got something to do with array capacity/length? What am I missing here?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You didn't output anything.

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 3   Vote: I like it +3 Vote: I do not like it

      dorijanlendvaj yes, right.

      But, the confusion is, it did output for smaller inputs. So something must be wrong processing larger inputs (Breaks at pretest 3; n=99999)

      I couldn't still figure out why, only for large inputs, would it not output anything, .

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 3   Vote: I like it +3 Vote: I do not like it

        5 0000000000 0000111111 1110101010

        Your code doesn't output anything on this test case.

        Test case 3 is very similar; the first string is 199998 0s, the second string is 99998 0s and 100000 1s and the third string is 50000 1s, 50000 01s and 49998 0s.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please give small clue for Div2E or Div1B, through simulation I figured that total possible almost sorted permutations for $$$n$$$ length array was $$$2^{n-1}$$$, and there was some kind of pattern being followed but could not uncover it...

»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

So the Anime theme round ends with SUPERSONIC score distribution , rating changes and editorial. Thank you so much XD

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

To not keep you waiting, the ratings updated preliminarily. We will remove cheaters and update the ratings again soon!

»
3 years ago, # |
  Vote: I like it +55 Vote: I do not like it

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

Can Someone give me test case for which my submission for problem D gives WA.
LINK to submission

You can also point out mistake in my code.

It will be very helpful.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello, I am a new user of codeforces and I joined your contest today. I solved problem A and B and got 70 points in total. Did i do something wrong or is there something wrong with codeforces?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    no ,you are good enough,proud for you

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is this code wrong(Problem Div.2-D)? https://codeforces.com/contest/1509/submission/113266390

»
3 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Emmm, I have a very mysterious problem about problem B of div.2!

I surprisingly found that when I iterated string "s" by using "for(auto &i : s)",I got a WA on test 162nd.

After a very long time's debugging, I attempted to replace "break" with "goto",and then got an AC. Could anyone explain the reason behind this?!

Much obliged!

My submission:

using "goto" : 113285205

using "break" : 113284849

Sorry for my poor English..

If there are any grammar mistakes,plz ignore it...

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The one using break doesn't skip the 2nd loop, use return instead

    Try this:

    1
    12
    TMMTTTTTTMMT
    

    ans is "NO" but yours prints "NO NO"

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Had -114 in the contest can anybody feel my pain?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I wish my upvote for you could ease your pain a little^ ^

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Thanks buddy .I surely will come back stronger next time. With this comment I promise to be expert in next 50 days.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me why this solution of DIV2/C is giving TLE with Memoization? https://codeforces.com/contest/1509/submission/113300784 I really can't figure out the silly mistake.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    You are copying vector<ll> v every time you run the function. Try using reference (i.e. vector<ll> &v).

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Kaguya-sama theme contest when?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone give me a test case or tell me what's wrong with my solution in div.2 D

My approach was to try every possible 2 strings and greedily make a resulting string such that it contains both strings and check if its size is less than 3*n.

link to submission getting wrong answer on test 843 of test-set#6

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello, I'm new here and confused why did my rating just go up from this contest from ~800 to 935? My profile says I'm rank 4003 on the rating graph but I'm really not...