ssense's blog

By ssense, history, 2 months ago, In English

1537A - Arithmetic Array

Tutorial
Code

1537B - Bad Boy

Tutorial
Code

1537C - Challenging Cliffs

Tutorial
Code

1537D - Deleting Divisors

Tutorial
Code

1537E1 - Erase and Extend (Easy Version)

Tutorial
Code

1537E2 - Erase and Extend (Hard Version)

Tutorial

Solution by Ari.

Code

1537F - Figure Fixing

Tutorial
Code
 
 
 
 
  • Vote: I like it
  • +154
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it +80 Vote: I do not like it

This was faster than the system testing!

Thank you!

»
6 weeks ago, # |
Rev. 5   Vote: I like it -316 Vote: I do not like it

Horribly weak pretests for E1 and E2 :(

Not to mention long queues.

Round should be unrated!!!

MikeMirzayanov 1-gon ssense I_Love_YrNameCouldBeHere

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

    My guy, you haven't seen long queues, this one was no longer than 3 mintues. I saw 40 minutes long queue. Also, if you didn't think before submitting E1 or E2, it's on you. Please refrain from posting such non-sense next time.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can someone explain why long queues mean the round might be unrated? Is it cause we'll not be able to check whether our solution has passed?

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Pretty much so, but the queue has to be extreme to lead to an unrated round.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +192 Vote: I do not like it

    Although we regret not making stronger E tests, poor test quality isn't a reason to make the round unrated.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    What's the issue with pretests? Difficult problems are meant to challenge the coder. If the organizers give you large pretests so that you can find every corner case with ease, it would be useless.

    Round is fine.

    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 2   Vote: I like it +31 Vote: I do not like it

      Difficult problems are indeed meant to challenge the coder. But I don't think that means you make a person think he's got the answer right when he hasn't, hence making him solve the next question when he hasn't solved the previous one correctly.

      Also, I don't think giving WA on the pretests would as such help too much in finding the corner cases, its just to tell the contestant that you haven't yet got this question right and he should continue to work on it.

      Round is fine though, only a minor issue which isn't enough to make it unrated.

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

    I did fall prey to the weak pretests of E1. (Pretests passed but not accepted)

    But I don't think that's enough reason for round to be unrated. Questions were good and above all, it was my fault that system tests didnt pass.

    Round should unrated only if questions are super ambiguous or online judge takes too long to give verdict on submission

»
6 weeks ago, # |
Rev. 2   Vote: I like it +18 Vote: I do not like it

Adhoc Adhoc everywhere :0

I enjoyed the contest btw and I really wish you guys make more of these. Kudos (Y)

»
6 weeks ago, # |
Rev. 7   Vote: I like it -30 Vote: I do not like it

(◍•ᴗ•◍)❤

»
6 weeks ago, # |
  Vote: I like it -40 Vote: I do not like it

I'm such an idiot for not solving B but solving C

»
6 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

How accepted solutions for problem E1 rose so quickly ?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +44 Vote: I do not like it

    https://www.youtube.com/channel/UCm-7dkk1fHId1hy5vY5VVCQ

    I was wondering the same about D too. Found why.....

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

      This is horrible :(

      Everyone should report the channel now!

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I hope the moss checker catches them.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I am relatively new to CF. Any idea what is going to happen? Will the round get unrated or is the plag checker capable enough to remove any plag solutions?

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

        Plag checker usually removes people from rankings

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      nah man D was on gfg also, I think that's also a major reason

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I was wondering the same about the submission for Problem D. I was trying to crack the pattern but couldn't.

      This guy's an Indian judging by the Hashtags he has put in videos. There's a lot of cheating nowadays going on atleast involving Indians. Platforms like Codechef have become worthless because of these people.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Please delete this comment as more people are getting to know about this channel

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

    Hey, there are many telegram grps exist where they post solutions till E2.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

No original problems, just dumb adhoc problems

»
6 weeks ago, # |
  Vote: I like it -23 Vote: I do not like it

F:"It is guaranteed that the graph is connected."

There seems to be no guarantee of this condition.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +75 Vote: I do not like it

    It says the graph is connected in the first sentence and again in the input section.

»
6 weeks ago, # |
Rev. 2   Vote: I like it +197 Vote: I do not like it

In problem E, one can prove that

$$$ a^{\infty}<b^{\infty}\Longleftrightarrow a+b<b+a $$$

So just compare the prefixes using Z function.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    I have done the same. But my answer is failing for test case 43 in E1 and 93 in E2

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

      Me too, and my fault is that I forgot to judge a sqecial situation, when a suffix of the string is also its prefix, you need to cut out the suffix to get a better answer.

      Prove:That's because if you found $$$S[1,n-i+1]=S[i,n]$$$ ,it means you've already judged suffix starts from 2 to i-1, ans all of them are smaller then itself, now we judge if we cut the $$$i^{th}$$$ suffix, if we cut it, we will connect itself to it after cutting(we call it s1 ans the one that didn't been cut s2), and it can be proved that the first place that may be different is the $$${n+1}^{th}$$$ place of s2, and it is the initial string again,for s1, it is the suffix from (n mod (i-1)+1) we know that if s[x] means the suffix from x,$$$s[j(1\le j \le i)]\le s[1]$$$,so $$$s1\le s2$$$, we need to cut it.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Catch Jiangly and ORZ%

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

    What's the intuition behind this equivalence? After thinking for a while I was able to find a proof, but how do you come up with it in the first place?

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

      I have solved a problem about arranging some strings, where I needed to prove the latter relation is transitive, so I discovered and remembered this equivalence.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Will you please provide the proof for the above relation?

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

      I'm a bit late, but here is some more or less intuitive proof. We can look at strings as base-p numbers (here $$$p=26$$$, but it doesn't really matter). Obviously it's enough to compare string consisting of $$$|b|$$$ copies of $$$a$$$ with string consisting of $$$|a|$$$ copies of $$$b$$$. In other words, we want to compare \begin{gather*} \sum_{i=0}^{|b|-1}a \cdot p^{|a|i}\quad vs \quad \sum_{i=0}^{|a|-1}b \cdot p^{|b|i}\\ a \cdot \frac{p^{|a||b|} — 1}{p^{|a|} — 1} \quad vs \quad b \cdot \frac{p^{|a||b|} — 1}{p^{|b|} — 1}\\ a(p^{|b|} — 1) \quad vs \quad b(p^{|a|} — 1)\\ a\cdot p^{|b|} + b \quad vs \quad b\cdot p^{|a|} + a \end{gather*}

      And the last line is just $$$a + b$$$ vs $$$b + a$$$ (here $$$+$$$ is concatenation)

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

        I cannot understand what do you mean by $$$a.p^{|a|i}$$$ in the summation formula. Can you please elaborate more?

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

          To concatenate numbers you need to multiply one of them by some power of base. For example, if $$$a = 123$$$ and $$$p = 10$$$, then $$$|a| = 3$$$, and \begin{gather*} 123123123 = 123\cdot 10^6 + 123 \cdot 10^3 + 123 \cdot 10^0 = \sum_{i=0}^2 123 \cdot 10^{3 i} \end{gather*}

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

            Wow, amazing way to see strings. Thank you very much.

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

        Thanks man! Its amazing how things simplify after you see strings as numbers with base 26.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please tell what proof you came up with? Thank you.

»
6 weeks ago, # |
Rev. 2   Vote: I like it -7 Vote: I do not like it

.

»
6 weeks ago, # |
Rev. 2   Vote: I like it +52 Vote: I do not like it

For D, I just printed the answer for the first 100 natural numbers and found the solution...

Hopefully, I will become Orange today after 15 months :)

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

    What did you do? How did you simulate each number? I believe you need to know the optimal move, but if you know that then you actually know the answer

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

      I used dp to calculate the answer.

      Let dp[i] = 1, if alice can win when n=i,

      Simply, for any j which divide i,

      If dp[i-j] is 0 then, dp[i] is 1.

      I used this method to find answer for 100 natural numbers, then I guessed the sequence.

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

    Now you're orange. Congrats

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

    Were you familiar that these type of questions are pattern finding or did you first try to approach the question using paper and pencil before brute force.

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

      Generally (most of which I encountered), game theory questions can be guessed by writing the answer for some initial numbers.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    heres the code https://ideone.com/kNqcuK to print answers for first 1000 numbers

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    same))

»
6 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

I was thrilled to find I was able to do 5 questions only find they were of div3 difficulty overall nice round thanks for the contest

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Woow !! fast editorial Thanks :)

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

Problem D: Can someone explain me the reason for "If number is odd then opponent (BOB) will always win"?

I didn't get it.

Thanks

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    for odd you will have divisor odd ,now if you subtract odd number from odd number you will find even number for even numbers you may refer above in editorial

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If n is odd, then in the first move Alice have to choose odd divisor. and if u subtract a divisor from a number then that divisor also remains divisor of the new n.

    so bob will just choose the previously taken odd divisor of alice, and since the number is odd so it will be zero after odd time of subtraction. (odd*odd=odd). and the last subtraction will be made by alice (because total number of subtraction is even),and alice will make the number zero means he is subtracting the complete number so alice will loose.

    Hope you will understand thanks!!.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for editorial.

»
6 weeks ago, # |
  Vote: I like it +34 Vote: I do not like it

The problemset was fairly interesting.

»
6 weeks ago, # |
Rev. 4   Vote: I like it +61 Vote: I do not like it

Check out my simple greedy solution for E2. 119887467

Explanation and Code
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Can you please explain the else if statement?

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

      You can cosider the given testcase s= dbcadabc. When i=4(0 based indexing) s[i]==s[j], then we will take this character in our prefix if the next character {(i+1)th} is less than or equal to s[1], which is 'b'. If that also came to be same then we will check the next one, like in this example , s= dbcadbbc, we will compare s[6] with s[3].

      I know it's a bit hard to understand, but I have tried my best :)

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

        How did you come up with this idea ?? Is there some algorithm or practice?

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it +9 Vote: I do not like it

          I simply followed the greedy approach to get the lexicographically smallest string. But, some people are talking about some Z function, I have no idea about it.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Underrated

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

    Very clean soltuion!

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

    Great solution.. I saw many solutions but all of them talked about some Z function.. I am glad I ran over this one.. Thanks alot

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    nice solution

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

    Thank you for making this problem soo simpler to understand.

    One point I would like to mention is: In second condition we don't need to take modulo, as j will always be smaller than i and even if j exceeds (last+1), substring starting from s[0] will be equal to substring starting from s[last+1].

    link to solution

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

      Yeah, you are right, there is no need to take the modulo.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I had this same solution but since no one mentioned it I thought I am missing something but couldn`t find anything wrong with it. Now I can rest.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Great Solution! Learned Z function for this problem, but couldn't understand the tutorial. Finally found this solution. Piece of cake:)

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

    I just wanna say this is an brilliant solution

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thx for great contest and editorial!

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

Problem statement was quite clear.awasome explanation.

»
6 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

contest was really good but a little bit easy than other div2 rounds

»
6 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

E1 Test 43 should have been a pretest.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

It was fun doing this contest, and yes this is codeforces .

»
6 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

Problem D is amazing!

»
6 weeks ago, # |
  Vote: I like it +47 Vote: I do not like it

For E2, I have a simpler solution that, I believe, implicitly uses the Z-function concept, however is not at all a prerequisite to understand. Also, I’m not 100% sure about correctness; feel free to hack in that case.

The editorial for E1 establishes the fact that the optimal answer is merely a repetition of a prefix. We will check which prefix length is optimal to be repeated, starting from $$$1$$$ to $$$N$$$. Let the current optimal length of prefix be $$$len$$$.

The casework is similar to what is described in the editorial for E2:

If $$$s_i > s_{i\, \%\, len}$$$ (0-based indexing here), the prefix should not be extended any further; no prefix beyond this point is optimal, and it is optimal to keep repeating our current optimal prefix. So we simply break.

If $$$s_i < s_{i\, \%\, len}$$$, it is more optimal to extend our prefix up to this point; hence we do it, i.e. set our optimal prefix length to $$$i + 1$$$. This needs some more explanation, so bear with me for the next couple of lines.

There’s also the more interesting case of $$$s_i = s_{i\, \%\, len}$$$, but before that, let’s establish an invariant: So far in the algorithm, the string made by the repetition of the prefix, and the substring $$$s[0:i]$$$; both are equal. How? Well, we break when $$$s_i > s_{i\, \%\, len}$$$, and in case of $$$s_i < s_{i\, \%\, len}$$$, we simply extend our prefix up to here, making it equal.

Let’s deal with the $$$s_i = s_{i\, \%\, len}$$$ case now: Here, we cannot decide at this moment, whether repeating the current prefix or extending the prefix up to this point is more optimal. Hence, we just proceed ahead.

Further along the line, if $$$s_i > s_{i\, \%\, len}$$$, we realize that repeating our current prefix is indeed the most optimal, and we need not check further, just like in the previous scenario. Hence we break.

However, if $$$s_i < s_{i\, \%\, len}$$$, we realize our prefix repetition was non-optimal; how do we go back, i.e. change our prefix now? That’s where our invariant comes in. Our prefix repetition string was equal to the substring $$$s[0:i - 1]$$$, and becomes unequal at index $$$i$$$; hence extending our prefix length simply means changing the prefix to $$$s[0:i]$$$.

This helps us maintain an $$$O(N)$$$ solution. 119889474

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

    Your code is nice and simple. But didnt understand your casework for the case when si = si%len (in your code, you are not dealing with this case separately as well).

    You say "Here, we cannot decide at this moment, whether repeating the current prefix or extending the prefix up to this point is more optimal. Hence, we just proceed ahead.", but you are never comparing these two possibilities in further execution. You are just assuming that current answer will be better until you find the next mismatch.

    For example, your third last paragraph says that you are breaking the loop if you found si>si%len, but this just tells you that the retained prefix is a better answer than current index, however you are still not comparing with the other possibility which you ignored previously. What if you would have achieved a better answer using that prefix?

    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 2   Vote: I like it +7 Vote: I do not like it

      Thank you for pointing this out. I believe my write-up is still incomplete, and the $$$s_i = s_{i\, \%\, len}$$$ case requires another explanation. Let me rewrite this particular case.

      When $$$s_i = s_{i\, \%\, len}$$$, I now claim that maintaining our original prefix is always more than, or equally optimal to changing to this prefix.

      Proof

      Hence, in our algorithm, we make no update to the optimal prefix length, and proceed forward. This should make the solution more complete, if not fully.

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes, now your solution is complete :) I`ll also suggest the authors of the editorial to mention that in the si = si%len case, its safe to assume sticking to the current prefix is a better choice than switching.

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Can you please prove or explain these two things:

          1. From the third paragraph, "Hence, we are simply left with proving that $$$pref_{len(x)−len(y)}(x)>=suf_{len(x)−len(y)}(x)$$$ to prove that our current prefix repetition is optimal." Why does this imply our current prefix repetition is optimal? I think in the case of equality $$$(pref_{len(x)−len(y)}(x) = suf_{len(x)−len(y)}(x))$$$, we also need to check further by comparing the string $$$xxxxx...$$$ starting at the third $$$x$$$ with the string $$$suf_{len(y)}(x) + yxyxy...$$$

          2. From the last paragraph, "This means there exists an $$$i$$$ where $$$pref(x)[i]<suf(x)[i]$$$. This can actually be avoided by repeating a prefix smaller than our current optimal one, but this shows that a smaller prefix length yields a more optimal answer, which violates the invariant of our algorithm." If $$$len(y) > i$$$ (0-based indexing), we can repeat the prefix of length $$$len(y)$$$. However when $$$len(y) \le i$$$, I couldn't find any prefix of $$$x$$$ to repeat that yields a more optimal answer.

»
6 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Thanks ssense I_Love_YrNameCouldBeHere for such a great round . Today I got my best rank .

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

I am getting a runtime error for the solution of 1537C - Challenging Cliffs. Will anyone please help me. Here is my solution submission:

Thanks in advance!

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your value of mini is — 9e7 + 9999999. It should be 9e8 + 99999999 :)

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In order to avoid this kind of mistake, I suggest initializing mini as the difference between the first two elements of your sorted array, as n is at least 2, and just do the loop from i=1

»
6 weeks ago, # |
  Vote: I like it +40 Vote: I do not like it

When you brute-force problem D for small N and spot the pattern :

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

I finished E1 10 seconds before the round finished. Wasn't able to submit :(

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

    The exact same thing happened with me. I even switched to Python to code it up quicker, but I just missed the deadline. :(

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

To get difficulty n−1, we need mk to be the shortest mountain and mk+1 to be the tallest mountain. This will only happen if n=2. Regarding the Problem C tutorial, This can also happen for n>2 when all elements are the same, isn't it?

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

I see a lot of people getting relatively low positive delta (even negative delta) because of the cheaters. This is so unfair!

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

In problem E, can someone please prove why it's optimal to keep duplicating a prefix? The editorial's proof isn't clear to me.

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

    Think like this, might be helpful. Without loss of generality in the first step you have to double some prefix (after deleting some characters from the end). As these are the only two operations available. So initially you want to double something which gives you maximum advantage i.e it is at least smaller than the initial string given to you, in fact, you will select the very first occurrence of the prefix that when doubled is smaller than the original string given. So in brute force double every prefix and check if it is smaller than the original string. When you find one break. now suppose you have selected prefix P and now you are getting PP after doubling. Now you perform the same step as above i.e finding some prefix of PP which when doubled gives smaller string than PP. And I can assure you , you will not find any such prefix in the new string PP which will give you advantage as in earlier case (Just work it out). So you are left with only option of repeating P, as this will at least not give you lexicographically bigger string. Hope this helps.

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

      Now you perform the same step as above i.e finding some prefix of PP which when doubled gives smaller string than PP. And I can assure you , you will not find any such prefix in the new string PP which will give you advantage as in earlier case

      in fact, you will select the very first occurrence of the prefix that when doubled is smaller than the original string given.

      I couldn't prove either of these.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice round! Easy version of D. I got bamboozled because of it.

»
6 weeks ago, # |
Rev. 5   Vote: I like it +15 Vote: I do not like it

Codeforces 726 Div2:E1 solutions implementations: so innovative these guys : ) (not even in variables in some solutions and getting +100 or so)! 119889554 119889070 119884298 119890054 PS: check their other solutions similarities in every aspect! Please,Strict actions should be there. MikeMirzayanov (sorry for disturbing)

Mass-copying

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

Has anyone managed to pass E2 using binary search and hashing. I know in that 2s TL it won't pass as it will be nlog(n) and is giving TLE. But now I saw binary search in the tags. So just curious to know has anyone passed using binary search.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    119900135 one of my friends solution.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks, man. I was calculating the power inside binary search which was creating an extra log factor, precalculating power fixed the issue.

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you explain your binary search based solution please?

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

          sure, Actually, I am simulating the Z function using binary search as I don't know Z function :(

          First precalculating the hash of the string and the prefix hashes. Now if for each index i I want to find out the first index where the prefix from 0 to i-1 and string starting at i differ.

          To do that I am using binary search. Before the first mismatch of both strings, both the hash values will be same , using this fact in binary search to find the first mismatch character and checking whether it is smaller or larger than that position in the prefix.

          • »
            »
            »
            »
            »
            »
            6 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Two questions:

            1. Is your hashing collision free?

            2. Can you explain why are you doing this "Now if for each index i I want to find out the first index where the prefix from 0 to i-1 and string starting at i differ"

            • »
              »
              »
              »
              »
              »
              »
              6 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Well technically no hash function can be collision free I guess. But the probability of collision is very very less I believe.

              Also for this "Now if for each index i I want to find out the first index where the prefix from 0 to i-1 and string starting at i differ". As far as I know Z function does exactly this, i.e it returns the longest prefix where s and the string starting at i match. And secondly I need to know this to know whether doubling this prefix will give me better answer or not, by comparing the first mismatch.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the thought process/idea behind D? I am finding it difficult to grasp the editorial.

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

    if n is odd, for eg 15, so their factors are 1,3,5,15(that it's all odd) you can see if we subtract any divisor D, the number will be even, but it cannot be a number of the form 2^k, because

    • (n%D)==0, so we subtract D from n, it becomes n-D and it must be divisible by D, so n-D, cannot be in the form of 2^K.

    so this implies if the starting n is odd, then Alice will make it even, and similarly, Bob will make again the number odd since a prime number is either 2 or the odd number, so Alice always gets the odd number, and hence Alice will lose.

    if n is even and not in the form of 2^K, so similarly Alice will always make it odd and so, Alice will win.

    Now, if n is of the form 2^K, then k times the game will be played, if both play it optimally, otherwise the one who don't half it will always lose, for eg 16 = 1, 2, 4, 8, 16, if Alice chooses 2 then it becomes 14 and it is the even number (not in the form of 2^K), so Bob will win. So, both try to half it at every step, so if k is odd then Bob will win otherwise Alice.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah, understood it. Thanks :')

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you pls explain why this condition always holds "so n-D, cannot be in the form of 2^K." ?

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

        Numbers in the form of 2^k have only even divisors, but here, a number n has an odd divisor D.

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          yeah, you are right. if number is in the form of 2^k for ex — 2*2*2 then all factors have to be even. thank you!!!

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

I`m seeing solutions for E2 where people are not dealing with the case si = si%len at all (going by the editorial, that part is important as well).

Can anyone explain how these solutions are working?

Example: Here

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Just a small detail and boom, lost 2 problems :(

»
6 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

I don't really get how my solution to problem E2 works lol. First of all, I only chose the shortest prefix which is lexicographically smaller than the whole string. Moreover, I found this first prefix naively by comparing char by char after compressing same consecutive characters. (So the string "aabcccb" gives the array {2, 1, 1, 3, 2, 1}. Each cell is the length of the jump to first different char). I don't understand why it is correct and why I don't get TLE. If someone could explain it would be cool. Solution: https://codeforces.com/contest/1537/submission/119930955

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

The sample code solution for 1537C — Challenging Cliffs seems wrong, or not?

It'd produce $$$m_{k+1}, m_{k+2}, ..., m_{n}, m_1, m_2, ... m_k$$$, which is not what is described in the tutorial.

Or have I misunderstood anything?

»
6 weeks ago, # |
  Vote: I like it +26 Vote: I do not like it

E1/E2 should contain multitests and every short(length<=4) string should checked the pretests :(

»
6 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

System testing was slower than internet Explorer. XD!

»
6 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Problem F is nice.

Tried to cover all the observations in my solution video :) Explanation Link

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I think just a KMP-like algorithm can solve E2 by greedy.

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

Maybe there is a problem which used a conclusion pretty like problem F(in Mandarin) You can see the conclusion there(also in Mandarin)(maybe u can use google translate :))

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What if in the first question the array consists of -10000 five times and sum we get is -50000. So we have to add +10000 five times and then one more to make it divsible by current size of array. In question, the constraint given to the inputs of array was -10000 <= A[i] <= 10000. Am i correct or something is there which I am not getting?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did the same mistake during the contest, the problem states that we can add any non-negative integer so if sum < n we will always print 1

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

For E2: At i-th position, I just compared the i-th prefix with the n-th prefix and got AC 119938778

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I guess problem D was the most interesting one rest were pretty easy!

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

MikeMirzayanov I think the rating points given for this contest needs to be re-evaluated, as I didn't solve any problems, with -3 penalty, still I got +37 for this contest whereas all others who solved one or more problems got negative points, pls take a look.

»
6 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

My Simple greedy Solution for E2 119941150

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

Does anyone come up with answer for D without bashing a bunch (like first 50) of small case? It wasn’t until I write a code to look at first 2000 answers that I spot the $$$2^k$$$ exception. I want to know the intuition behind this pattern if someone come up with it without bruteforce pattern to look.

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

    I tried to find some strategy or some sort of invariant which Alice can use to win. I wrote $$$n$$$ as $$$n = 2^k N$$$. Alice can give Bob $$$N(2^k - 1)$$$ which has all odd divisors and Alice is guaranteed to get an even number again. Now only exceptions are when $$$k = 0$$$ or $$$N = 1$$$.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Me waiting for system testing to judge my answers ... Meanwhile ssense with the lightning fast editorial ... HOLD UP ... HERE IS THE EDITORIAL :) thanx mannnn...

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

wonderful solution B,i can't realize this solution in contest so that i write 84 line code to ac...

»
6 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

include<bits/stdc++.h>

using namespace std;

define ll long long

int main() { ll t; cin>>t;

while(t--)
{
    ll n;
    ll a[n];
    for(ll i=0;i<n;i++)
    {
        cin>>a[n];
    }
    sort(a,a+n);
    ll index1,index2;
    ll min=10000000007;
    for(ll i=0;i<n;i++)
    {
        if(abs(a[i]-a[i+1])<=min)
        {
            min= abs(a[i]-a[i+1]);
            index1=i;
            index2=i+1;
        }
    }
    cout<<a[index1]<<" ";
    for(ll i=0;i<n;i++)
    {
        if(i!=index1 || i !=index2)
        {
            cout<<a[i]<<" ";
        }

    }
    cout<<a[index2]<<endl;
}

} can anyone tell me where am i wrong in this code?? this a solution of c

»
6 weeks ago, # |
Rev. 9   Vote: I like it +14 Vote: I do not like it

insight I used for E1/E2:

a bit long but simple
»
6 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

problem D was same as this leetcode problem: link

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But LeetCode problem gives $$$n \le 10^3$$$, whereas the Codeforces edition has $$$n \le 10^9$$$. This makes the problem drastically harder because a naive memoization/recursion will work on the LeetCode, but not the Codeforces rendition.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problems like D — Deleting Divisors, how to spot these patterns of even, odd, power of 2? I could only write a brute force code which was (obviously) giving TLE. So how to spot these patterns in future problems?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Help!!! Why my solution to problem E2 failing at case like 'baaaaaaaaaa...'. I precomputed the LPS and used it to compare the characters. Checker cmnt is also not showing any difference.(https://codeforces.com/contest/1537/submission/119930117)

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I think there is a typo for problem D code, cout << mn << "\n"; where does mn come from?

»
6 weeks ago, # |
Rev. 4   Vote: I like it +3 Vote: I do not like it

I had a different solution for D. Calculate the prime factorisation of $$$n$$$.

Let it be, $$$n=p_1^{k_1}\cdot\ p_2^{k_2}\cdots\ p_m^{k_m}$$$

Let $$$S=(p_1-1)*k_1+(p_2-1)*k_2+\cdots +(p_m-1)*k_m$$$

Now we can reduce $$$n$$$ until it becomes some $$$p_i$$$ or $$$1$$$.

Then possible moves players can make are: $$$S -p_i $$$ for some $$$p_i$$$ in prime factorisation of $$$n$$$ .

Check if any of these possible moves are odd, then there is always winning state for Alice otherwise Bob will win.

More explanation

Solution:https://codeforces.com/contest/1537/submission/119883715

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

    That's a nice approach to the problem. But as $$$\sum(p-1)$$$ is even $$$\forall p\ ( p \in prime \land p \neq 2)$$$, we only need to check power of $$$2$$$. For an odd number of moves either $$$n$$$ must have an odd divisor or power of $$$2$$$ must be even. I think this then reduces to the same as the editorial proof.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1537/submission/119973061 this shouldn't pass right? or some proof or logic explains why it passed?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't understand proof of E1. Can someone please explain?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same here.

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

      it is easy to understand the ans is the prefix string of s, so we suppose current ans is $$$a(1\le a\le i)$$$, now we need compare $$$i+1$$$ and $$$a$$$.

      if $$$s[i+1]<s[i\%a+1]$$$(pos begin at 1), then $$$i+1$$$ is bterr than $$$a$$$.

      else if $$$s[i+1]>s[i\%a+1]$$$,$$$i+1$$$ is worse.

      else if $$$s[i+1]=s[i\%a+1]$$$,$$$i+1$$$ is worse,becase $$$s[1:a - (i \% a + 1)]\ge s[i\%a+2,a]$$$,if not $$$a-(i\%a + 1)$$$ is better than $$$a$$$

      My English is poor becase I am a Chinese student. Do you understand me?

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

Why 2-pointers is not in the tags for E2 ? submission . EDIT: Now 2-pointer is there.

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

[deleted]

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

This round was easy compared to previous div2 rounds

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

I tried erase and extend easy version after reading and understanding the editorial then i coded it in python but i got tle while the same code in c++ has ac . Can someone help me to know how can the python code be optimized .

this is my solution https://codeforces.com/contest/1537/submission/119926280

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem F if It is NOT guaranteed that the graph is connected . Then do we have to check for each connected component separately??

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Huh? You have a connected undirected graph made of n nodes and m edges. It literally says it's connected.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No, I'm saying what is if the problem said that its not necessary that graph is connected then how to solve that problem !!

»
6 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Really poor Editorial for F. You just stated a bunch of necessary conditions and didnot bother to prove that they are sufficient. can ssense or anyone explain why sums of both colors being equal in the bipartite case is sufficient ?

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it +16 Vote: I do not like it

    For Bipartite:

    Let's suppose two colors are black and white. We can solve for black by adding using the edge connected to those nodes. With this, we also get that we change white by that amount, so the sum in white is the desired sum.

    Now, suppose some node is not working yet. Then, it must be in white and there must be another node that still doesn't work. Find those two, then we find any path connecting those. This path will have an even length (because we traverse from white to white) thus we can do something like +a, -a, +a, ..., -a. This operation would increase the first node by a, reduce the endpoint by a, and do not affect the rest. Thus, we reduce down one white node. Doing this until no node (that doesn't match) left is possible since the sum in white is already the sum we want after we doing black. So, we are done.

    For the sake of completion, let me explain the case of not bipartite as well.

    We can do the same coloring scheme, and we can increase or decrease the sum of white color to match that. Then, we delete those out and left with a spanning tree which is bipartite. Thus, we can follow the same algorithm to solve those nodes colored in white.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for the nice explanation!

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

      Can u explain the case for not bipartite again?? What are u deleting to get a spanning tree??

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

        Suppose we get a (non-bipartie) graph G, we can find one spanning tree called T. Then, we color black-ans-white corresponds to T. Since G is not bipartite, there exists node connecting same color. WLOG, it’s white. Then, we can solve for black in the same manner, and change sum-value of white using that node. Finally, we focus back to T and use only edge inside T, we would get same scenario as I described in bipartite case.

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

E1 editorial not clear. the proof part

someone help me pls

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice problem, not very difficult but make me cry. qwq

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

anyone got the binary search solution for e2? i'm not quite familiar with that z-function (i'm planning to learn it soon, but it would be nice to know different solutions)

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

anybody give me the link of video solutin of e2 problem ,i learned about the z function but i did'nt understand the solution and editorial please help me

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem F, when the graph is bipartite, I can understand that when the condition "sum1 equals sum2" not holds, the answer is No. But I can't understand why answer is Yes when the condition holds.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I got a greedy algorithm on E1 problem, and I failed test 5. Can you tell me why I was wrong? Thank you! My solution: https://codeforces.com/contest/1537/submission/119877862

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    try 4 8 cacb

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    for index i, just checking if it is greater than s[0] or not and then replacing rest of the part is not enough. Even if(s[i]==s[0]),check if(s[i+1]>s[1]) and so on. If s[i+j]>s[j] such s[i+j']==[s[j'], 0<=j'<j then also s can be repeated from i onwards. Consider the case

    6 6
    dcbdce
    

    correct ans is 'dcbdcb' not dcbdcd

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

I don't understand the proof in the E1. "Let's relax the requirement so you have a position in the string and each time you either return to the beginning or advance to the next character." What is meant by above ?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

problem B so dark, bruh, lmao !

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

import java.io.*; import java.util.*; public class MyClass { public static void main(String args[]) throws IOException { BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); int t=Integer.parseInt(br.readLine()); while(t-- >0) { int n=Integer.parseInt(br.readLine()); long arr[]=new long[n]; String s[]=br.readLine().split(" "); for(int i=0;i<n;i++) { arr[i]=Long.parseLong(s[i]);
} Arrays.sort(arr); StringBuilder sb=new StringBuilder(); if(n==2) { sb.append(arr[0]+" "+arr[1]); //System.out.println(arr[0]+" "+arr[1]); } else { int pos=-1; long min=Long.MAX_VALUE; for(int i=1;i<n;i++) { if(min>arr[i]-arr[i-1]) { pos=i; min=arr[i]-arr[i-1]; } }

for(int i=pos;i<n;i++)
            {
                sb.append(arr[i]+" ");
                //System.out.print(arr[i]+" ");
            }
            for(int i=0;i<pos;i++)
            {
                sb.append(arr[i]+" ");
                //System.out.print(arr[i]+" ");
            }
        }
        System.out.println(sb);
    }
}

}

its giving TLE on test case 60. can anyone please help me this is question number C

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

This is the easiest "Two pointer approach" for E1 and E2.
119946716

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In Question C if input is 7 1 1 1 2 2 2 2 the max clifs possible if 3 while program will give 1

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    read the question properly its walking uphill or flat is harder than walking downhill

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

Hi guys, I have a question in problem F: how to prove

Unable to parse markup [type=CF_MATHJAX]

where

Unable to parse markup [type=CF_MATHJAX]

is a sufficent condition for the answer when graph is a biparty ? The necessity is obvious but I can't prove the sufficiency. Thanks guys!
»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

//Erase and Extend (Hard Version), by two pointers

include "bits/stdc++.h"

using namespace std; int main(){ ios::sync_with_stdio(false); string str; int n, k; while(cin >> n >> k){ cin >> str; int last = 1; int first = 0; int len = 1; while(last < n && last < k){ if(str[last] > str[first]) break; if(str[last] == str[first]){ first++; last++; } else{ first = 0; last++; len = last; //save the length } } //cout << len << endl; //continue; string ans = str.substr(0, len); int cnt = k / len; int rem = k % len; while(cnt--) cout << ans; for(int i = 0; i < rem; i++) cout << ans[i]; cout << endl; } return 0; }

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

My Solution of E2 (and E1 as well)

https://codeforces.com/contest/1537/submission/120335720

I greedily pick the best prefix. Though I read the editorial for this problem I am not sure why the code implementation was so long.

PS: MY PURPOSE OF POSTING THE CODE LINK IS THAT MAYBE SOMEONE CAN PINPOINT IF I HAVE WRONG LOGIC OR CODE AS other COMMENTS MENTION WEAK TEST CASES FOR THE PROBLEM.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For E2 :

Let's say we have three pointers A, B, and C. Where C represents the best prefix of the string which when repeated and then shaved off from the end to reach a length k would give the correct answer. A is the pointer in the best string, that we have found until now, and B is the pointer to the current character in the string we need to compare with A.

Now, let's start with A = 0, and C = 0, and B = 1, which means that a string containing only the first element is the best answer until now, and we need to compare s[A], and s[B] now.

There can be three conditions:

  1. $$$s[A] < s[B]$$$ : In this case, since the newer character is more than the first element, we should reject it. Why? Let's say we have "dbcae", when you have A=0, and B=4. Now in this case 'd'<'e', so we will reject 'e' and declare the current best as the answer, which in this case would be "dbca". Now, if we repeat it, let's say for k=8, then it would become "dbcadbca". But in the case, we took in the 'e', it would be "dbcaedbc", which is lexicographically bigger. So no matter if anything smaller than this is present in the string, the answer can not be made better. So we end our loop here, and just print the answer.

  2. $$$s[A] > s[B]$$$ : In this case, the newer character is actually better than the original character. So the answer is actually better off using the newer longer string, instead of the older one. So in this case, C is set to B (the new best), A is reset to zero, and B is increased by one.

  3. $$$s[A]==s[B]$$$ : In this case, we don't know whether we are going to get something better, or not. So if we have "dbcbdbca", and A=0,B=4,C=3 then you have s[A]=s[B]. Now this repetition can actually lead to something that is better than repeating the original answer. Like for example, if we move forward, s[3]>s[7], which means that C=7 is the correct answer,instead of C=3. As "dbcbdbca" is better than "dbcbdbcb" (if k=8). So in this case, we just simply increase A, and B. Just a little corner case though : if A has reached C (the former best), it would mean that the original string has just repeated itself, then there is nothing more to compare. The B value is actually a better choice, so C=B, A=0 and B++ is done.

This loop is followed until B reaches n.

Here is a submission using this approach : submission

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I am unable to figure out the issue with my problem F submission. I am simply following 3 steps:

if the summation of the difference is odd -> "NO"
else if (not bipartite graph) || (sumOfDifference(color-0) - sumOfDifference(color-1)) == 0 -> "YES"
else "NO"

I am trying to find the bug for the last 2 hours but no luck so far. Please help.

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Problem D is really amazing and its tutorial is great!