the_nightmare's blog

Codeforces Round #721 (Rated for Div2)
By the_nightmare, history, 4 years ago, In English

Hi, Codeforces!

I'm glad to invite you to take part in Codeforces Round #721 (Div. 2), which will take place on May/20/2021 17:35 (Moscow time). The round will be rated for the participants with a rating lower than 2100. Participants from the first division are also welcomed to take part in the competition but it will be unrated for them.

You will be given 2 hours to solve 5-6 problems. Problems were created by members of Club of Programmers IIT (BHU)- rivalq, sharabhagrawal25, loud_mouth, DenOMINATOR, Bignubie, mallick630, shikhar7s, CoderAnshu and Me.

Huge thanks to those who helped make this round possible:

We tried our best to create interesting problems and simple-to-read statements and we hope you have fun! Happy coding :)

UPD

Scoring Distibution:- 500 — (750 — 1500) — 1500 — 2250 — 3000

UPD

Congratulation to the winners

Global

  1. ksun48
  2. jiangly
  3. alya_wow
  4. Geothermal
  5. TheIceKing

Div2

  1. alya_wow
  2. TheIceKing
  3. fqwmc
  4. l9ll6lll
  5. Lenstar

UPD :- Editorial

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

Comments Comments (339)
| Write comment?
»
4 years ago, # |
← Rev. 3   Vote: I like it +15 Vote: I do not like it

Hope this won't be similar to the math contest that was prepared by you guys (IIT BHU) earlier.

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

A contest by Indians after such a long time! Very Excited!!

→ Reply
»
4 years ago, # |
  Vote: I like it -118 Vote: I do not like it

As a tester, I want contribution. Problem set is great.

→ Reply
»
4 years ago, # |
  Vote: I like it -60 Vote: I do not like it

op

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

Nice work COPS-IIT BHU team.

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

Happy to take part in testing for the first time!!! As a tester, I recommend you to read all the problems.

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

    C was easier than both B1 and B2. Probably C should have been B .

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

      That's why I gave that suggestion.

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

      I think different problems worked well for different people. I got A, B1, and B2, and I ran out of time on D, but I didn't know what to do for C.

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

        You can think about each pair（i,j）(i < j),which satisfied that a_i = a_j,then,it can denote to answer (n — j + 1) * (i + 1) So you can used MAP from left to right,let f[u] denotes the sum of (n — i + 1),(a[i] = u),and add (n — j + 1) * f[u] to answer when the element a[i] you now deals equal u (I'm sorry that my English is so poor)

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

          your's explanation is pretty nice as it compelled me to think in right direction. Thanks!!!

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

As a tester the problems were great and I recommend everybody to participate.

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

omg Indian round

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

As a tester, I wish you good luck!

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

I hope the round is nothing like your username.

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

Hope to become pupil this time...

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

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

    Your rating graph is quite motivating!

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

      Well not a great results but I will keep trying I started well at the beginning and could reach expert but then bad stuff happened and I completely stopped practicing because of that now I should be able to improve I think

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

        Wishing you luck for today's round.

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

        I think, somehow, you and I have the same situation. I peaked Expert 3 times in 3 different years. But I stopped for a period of time. Do you think that Codeforces problems are more and more difficult? Jhin

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

          I think we used to try harder .. when I first started I would sit and think about a problem for hours now I am not like that... I don't think contests became harder there are so many people I know improved their rating a lot so it's our fault we should just try harder as before

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

            Hang in there! I added you as a friend. See you again in Blue or Purple.

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

    I predicted the future

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

Kudos to the team for compiling a much awaited contest for us. I hope that the problems are indeed as simple-to-understand as they are to-read. :D

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -12 Vote: I do not like it

    gyrating cat UwU

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

    Kudos to the team for compiling a much awaited contest for us. I hope that the problems are indeed as simple-to-understand as they are to-read. :D

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

Why isn't demoralizer part of problem setters team.

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

    i think he isn't part of that team that's why

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

I'm thrilled to take part in this contest. As it's prepared by one of my college senior of one and only IIT (BHU) Varanasi :).

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

[deleted]

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

https://ibb.co/n1qqWfg

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

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

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

[deleted meme]

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

    Its a relative thing, if everyone was good, then cutoff for pupil would have been 4000 rating. Nothing more.

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

Can I become pupil?

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

oh welcome back indians setters

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

Cheater becoming tester for the round strange!

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

    They even deleted a previous comment in which someone pointed this out

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

      Yeah i think this round was prepared before the blog post came out. Else they will not have considered him i think.

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

        i am not aware of what is going on. Mind sharing some details. like which cheater. you know u can always drop a personal message if u don't wanna share here

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

    Maybe he has already leaked some of the problems in his groups!

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

    Everybody deserves a second chance don't judge him like that

    Edit: after reading the blog I changed my mind ..making a YouTube channel and telling people to not cheat then do such a thing is a shame .. I thought it was just a one time thing and he won't do it again

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

    Who is it?

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

Whenever there is an Indian contest Every Indian Contestant

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

I hope this Indian contest to be great the same as the greatness of the Indian educational videos on youtube that saves us in the nights of the quizzes XD

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

others: u need css to make websites look good. codeforces: hold my html links..

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

    People (companies) who are good with CSS, are not doing that good except for good promotions.. If you know, you know :)

    Better & Strong System Should be there not always CSS done their work.

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

WowGood！Regardless of the difficulty of the question, I really expect this "simple-to-read statement"!

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

As a participant, I will read all the problems.

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

I hope this time its a codeforces round and not a jee round

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

IIT BHU giving the best coders of INDIA. One of the best Example demoralizer sir.

Not saying about college. I know its there own hard work.Just telling the fact That most best coder of India are from there

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

    lol college is doing nothing for good to student atleast in India,its all about their own labour and btw demoralizer dont even felt good to join college coding club cause he know colleg club is also good for nothing ,they are one of best cause they have done labour,Dont give credit to Indian colleges ,they are just big names from which noone learn thing of their own benifits

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

      Talking about colleges in India, it's okay if they do nothing for students to improve their skills. But there are some colleges (like my college) having too many assignments, classes, vivas and exams and there won't be much freedom.

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

Best of luck to all the participants :)

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

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

Strange Monogon did not ask for contribution this time :( Feeling unlucky already :((

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

Hope I become a pupil this time

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

Any update on scoring distribution? UPD : added

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

I hope I can solve only 2 problems...as a newbie...

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

Will B have a subtask? Asking due to the scoring distribution?

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

    There are 5 problems, One problem has been further divided into subtasks

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

by looking at the number of people who registered , reminding people that you would have to use m1.codeforces / m2.codefores / m3.codeforces

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

what are subtasks? can anyone tell

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

    basically they are the same problem with different constraints

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

Second question having a subtask seems scary.

Maybe it's combinatorics :o

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

Bruh, what is going on with that scoring distribution.

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

i can not register please . help the_nightmare

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

Are these guys MATH FREAKS?

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

Goodbye Specialist.

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

rainboy orz !

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

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

    There is not even a single question having tag "Maths". Idk how have you found maths in the contest.

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

    Fight hard till end. Other option would be still valid after contest

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

Whoever prepared problem B2 is an evil person

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

    it took me until 1:59 to solve B2. I was planning on at least tackling problem D when I first saw the scoring distribution lol

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

I suggest that every writer's first contest should coordinated by Anton in order to improve the quality of the contest(and avoid boring or classic problems like D,E).

And other coordinators should learn how to reject some problems?

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

I thought I would become expert today :|

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

    Same.

    My reaction after knowing the solutions is like your profile picture

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

Quite unbalanced problems

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

Lol, $$$B$$$ is harder than $$$C$$$, $$$D$$$ and $$$E$$$.

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

    Are $$$C$$$, $$$D$$$ and $$$E$$$ known Algorithms/Ideas?

    I managed $$$B$$$, the hard one could be solved with straight forward game theory and dp (was a bit ugly to implement though. The dp depended of 4 variables. 1. The amount of zeros coupled with a zero. 2. The amount of zeros coupled with a one. 3. Whether there is a central 0 in case of n odd. 4. Whether last turn a reverse was performed.).

    But for the love of God, I couldn't come up with anything for $$$C$$$ and didn't get to think about $$$D$$$ and $$$E$$$

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

      $$$E$$$ is D&C DP optimization

      $$$D$$$ is case analysis + implementation

      $$$C$$$ is just easy and described somewhere below

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

        E has a much simpler solution involving segment tree range updates. D is tree traversal and basic analysis on it C is simple, just think about the contribution of each element in the answer. The detailed solution will be given in editorial

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

        Can you explain Soln of D in detail?

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

        Ok, now: I finally did implement $$$D$$$: 116963680. And I absolutely positively can say: There's no way I would've managed this task in the contest. It is just plain more difficult than $$$B1$$$+$$$B2$$$ for me.

        I thought about the task yesterday in the evening and did come up with a solution. I sat down today implementing it: there were so many cases and implementation details. I did two logical errors which I had to find and fix (the message "wrong answer 1923rd numbers differ" on test case 5 (!) nearly gave me a heart attack. How was I gonna find that?). And the editorial doesn't look much simpler to me.

        So I state $$$B<D$$$.

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

          nvm

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

            Ah, you already got it. I just finished rereading the task and wanted to comment, that this is not a problem I'm very motivated to think about again... It felt like a big casework for me :/

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

        I don't know if it's too much to ask for, but I simply can't spot anything wrong with my solution for C. Please do have a look, chief

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

          You have a really minor error. 

          sum+=((prefix[i-1])*((sz-v[i]+1)));

          The sz is wrong. It should be:

          sum+=((prefix[i-1])*((n-v[i]+1)));

          See 116995339

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

      C has a common idea with many "over all subarray" problems. Instead of counting weight of every subarray, you can count amount of weight an element adds to the final answer.

      Then it was just some mathematics to calculate the number of subarray an element contributes to.

      Keep track of index of each element, say $$$1$$$ occurs at indexes $$${1,5,8,10,...}$$$, then the contribution for this can be calculated as,

      for every index in this array:
    contribution += index*(suffix sum of ( n - all indexes above this index))
      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it +1 Vote: I do not like it

        Well funnily I already did split the indices into seperate vectors. And I tried to do some dp then, by somehow counting the amount of "subsequences with n times the same number".

        It just wouldn't come to my mind searching for the pairs only. With your hint implementing it was done in 5 minutes. Oh well! Thanks! :)

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

    I agree. I solved B at the end of the contest.

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

      I also solved B2 in the last 30 seconds. Overall, It was a good experience.

      I hope everything passes system tests. Fingers Crossed.

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

How to solve E?

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

how to solve C?

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

    For any (i, j) such that a[i] == a[j], number of subsegments that contains the pair is (i+1) * (n-j). This is basic idea and then we need to optimize our code, check my AC submission.

    Optimization ->
    I used Hashmap (unordered_map<int, vector<int>>) through which I add all the indices in a vector where the values are equal. For eg-> let's say in a of size n=10, value 3 is at {0, 2, 4, 5, 8}.

    Now using the above expression => let's say j == 5 then subsegments which have index 5 and one of any previous index(0, 2, 4) in it are = (1 + 3 + 5) * (n - 5) and this is where we can use prefix sum and get time complexity of O(N).

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

      Can you please explain how you get to (i+1)*(n-j)?

      Edit — Nevermind got it. I misread subsegment as subsequence!

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

        Consider the array indexed from $$$0$$$.

        Any range that starts at $$$i$$$ or before it and ends at $$$j$$$ or after it, has the pair $$$(i, j)$$$. There are $$$i + 1$$$ possible left endpoints and $$$n - j$$$ possible right endpoints for the range containing $$$(i,j)$$$; thus the pair $$$(i,j)$$$ is inside $$$(i + 1)\cdot (n - j)$$$ ranges.

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

We will soon upload the editorial for the contest.

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

This contest was a nightmare for me!!

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

I could have become expert if i had not made the silliest mistake on problem A which will make my solution pass the pretests but will fail at higher values.

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

Coordinators should take the blame for not rejecting this shit.

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

I didn't like the problems at all. A and B were just stupid observations. Also, difficulty of C was probably overestimated.

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

    You wanna see observations in problems though. Those observations are nice.
    They should've swapped C with B though.

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

    Well they aint gonna take the blame anyways. You know the contest will be a gamble when you see B to be worth 2250 points.

    Feeling sad with many many others.

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

Why DP failed on problem C. State: dp[i][j] = weight of subarray from [i,j] Transition:

if (A[i] == A[j]){
    dp[i][j] = 1 + dp[i+1][j] + dp[i][j-1];
}
else dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
ans += dp[i][j];

While adding the weights of every subarray.

Submission: 116828863

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

    Considering the range of values can be 2x10^5 using 2-D dp may not be a good idea IMHO.

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

      Can you give some idea on how to solve it?

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

        I don't want to give a spoiler here :) But here are some hints based on my solution:

        Hint 1
        Hint 2
        Hint 3
        → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    the answer can be very large so change int to long long. Also i don't think your (N^2) will pass the time limit restriction.

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

    .

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

How to solve B??

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

    Here is my solution. Let's call $$$f(i)$$$ to the symmetric position to $$$i$$$ if we take the center of the string as symmetry center.

    Now, the state of the game depends on:

    • the number of $$$i$$$ such that s[i]=='0' and s[f(i)]=='1'. Let's call this $$$C_{0,1}$$$.
    • the number of $$$i$$$ such that s[i]=='0' and s[f(i)]=='0'. Let's call this $$$C_{0,0}$$$.
    • whether the previous movement was a reverse or not. Let's call this a Boolean variable rev.
    • whether the middle value of the string is 0 or 1, (if the string's length is even we consider it as a 1). Let's call this a Boolean variable mid.
    • whether it's Alice or Bob's turn. Let's call this a boolean variable turn.

    So, the state of the game is the tuple $$$(C_{0,0}, C_{0,1}, rev, mid, turn)$$$

    Now consider d = score(Alice) - score(B). We can interpret the game as the following: Alice wants to minimize d and Bob wants to maximize d. So, we can have the following DP solution:

    $$$Dp(state)$$$: for the current state, if it's Alice's turn, what's the minimum possible value of d, and if it's Bob's turn, what's the maximum possible value of d. The transitions are straightforward. The time complexity is $$$O(n^2)$$$, and so it's the space complexity. Since this Dp doesn't depend on the input string, we can precompute this Dp (or do it recursively with memoization).

    Now, for the initial state of the game, if Dp(state) < 0, then Alice wins; if it's > 0, then Bob wins; otherwise it's a draw.

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

caseforces xD

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

.

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

    I don't understand how you can speak so disrespectfully of the efforts of other people who have made significant efforts to prepare. Oh, I see you prepared a lot of rounds and they were all great. Sorry, no.

    You probably didn't like the problems. You may not be alone in this. AND? people tried. The writers tried hard. The coordinators tried hard. Testers helped with testing. There were clear statements in the round, there were no mistakes in solutions and tests. You don't pay to participate. Enthusiasts put their energy into making you happy. They have failed to please you. Any set of problems — some like it more, some less. I urge you to maintain respect and express your criticism in a balanced manner and without harsh or offensive forms.

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

      Totally agree with you!! Please don't get disappointed due to such comments, you have made the best coding platform for us. I am very grateful to have this free of cost.

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

      Sorry for this comment, I was really impulsive that time.

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

First time solved 4 Qs in div 2! Practicing DP for the past few days really worths it.

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

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

Problem B ruined the contest for me , I couldn't find any mistake in my code ,tried till the end but failed .:(

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

Finally getting to 1500! Ideas for A,B1 and C :

A
B1
C
C-code
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    On C if all the number are equal your solution is (N^2) and i dont think will pass the system tests

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

      Nope its O(n) because the map loop will execute only once and the inner loop is linear.

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

        you are right about that it shouldn't TLE ! I did the same thing as you and i got TLE in pretests. ;_; Really not sure what went wrong. https://mirror.codeforces.com/contest/1527/submission/116811751

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

          I guess its because you are initializing vector with max constraints for every test case and also running loop till max constraints for every TC. Also I thought of doing coordinate compression like you did but then just went ahead typing fast and mindlessly took a map of vector lol.

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

            You are right, it's the initialisations ;_; ;_; I'll cry myself to sleep now ;_;

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

    For B2 check the case if it is not a palindrome,then it will favor Alice completely, except in the case when the string length is odd with 0 at the mid position and the total number of zero's are 2, then it will be a draw.

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

      Thanks! I was completely blanked by B2, was thinking of some dp with differences of scores of A and B then breaking down into some transitions, but got me nowhere. I wonder if there is a dp solution to it.

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

    In B1, for the case "100001", n is even but I think it is a draw.

    Alice Move- 101001 Alice-1 Bob-0 Bob Move- 100101 Alice-1 Bob-0 Alice Move- 101101 Alice-2 Bob-0 Bob Move- 111101 Alice-2 Bob-1 Alice Move- 101111 Alice-2 Bob-1 Bob Move- 111111 Alice-2 Bob-2

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

      One winning scenario for Bob:

      100001 (Alice +1) 101001 (Bob + 1) 101101 (Alice + 1) 101111 (Bob rev) 111101 (Alice + 1) 111111

      Final : Alice 3 Bob 1

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

Please check this submission :- https://mirror.codeforces.com/contest/1527/submission/116820959

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

badly missing antontrygubO_o.

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

    Strongly agree. My favourite coordinator (he also was the coordinator of my previous 672 round too).

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

D and E are boring ,and B is hard .

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

    How to solve E? Couldn't get any idea for an hour.

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

      $$$dp[i][j]$$$ is the answer of dividing the first i elements into j segments .

      And use a segment to maintain it.

      Works in $$$O(nk\log n)$$$

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

        you can do the same dp but with DC

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

        How to calculate the range cost in log(n). can you explain?

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

          Extend right endpoint r.

          When r+=1 , find the last position $$$i$$$ that $$$a_i=a_r$$$.

          And the cost of $$$[l',r]+=r-i+1,(l'<=i)$$$,and $$$[l',r],(l'>i)$$$ doesn't change .

          Use a segment tree to find the minimum element in a range.

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

Holy smokes, what a nightmare.

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

Nice problem D! liked it.......

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

For E, I wonder how calculate cost(i, j) fast? Got tle in case 13 due to n^2 init

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

    I got accepted in O(n2). Take a look at https://mirror.codeforces.com/contest/1527/submission/116859222

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

      understand, the same divide & conquer dp, with second dimension compress a bit. nice idea.

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

        Divide and conquer dp is a bit overkill for this I thought.

        My solution went like this: int ans = 0; First we will store cost(1, i) in DP[i] for all 0<=i<=N. DP[0] = 0 ans = DP[N]

        Now we will do the following sweep (K-1) times: Keep a RMQ (min) segment tree. Initially, the array represented by the segment tree at index x (1<=x<=N) stores DP[x-1]. Now, we'll sweep from left to right. Let prev(x) denote the maximum i such that i<x and A(i) = A(x). When we reach index x, we will add (x-prev(x)) to range (1, prev(x)). We will update DP[x] to min_query(1, x) now.

        After each time we do this, we will update ans to DP[N].

        It's easy to see why this works.

        Submission link: https://mirror.codeforces.com/contest/1527/submission/116857074

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

      delete

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

        I think it is n*k*logn*20 ？ standard d&c dp with 20 to calculate the cost for each necessary state

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

          oh,sorry.

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

          Yes, you're right. It's O(n2) for pre-processing the cost matrix and then O(n * k * log(n) * 20) for calculating the minimum cost partition.

          The 20 is needed because we can't store O(n2) values within the memory limit. We could compress it further to reduce it to 10 or 5 but that is not required.

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

I see that many people in problem B have checked if count of '0' is odd and not 1 then its alice . But I dont understand. lets say its of size 5.
1000001 (starting string)
1100001 (alice = 1 , bob = 0)
1000011 (alice = 1, bob = 0 )
1100011 (alice = 2 , bob = 0)
1110011 (alice =2 , bob 1)
1100111 (alice =2 , bob = 1 )
1110111 (alice = 2 , bob = 2)
1111111 (alice = 3 , bob = 2)
hence bob wins.
could someone tell me what I am thinking wrong

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

    Alice's first move is not optimal, she should try to make the string palindrome so that Bob cannot reverse if the next step. So the optimal first move is making the third 0 to 1. Then Bob would be bound to pay $1 as he cannot reverse.

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

    1001001(Alice), 1101001(Bob), 1101011(Alice), 1111011(Bob), Alice's reverse, 1111111(Bob), Alice wins

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

    If count of 0 is zero then Draw.
    Else if Count of 0 = Even :- Bob Wins.
    Else if Count of 0 = Odd, then 2 Cases :- 1.) Count of 0 = 1 :- Bob Wins.
    2.) Else :- Alice Wins

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

      It is given there is atleast one 0

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

        Ok then it will not enter in starting if-condition.
        Always go in else part & Game can never be draw.

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

    1000001 (starting string) 1001001 (alice = 1, bob = 0) 1101001 (alice = 1, bob = 1) 1101011 (alice = 2, bob = 1) 1101111 (alice = 2, bob = 2) 1111011 (alice reverse the string, alice = 2, bob = 2) 1111111 (alice = 2, bob = 3)

    Alice Wins. The strategy is as follows: If we have a string with number of '0' larger than 1 and odd, that means that the middle character is '0'. So, alice takes that first and then forces Bob to make a '0' into '1' every time. Alice will always place a '1' in the mirror of were Bob placed his so the string still remains a palindrom. In this way, when there is only one '0' left, the score is equal and alice can reverse the string and make Bob Lose. Hope this helps and you understood!

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

I think B1+B2 can be solved by greedy: denote a as the number of 0 at some index i such that 1 at index n+1-i; and denote b as the number of other zeros. If a = 0 (here is the easy part): if b = 1 or 2 then Bob Win; otherwise, Alice wins if and only b is odd. If a = 1: Alice wins except case b=1 (draw). If a \ge 2: Alice wins.

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

the most weird contest I have ever seen

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

What is the idea for A ?

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

    The first bit of n must be 1, suppose that it is on index t from right to left, so in the expression, you need to have a number with bit 0 at that position. And the maximum one is 011...1 with t-1 numbers of 1.

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

how to solve B2? it's harder then E for me.

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

    If the string is already a palindrome, then you can use your B1 solution and if not then ALICE always wins except in one case that is if the string length is odd and it has a zero at the middle and has only one position i such that s[i] != s[n — i — 1];

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

      Can you explain the thinking/idea behind this?

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

        Just tried all the cases on paper

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

Isn't Problem B misplaced? It should have been C or D according to the scoring distribution.

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

In B1 probelm who should be winner for 10000001 case and please mention the moves also

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

    Bob will win. First, Alice replaces some zero, suppose that 11000001. Then Bob does the same, replace by the opposite position 11000011. Continue for two more steps: 11100111, now each one costs 3 and here is turn of Alice, she makes 11110111, now Bob just reserves the string, and Alice costs 2 more than Bob.

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

    Bob Wins. (10000001) (position = 1 to 8)
    It is palindrome with 6 0's.
    In first move, Alice can choose any 0 (at position=i) then bob choose 0 at position (9-i).
    Similarly happen one more time.
    Then only 2 0's are remaining, then bob chooses some '0' and now string is not palindrome , then bob reverses it and then Alice again chooses some '0'.

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

    Whoever that is able to mirror wins. Example:

    1001001

    Alice does whatever: 1101001

    Bob mirrors Alice: 1101011

    Thus forcing Alice to not have the reverse option: 1111011

    When one zero left, Bob does reverse and let Alice fill in the last one. Bob wins, in fact, if there are 2n numbers of zero, then Bob always wins.

    If there are odd numbers of zero, Alice fills in the middle one, like 100010001, and wins by using the same mirroring strategy as the above example when Bob does whatever like 110010001.

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

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

The contest was amazing. I think the most interesting problem of today's contest was B2. Thank you very much the_nightmare

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

A recursion based solution for B2:

  • U = number of 0s in position S[i] such that position S[n-i-1] = 1 (call them 'unbalanced' zeros)

  • B = number of 0s in positions S[i], i < n/2, such that S[n-i-1] is also 0 (call 'balanced' zeros)

  • Mid = 1 if n is odd and the middle position is 0, otherwise 0

  • Rev = True if last move was a reverse, False otherwise

Then rec(U,B,Mid,Rev) is the minimum possible score from that state.

If U = 0, B = 0 and Mid = 0, return 0

Otherwise, let best = INF

  • If U > 0, best = min(best, 1 — rec(U-1,B,Mid,false))

  • If B > 0, best = min(best, 1 — rec(U,B-1,Mid,false))

  • If Mid > 0, best = min(best, 1 — rec(U,B,0,false))

  • If not Rev and U > 0 (i.e. not a palindrome), then best = min(best, — rec(U,B,Mid,true))

These are the only possible transitions. If the score comes out positive, Bob wins, if it's negative, Alice wins, if it's 0, Draw.

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

    what will be the time complexity of this approach?

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

      U <= N/2, B <= N/2, Mid is from {0,1}, Rev is from {0,1}.

      The theoretical maximum complexity is N^2, but the constant factor reduction is very significant, since U+B <= N/2. Even if we ignore this bound, we have 500*500*2*2 states = 10^6. But we can also use memoization across the 10^3 test cases, so we will only evaluate at most 10^6 states over all test cases.

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

    If not Rev and U > 0 (i.e. not a palindrome), then best = min(best, 1 — rec(U,B,Mid,true)) can u plz explain this?

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

      Typo there. I've amended — apologies.

      The line represents the fact that if the string is not a palindrome (U > 0) and the last move was not a reversal (Rev = False) then we can flip to the other player.

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

    Can you please share your submission

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

      Sure

      Ignore the comments. That's me thinking during the contest.

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

        great solution

        why didn't I think abt recursion , it makes thinking so easier

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

    Glad to see this, I also followed a similar approach. I took $$$\mathcal{O}(N^2)$$$ time to precompute the memo, and then answered all queries in practically $$$\mathcal{O}(1)$$$ time (apart from having to read and process the input strings, of course).

    Submission link

    Short explanation:

    1. coz = count of positions such that it's a 1 on the left side and 0 on the other (asymmetric)
    2. czz = count of positions such that it's a 0 on both sides (symmetric)
    3. Note that we don't need a coo (count of positions such that it's 1 on both sides) because participants can't play on those positions.
    4. mid_set whether the middle bit is set or not.
    5. mid_max — the maximum value the middle bit can take. it is zero if the middle bit does not exist ($$$n$$$ is even).
    6. prev_rev whether the previous operation was a reverse operation.

    Note that all these parameters uniquely define the state of our game and the transitions that can be taken from such a state. I think now, the rest of the operations in the code are relatively straightforward. The total time complexity is $$$\mathcal{O}(N^2 + TN)$$$. Of course, this solution is an overkill imo :P

    But, jimm89 why do you not need to precompute the memo? Without precomputation wouldn't it blow up to $$$N^2$$$ in some worst case. Because of this I think I had got TLE in test 2 earlier with similar approach.

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

      Yours TLEs because you’re initialising the DP vector for each test case. You need to memoize over all test cases, which achieves the same time saving as precomputation.

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

        Thanks, haha, I completely forgot about that! I have resubmitted with clearer code now: link.

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

          Nice code. I didn’t think to memoize in a 4d vector — my code is slower because I used a map. Fortunately it’s still only 311ms!

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

    Could you please explain a little why your transitions are 1 — rec(). Why minus? I'm curious about learning this approach. It seems to be helpful in many game related problems! jimm89. Sorry for unnecessary tagging, but I really wanted to know your thinking process in this recursion!

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

      Sure: I’ve reframed the problem to say that both players are trying to minimise the value of their own score minus the other score, so when they make a move which is not a reversal, we add 1 to their score, and then gameplay transitions to the other player. Anything the other player scores is then subtracted. Our final answer depends on whether, from Alice’s position, the best we can do is negative (win), zero (draw), or positive (lose).

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

Where do you guys get such problems? Although punishing, quite simple interesting!

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

My solution for C:

Store the positions for each unique number. Consider the example:

$$$[1,2,1,1]$$$

All pairs $$$(i,j)$$$ with $$$a[i] = a[j]$$$ are:

$$$a[i] = 1; [(1,3), (1,4), (3, 4)]$$$

Consider the pair $$$(i,j) = (1,3)$$$. For each subsegment that contains this pair, we have $$$(i)$$$ possible choices for starting position of the subsegment and $$$(n-j+1)$$$ for ending position of the subsegment. Using this, we can get number of subsegment containing each pair as $$$i*(n-j+1)$$$.

Let's say we store positions of all $$$1$$$ as $$$[1, 3, 4]$$$.

Then, $$$count_1 = 1*(n-3-1) + 1*(n-4+1) + 3*(n-4+1)$$$.

Note that $$$(n-4+1)$$$ is repeated twice since there are $$$2$$$ ones to the left of $$$a_4$$$. We could simply multiply $$$(n-4+1)$$$ by $$$(1+3)$$$. This is the prefix sum of positions of all $$$1$$$s before the current $$$a_4$$$.

Hence, for each unique $$$num$$$, $$$count_{num} = \sum\limits_{i=2}^{size(pos[num])} (n-pos[num][i]+1)*sum(i-1)$$$ where $$$sum(i-1)$$$ returns sum of all values in $$$pos[num]$$$ in range $$$[1,i-1]$$$ inclusive.

Sum of $$$count_{num}$$$ for all unique numbers is the final answer.

Submission

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

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

Sad that simple $$$O(NK \log(N))$$$ with long long and recursive lazy segment tree TLEed on E. Had to make some submissions and ACed with unsigned in the end. Did no tester face this issue or was it intentional to prevent other slower solutions for passing?

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

    Just submit the same code with C++17(64)

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

      Wow. Now it passed in ~2 seconds. Interesting!

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

    Actually, none of the testers solved that problem while testing.

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

Don't know why but B1 and B2 for me easier than C a lot!! :)))

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

Sorry, my bad...

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

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

I am fucking brain dead holy shit

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

What will be the output for string '0000' in B1? I think the output should be "DRAW".

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

    No, lets say Alice puts 1 in any position 0100 Bob can make it 0110 then since it is pallindrome again, Alice has to enter 1 making it 1110 Then Bob can reverse and Alice would have to fill again. Thus, Alice lost

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

Can someone please explain why first soln failed but second passed?

  1. 116754150

  2. 116768652

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

How could Alice win with 10000?

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

    She just make the 2nd operation first then Bob have to put 1 somewhere. After we will have the same picture as in B1 version.

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

    Alice keep on reversing it in every turn until he gets a palindrome after bob turn.

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

    Alice reverses 00001 (score 0-0)

    Bob's options: (1) 10001, (2) 01001, (3) 00101 (note that 00011 is equivalent to 01001) (score 0-1)

    In scenario 1, Alice then places in the middle 10101, and from there Alice can force Bob to mark both remaining 0s.

    In scenario 2, Alice reverses on both her next two moves, forcing Bob each time to mark another 0.

    In scenario 3, Alice then goes 10101, and the outcome is the same as scenario 1.

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

I wonder why writers wouldn't use the term 'subarray' instead of 'subsegment' in C. I misread 'subsegment' as 'subsequence' and I'm sure there are many others who made the same mistake reading it for the first time. If your aim was to create simple-to-read statements why not use the conventional terms?

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

The why i fear problem C, this should not translate to fearing C cups.

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

    I spent too much time on C, and when I figured it all out, I was too slow to code everything out and submit.

    So yes I do fear problem C, too.

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

casework solution for B2

let cd = count of a[i]!=a[n-1-i]
let c0 = count of a[i]==a[n-1-i] and a[i]==0

if cd==0: solve same as B1
else if cd==1 and n%2 and a[n/2]==0 and c0==0: DRAW
else ALICE

I can't prove how it works but it passed system test
AC code: https://mirror.codeforces.com/contest/1527/submission/116851873

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

What about cheaters ?

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

Here's my screencast from today's round. It's currently uploading and should be ready in the next few minutes.

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

bad round :(

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

How to prove the correctness of case based solution of B(1+2)?

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

    B1 feels intuitive. bob copies alice as much as he can until there's only 1 token left (on either side of the palindrome), in which he can flip it the final time to make alice go down an extra 2 tokens. be careful about n%2==1 where middle is open to '0' (as then alice can flip the script) and should be good.

    then B2, the logic is bob wants to make it a palindrome ASAP, otherwise alice keeps spam flipping. so we know that the cases eventually reduce down to B1. then, alice can also decide whether she wants to be the one to start case B1 by placing the final token herself, or keep spam flipping and let bob get to case B1 with it being his turn to move, and adjust costs accordingly.

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

      hmm, using the same but getting WA in B2.

      Anyways thanks! I will try again.

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

From my point of view, task C was rather well-known and classical. This idea is obvious.

How could this task even get to this round? I thought that rounds are checked for well-known tasks with trivial and well-known ideas.

This could be compared with the task like "longest increasing subsequence" and some other basic tasks.

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

    Can you tell what's the well known version of C or link it here? Curious as i could'nt solve

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

    I think it's fine to have it in Div 2, this approach is indeed standard, but it isn't described in algorithm books and websites, so a lot of newbies don't know it. Now they know.

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

inkjhb

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

This contest was a disaster for me

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

Great

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

    Alice: 1000 (add)
    Bob: 1001 (add)
    Alice: 1101 (add)
    Bob: 1011 (flip)
    Alice: 1111 (add)

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

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

small hint for B2 : If the starting string isn't palindrome, Alice will win or it will be a draw. There is no way for Bob to win if the starting string isn't palindrome.

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

Test cases are weak for Problem A as my this solution also passed:- int main() { int t; cin>>t;

while(t--)
{
   long long int n,count=0,u;
   cin>>n;
   u=n;
   while(n)
   {
    u=n-1;
    n=n&u;
   }
   cout<<u<<endl;
}

}

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

    Your solution works in log(n), you are doing n=n&(n-1) which sets least significant 1 to 0.

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

What if the string is of 4 length and string is 0000 then it should be draw,because first alice will change first character to 1 so string becomes 1000 then bob reverses it and then alice changes it to 1001 now bob cannot reverse the string because its palindrome, now bob makes it 1101 and now alice reverses it and now bob again makes 0 to 1 so string became 1111 and both pays 2 2 dollar for changing 0 to 1 , so answer should be DRAW and not BOB

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

    Init 0000
    Alice+1 1000
    Bob+1 1001
    Alice+1 1101
    Bob+0 1011
    Alice+1 1111

    Score 3:1

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

the score of B2 must be 1750 or 2000

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

How I solved A:

  1. Look at sample input and output
  2. Write the code
  3. Submit it
  4. Freak out that there are only 2 pretests and they were correct
  5. Now read the statement and spend 5 minutes verifying that the code was right.
→ Reply
»
4 years ago, # |
  Vote: I like it -15 Vote: I do not like it

Sir MikeMirzayanov, problem B1 lacks tests that come out "DRAW"!!?

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

    Because draw is impossible

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

      what about 11111

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

        The second line of each test case contains the string s of length n, consisting of the characters '0' and '1'. It is guaranteed that the string s is a palindrome and contains at least one '0'.

        → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it
        It is guaranteed that the string s is a palindrome and contains at least one '0'.
        → Reply
»
4 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Problem E is similar to B. The Bakery.

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

Question B2 https://mirror.codeforces.com/contest/1527/submission/116807363 Can anybody tell on what test case this solution goes wrong??

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

    if(n%2 == 1 and s[n/2] == '0' and z == 1) change this line to

    if(y==2 and z == 1)

    test case — 10000 ans = ALICE operations

    alice(0) — 00001

    bob(1) — 10001

    alice(1) — 10101

    bob(2) — 11101

    alice(1) — 10111

    bob(3) — 11111

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

Easy solution B2 https://mirror.codeforces.com/contest/1527/submission/116808998

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

When will be the ratings updated ?

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

To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!

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

Can anybody highlight the Corner Cases for Problem B2... I am getting wrong answer on Pretest2...

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

    Try
    1
    7
    1100010

    Output should be ALICE.

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

      Yes, this is a nice case...my solution is not working. May i know ur approach? Whether dp is required here? Actually, i am trying for a generalized solution for both B1 and B2. B1 got executed, but is failing cases in B2.

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

        We can use DP in this problem, but it I don't think its necessary.

        I've just further built upon my solution from B1. If you've done B1, you might have noticed that Alice wins by one point when there are odd no. of 0s and Bob wins by 2 points when there are even no. of 0s (given both players play optimally and discarding the edge case of n=1). Hence whoever wins, wins by a margin of a maximum of 2 points.

        Alice's disadvantage in B1 is that the string is a palindrome when she starts; hence her first action can't be of reversing. She is forced to change a 0 to 1. But in B2, she can start by reversing the string if it isn't a palindrome, forcing Bob to change a 0 to 1. She'll keep spamming the reverse operation till possible, so the only way for Bob to stop her from doing this is by making the string a palindrome again.

        Now the cases reduce to how many zeroes need to be changed to make the string a palindrome. If 0 changes are required, then the answer would be the same as B1. If 3 or more changes are required, then Alice would win. Bob will change these 3 zeroes to ones, but once the palindrome is obtained, he can gain a maximum of 2 points more than Alice in the palindromic string (explained earlier), and hence will remain 1 point down in total.

        So the only cases which are required to solve for are 1 and 2 changes. I encourage you to solve these cases on your own. If stuck, you can refer to my solution, which I think is relatively simple.

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

May I know where is the mistake in my solution for Problem B2?

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

    I can tell you my approach. (Assuming you solved B1)

    In B2, if the input string is not a palindrome then Alice keeps on reversing the string until Bob makes it a palindrome. Once the palindrome is made, you can use your B1 method to see who wins. But here is the tricky part, Alice just doesn't wait until Bob makes the palindrome. If Bob takes k no.of operations to make the string palindrome, then Alice waits till the (k-1)th step and sees the future by using your B1 function which takes the finished palindrome string as parameter and assuming Alice starts the move.

    If B1 function outputs => DRAW or ALICE, then Alice will let Bob make the kth step too and proceeds.

    If B1 function outputs => BOB, then Alice will do the kth step and let Bob start the move once the palindrome is made.

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

Can someone tell me why my code is giving correct answer on local compiler but not on codeforces ones?(For problem B2 in today's contest)

I suspect there must be something wrong with declaring string as global variable.

My code

UPD : It's becoz i was using cout and puts in the same code. The code got accepted when i either used cout or puts solely. Don't know the technical concept behind it.

→ Reply
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it 
My DP solution for question B2 is as follows:

Firstly, notice that if both s[i] and s[n-i-1] are 1, they are useless, we can comfortably remove them from our string. Next, if we have s[i] = 1 and s[n-i-1] = 0, let us swap them (swapping them will not make any difference to the current state of the game. WHY?). After this our string looks something like 000001010. Let us push all the 1s to the end of the string (Again, will not make any difference. WHY?) After this transformation, our string looks something like 0000000111 , basically X 0s followed by Y 1s (X >= Y).

We need one more parameter to define the state of the game because of one additional move mentioned in the problem (If the current string is not a palindrome and the previous turn has not been skipped, we can skip the move)
Let S represents a boolean variable representing whether the previous turn was skipped or not.

We can now represent any state of the game with three variables (X,Y,S)
DP (X,Y,S) represents the minimum number of flips from this state of the game.
Transition are straight forward:

   return 0 if X == 0 (kinda obvious)

   if (Y==0)
     -> delete the middle 0 (if possible), leading to (X-1,Y,0) 
     -> delete any other 0, leading to (X-1,Y+1)

   else
      -> delete the middle 0(if possible)
      -> flip the first zero, which will lead to the deletion of the last one, leading to (X-1,Y-1) {Flip 
          any zero actually, it will lead to (X-1,Y-1)}
      -> skip this move (if the previous was not skipped), leading to (X,Y,1)

Let the maximum of the states next to the current one be K, dp(X,Y,S) = X — K.

Finally, Score of Alice is dp(X,Y,0) {X,Y represents initial string}
Score of Bob is initial number of zeroes — score of Alice
The one with the lower score wins.

Link to my Submission : (https://mirror.codeforces.com/contest/1527/submission/116850107)
→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

.....

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

Can someone help me in CodeForces 721 Div 2 Problem B1, what if the string is '0000' ,why the answer is BOB why not it is DRAW. Since both will play optimally and will not allow to win the opponent.

0000 Alice=0 , Bob=0 // in starting

1000 Alice=1 , Bob=0 //alice have to change

0001 Alice=1 , Bob=0 //bob reverse the string i.e. not want to spend money

1001 Alice=2 , Bob=0 // again alice have to change the

1101 Alice=2 , Bob=1 //bob has no other option but to change

1011 Alice=2 , Bob=1 // alice reverse the string i.e. not want to spend money

1111 Alice=2 , Bob=2 // again bob will change

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

    0000 Alice=0 Bod=0

    1000 Alice=1 Bod=0

    1001 Alice=1 Bod=1

    1101 Alice=2 Bod=1

    1011 Alice=2 Bod=1

    1111 Alice=3 Bod=1

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

      yes i know this is one of the possible way , but if there is a way ALICE not want to make BOB win so he will make the game draw if he himself cannot win Dont you think it is also valid

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

        Yes it is also valid

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

          Don't you think this case is a contrary case and can have different answers and still both are playing optimally

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

Why editorial is not published yet?

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

can anyone tell me how BOB will win if S = 100001, in ques B. Thanks!

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

    First Alice has to make 1 zero to one, so S=110001 Bob converts Last zero to one, S=110011 It is palindrome so ALice cant reverse it so convert zero to one, S=111011 It is not palindrome so bob reverse it, S=110111 It was reversed last time so alice converts zero to one , S=111111 No of dollars Alice spent=3 Bob spent=1 Bob wins.

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

    100001(0:0) goes to 100011(1:0) to 110011(1:1) to 110111(2:1) to 111011(2:1) to 111111(3:1)

    as bob has lesser number of coins, hence bob wins

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

I think E in the contest is some kind of classical problem, can anyone please provide me link for similar questions for practice.

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

I didn't see anyone notice that B2 does not require DP, In B2 we just need to check if the given string is palindrome or not.

If it is a Palindrome then B2 solution is the same as B1 but if it is not a palindrome then we just need to count the number of zeroes and how many numbers are different. let Z : number of zeroes in the string and P : number of zeroes that need to change to make the string palindrome. if(z == 2 && p == 1) then only ans will be DRAW and in every other case ALICE will always win. code : here

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

    Yes that is right! Printing out the dp-table shows the same result. So if somebody is stuck on the game logic and can't work it through, he or she could do the dp, see the regularity, improve the answer and then be able to solve even bigger constraints, than dp allows (since the dp is $$$O(n^2)$$$ and your solution is $$$O(n)$$$).

    Just a miniscule heads up
    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me why did this give me TLE its problem A- submission

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

    see, for A if you consider the most significant bit, then , adding all the numbers till the highest power of 2 smaller than will get you a number in which the most significant bit is one as for all numbers from n to 2^k, that bit is always gonna be one , but for 2^k-1 that goes to a 0 and rest to 1 whereas we already had 0s in those bits previously , so adding that fetches us 0.

    quite simply (2^k)&(2^k-1) = 0 and this is what was used giving us the and 2^k — 1

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

Super fast Editorials in the previous contests created a bad habit. Now I am angry since the editorial of this contest is not up yet XD

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

    No it isn't bad habit. I honestly don't know why it so hard to have the round started when editorial is ready. Usually the "late" editorials are added after 1 day. Would it be so bad to have the round 1 day later and have everything prepared? I don't think so.

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

When can we expect the editorial to be published...

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

Hi!

Can someone explain me why my submission to Problem C keeps failing (attempt)? I think I had got the idea behind it, but I failed pretest 5 times during the contest!

Thanks in advance!

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

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

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

nightmare round

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

Can somebody help me understand B1 in 721? There are two test cases that have been bugging me

TEST CASE 1 :-

7

1001001

I feel that the answer for this test case is DRAW because both Bob and Alice spend two Dollars each

TEST CASE 2 :-

7

1000001

I feel that the answer for this test case is BOB because Bob spends 2 Dollars and Alice spend 3 Dollars

CLEAR EXPLANATION OF MY POV:- In case1 :- step 1:- 1101001 (Alice spends a Dollar)

step 2 :-1001011 (Bob reverses the string)

step 3:- 1101011 (Alice spends a Dollar)

step 4:- 1111011 (Bob spends a Dollar)

step 5:- 1101111 (Alice reverses)

step 6:- 1111111 (Bob spends a Dollar)

Both Alice and Bob spent 2 Dollars each.

In case2:- step 1:- 1001001 (Alice Spends a Dollar)

step 2:- 1101001 (Bob spends a Dollar)

step 3: 1001011 (Alice reverses)

step 4:- 1101011 (Bob spends a Dollar)

step 5:- 1111011(Alice spends a Dollar)

step 6 :- 1101111 (Bob reverses)

step 7 :- 1111111(Alice spends)

Alice spent 3 Dollars and Bob spent 2 Dollars

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

    The idea behind the 2 test cases you mentioned is similar, so I will just mention it for the first one:-

    Step 1: 1101001 (Alice spends a dollar); Step 2: 1101011 (Bob spends a dollar); Step 3: 1111011 (Alice spends a dollar); Step 4: 1101111 (Bob reverses the string); Step 5: 1111111 (Alice spends a dollar).

    Alice spends 3 dollars while Bob spends just one dollar, which means that Bob wins.

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

.

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

Hello MikeMirzayanov ,Codeforces system sent me a message saying that my solution(116813246) for B1 matches with someone else's(whom I don't know) submission(116794282).Now I see that some part of our code coincidentally matches but that was the most obvious part of this question.In my opinion that part was quite straightforward and many people would be having similar implementation.Even given solution has similar code but that doesn't mean I copied from problem setter or vice versa.Please check my solution manually and tell if it looks plagiarised...

→ Reply