the_nightmare's blog

By the_nightmare, history, 2 months 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 20.05.2021 17:35 (Московское время). 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

»
2 months 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.

»
2 months ago, # |
  Vote: I like it +139 Vote: I do not like it

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

»
2 months ago, # |
  Vote: I like it -118 Vote: I do not like it

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

»
2 months ago, # |
  Vote: I like it -60 Vote: I do not like it

op

  • »
    »
    2 months ago, # ^ |
      Vote: I like it -37 Vote: I do not like it

    why downvoting here, what is so wrong in the comment, It Is still not edited, that it looks absurd here. This is the problem with the CF community . Hope these downvoters or haters realise it.

»
2 months ago, # |
  Vote: I like it +59 Vote: I do not like it

Nice work COPS-IIT BHU team.

»
2 months 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.

  • »
    »
    2 months 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 .

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

      I cracked B1 and B2 but was not able to solve C.

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

      How you approached C ?? I was struggling with both B2 and C :(

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

      That's why I gave that suggestion.

    • »
      »
      »
      2 months 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.

      • »
        »
        »
        »
        2 months 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)

        • »
          »
          »
          »
          »
          2 months 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!!!

»
2 months 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.

»
2 months ago, # |
  Vote: I like it +56 Vote: I do not like it

omg Indian round

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

As a tester, I wish you good luck!

»
2 months ago, # |
  Vote: I like it +62 Vote: I do not like it

I hope the round is nothing like your username.

»
2 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Hope to become pupil this time...

»
2 months ago, # |
  Vote: I like it +214 Vote: I do not like it

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

    Your rating graph is quite motivating!

    • »
      »
      »
      2 months 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

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

        Wishing you luck for today's round.

      • »
        »
        »
        »
        2 months 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? SupaHotFire

        • »
          »
          »
          »
          »
          2 months 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

          • »
            »
            »
            »
            »
            »
            2 months 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.

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

    I predicted the future

»
2 months 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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it -12 Vote: I do not like it

    gyrating cat UwU

  • »
    »
    2 months 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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope everyone who read this comment(also me) have a rating increase in this contest

»
2 months ago, # |
  Vote: I like it +28 Vote: I do not like it

Why isn't HealthyUG part of problem setters team.

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

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

»
2 months 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 :).

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

[deleted]

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

»
2 months ago, # |
Rev. 2   Vote: I like it -38 Vote: I do not like it

[deleted meme]

  • »
    »
    2 months 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.

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

      can you plz elaborate what cutoff ?? Do you mean to maintain delta rating to zero, as a pupil you need to rank at least 4000 in this contest ??

»
2 months ago, # |
  Vote: I like it -30 Vote: I do not like it

Can I become pupil?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

oh welcome back indians setters

»
2 months ago, # |
  Vote: I like it +71 Vote: I do not like it

Cheater becoming tester for the round strange!

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

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

    • »
      »
      »
      2 months 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.

      • »
        »
        »
        »
        2 months 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

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

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

  • »
    »
    2 months 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

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

    Who is it?

»
2 months ago, # |
  Vote: I like it +106 Vote: I do not like it

Whenever there is an Indian contest Every Indian Contestant

»
2 months 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

»
2 months 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..

  • »
    »
    2 months 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.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I can't wait! Good luck to everybody!

»
2 months 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"!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

All the best everyone, hoping to learn some new concepts.

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

As a participant, I will read all the problems.

»
2 months 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

»
2 months 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 HealthyUG 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

  • »
    »
    2 months 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 HealthyUG 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

    • »
      »
      »
      2 months 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.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Indian Round,excited❤️

»
2 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Best of luck to all the participants :)

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

»
2 months ago, # |
  Vote: I like it -28 Vote: I do not like it

I am expecting lot of combinatorics because IIT.

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

Strange 1-gon did not ask for contribution this time :( Feeling unlucky already :((

»
2 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Hope I become a pupil this time

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

Any update on scoring distribution? UPD : added

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

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

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

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

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

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

»
2 months 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

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

    Hope this round don't become like that previous div3 round(10 mins queue time)..Let's hope for best..and All the best to you

»
2 months ago, # |
  Vote: I like it -10 Vote: I do not like it

what are subtasks? can anyone tell

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it -10 Vote: I do not like it

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

    means 2nd question has 2 sub task ...750 and 1500

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

    basically they are the same problem with different constraints

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

    Subtasks are like The problem statements are almost same, there is one easy version and one hard version of the same problem. They can make the problem harder by changing the constraints or adding more things to print out etc.

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

Second question having a subtask seems scary.

Maybe it's combinatorics :o

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hoping this tym my rating will increase a bit.

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

Bruh, what is going on with that scoring distribution.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i can not register please . help the_nightmare

»
2 months ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

:|

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Are these guys MATH FREAKS?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it -12 Vote: I do not like it

    Yes, actually. You have to be above average in maths to get IIT BHU

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

    Aren't you supposed to be Mr. Incredible?

»
2 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Goodbye Specialist.

»
2 months ago, # |
  Vote: I like it +16 Vote: I do not like it

rainboy orz !

»
2 months ago, # |
  Vote: I like it +7 Vote: I do not like it

  • »
    »
    2 months 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.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it -44 Vote: I do not like it

      Problem C was combinatorics

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

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

»
2 months ago, # |
  Vote: I like it +25 Vote: I do not like it

Whoever prepared problem B2 is an evil person

  • »
    »
    2 months 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

»
2 months 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?

»
2 months ago, # |
  Vote: I like it +5 Vote: I do not like it

I thought I would become expert today :|

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

    Same.

    My reaction after knowing the solutions is like your profile picture

»
2 months ago, # |
  Vote: I like it +27 Vote: I do not like it

Quite unbalanced problems

»
2 months ago, # |
  Vote: I like it +27 Vote: I do not like it

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

  • »
    »
    2 months 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$$$

    • »
      »
      »
      2 months 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

      • »
        »
        »
        »
        2 months 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

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

        Can you explain Soln of D in detail?

      • »
        »
        »
        »
        2 months 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
      • »
        »
        »
        »
        2 months 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
        • »
          »
          »
          »
          »
          2 months 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

    • »
      »
      »
      2 months 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))
      
      • »
        »
        »
        »
        2 months 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! :)

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

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

    • »
      »
      »
      2 months 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.

»
2 months ago, # |
  Vote: I like it +6 Vote: I do not like it

How to solve E?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve C?

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it -33 Vote: I do not like it
  • »
    »
    2 months 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).

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

      thanks

    • »
      »
      »
      2 months 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!

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

        let i = 2, j = 6 and n = 8. then every subarray with start as any of s1 = {0, 1, 2} and end as any of s2 = {6, 7} will contain the pair. Ways of choosing from s1 and s2 = 3 * 2.

      • »
        »
        »
        »
        2 months 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.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

We will soon upload the editorial for the contest.

»
2 months ago, # |
  Vote: I like it +29 Vote: I do not like it

This contest was a nightmare for me!!

»
2 months 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.

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

    i used log function which gave wrong answer

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      Simply,take the n-1 value where n is the number which has the most significant bit only.

      include <bits/stdc++.h>

      using namespace std; int main() { int t; cin>>t;

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

      }

»
2 months ago, # |
  Vote: I like it +31 Vote: I do not like it

Coordinators should take the blame for not rejecting this shit.

»
2 months 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.

  • »
    »
    2 months 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.

  • »
    »
    2 months 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.

»
2 months 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

  • »
    »
    2 months 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.

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

      Can you give some idea on how to solve it?

      • »
        »
        »
        »
        2 months 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
  • »
    »
    2 months 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.

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

    Although this is O(N^2) and won't get AC.
    dp[i][j] = 1 + dp[i+1][j] + dp[i][j-1], if I am correct, this will count weight of (i+1, j-1) twice in dp[i][j].

    it can be

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

    correct me if I am wrong!!

    I did it without dp, submission

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

      I did exactly this it was showing runtime error on 5th test case yeah I got my mistake tho you cant generate a 2-d array of 10^10 size

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

    .

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

How to solve B??

  • »
    »
    2 months 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.

»
2 months ago, # |
  Vote: I like it +55 Vote: I do not like it

caseforces xD

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

.

  • »
    »
    2 months ago, # ^ |
    Rev. 3   Vote: I like it -24 Vote: I do not like it

    I blame kassutta

  • »
    »
    2 months 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.

    • »
      »
      »
      2 months 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.

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

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

»
2 months 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.

»
2 months ago, # |
  Vote: I like it +30 Vote: I do not like it

»
2 months 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 .:(

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

    Problem B was more of a strategy question than a programming question.

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

      Yeah it was an observation based question to be precise and a bit of game theory i guess but couldn't able to notice that during the contest xdd

»
2 months 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
  • »
    »
    2 months 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

    • »
      »
      »
      2 months 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.

      • »
        »
        »
        »
        2 months 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://codeforces.com/contest/1527/submission/116811751

        • »
          »
          »
          »
          »
          2 months 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.

          • »
            »
            »
            »
            »
            »
            2 months 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 ;_;

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

              It happens :( try to stay calm maybe next time xD.

  • »
    »
    2 months 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.

    • »
      »
      »
      2 months 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.

  • »
    »
    2 months 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

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

      Nope because

      0000 -> A***

      1000 -> A**B

      1001 -> AA*B

      1101 -> AAAB

      1111 -> All 1's break

      so Alice score is forced and is 3 and bob score is 1. So bob wins.

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

        Thanks!

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

        Can't Bob reverse the string after alice converts first 0 into 1 since its no longer a palindrome?

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

          Reversal of the string doesn't have any effect on the game as we are trying to turn the string into a palindrome.
          The second operation is just a dummy move.

    • »
      »
      »
      2 months 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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
2 months ago, # |
  Vote: I like it +56 Vote: I do not like it

badly missing antontrygubO_o.

  • »
    »
    2 months 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).

»
2 months ago, # |
  Vote: I like it +30 Vote: I do not like it

D and E are boring ,and B is hard .

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

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

    • »
      »
      »
      2 months 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)$$$

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

        you can do the same dp but with DC

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

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

        • »
          »
          »
          »
          »
          2 months 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.

»
2 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Holy smokes, what a nightmare.

»
2 months ago, # |
  Vote: I like it +15 Vote: I do not like it

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

»
2 months 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

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

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

    • »
      »
      »
      2 months 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.

      • »
        »
        »
        »
        2 months 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://codeforces.com/contest/1527/submission/116857074

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

      delete

      • »
        »
        »
        »
        2 months 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

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

          oh,sorry.

        • »
          »
          »
          »
          »
          2 months 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.

»
2 months 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

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

    What if alice choose the middle 0?..then its alice who wins

  • »
    »
    2 months 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.

  • »
    »
    2 months 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

  • »
    »
    2 months 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

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

      It is given there is atleast one 0

      • »
        »
        »
        »
        2 months 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.

  • »
    »
    2 months 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!

»
2 months 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.

»
2 months ago, # |
  Vote: I like it +33 Vote: I do not like it

the most weird contest I have ever seen

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the idea for A ?

  • »
    »
    2 months 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.

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

    This worked for me I guess there maybe many more logics

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 months 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];

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

      Can you explain the thinking/idea behind this?

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

        Just tried all the cases on paper

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

»
2 months 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

  • »
    »
    2 months 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.

  • »
    »
    2 months 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'.

  • »
    »
    2 months 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.

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

»
2 months 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.

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

    what will be the time complexity of this approach?

    • »
      »
      »
      2 months 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.

  • »
    »
    2 months 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?

    • »
      »
      »
      2 months 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.

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

    Can you please share your submission

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

      Sure

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

      • »
        »
        »
        »
        2 months 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

  • »
    »
    2 months 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.

    • »
      »
      »
      2 months 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.

      • »
        »
        »
        »
        2 months 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.

        • »
          »
          »
          »
          »
          2 months 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!

  • »
    »
    2 months 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!

    • »
      »
      »
      2 months 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).

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

        Very beautifully explained! Its becomes a little tricky when you are not the one playing the game! I've come across many problems like this where you sometimes have to maintain the difference of 2 players score!

»
2 months 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!

»
2 months 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

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

    Nice explanation, a bit of typo, should be $$$a[i] = (1,3),(1,4),(3,4)$$$

»
2 months ago, # |
  Vote: I like it +29 Vote: I do not like it

»
2 months 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?

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

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

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

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

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

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

»
2 months 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!! :)))

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

Sorry, my bad...