Gol_D's blog

By Gol_D, history, 3 months ago, In English

1660A - Vasya and Coins

Idea: MikeMirzayanov

Tutorial
Solution

1660B - Vlad and Candies

Idea: Vladosiya

Tutorial
Solution

1660C - Get an Even String

Idea: MikeMirzayanov

Tutorial
Solution

1660D - Maximum Product Strikes Back

Idea: Aris

Tutorial
Solution

1660E - Matrix and Shifts

Idea: myav, MikeMirzayanov

Tutorial
Solution

1660F1 - Promising String (easy version)

Idea: MikeMirzayanov

Tutorial
Solution

1660F2 - Promising String (hard version)

Idea: MikeMirzayanov

Tutorial
Solution
 
 
 
 
  • Vote: I like it
  • +50
  • Vote: I do not like it

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

If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table to increase/decrease the constraints.

I've also added a new feature to view progress of your judgement in near real-time. (For example, the current state of your ticket, how many inputs were evaluated, etc).

If you are not able to find a counter example even after changing the parameters, reply to this thread, mentioning the contest_id, problem_index and submission_id.

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

    Can you explain ur solution

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

      in problem I made simple observation that whenever number of negative is greater

      let say r = number of negative in subarray — number of pos in subarray

      if r >0 and r%3 == 0 then subarray will be promissing

      I used divide and conquer to calculate those subarray

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

There is a solution in the f2 order_set or fenw_tree.This is awesome

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

thanks for explanations

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

In B Can someone please explain why 6 1 1 1 1 1 5 will give no in this case we eat candies like index 6, index 5 , index 6, index 4, index 6, index 3 , index 6 , index 2 , index 6 ,index 1.

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

    Give attention to this line, "Vlad decided to eat exactly one candy every time, choosing any of the candies of a type that is currently the most frequent (if there are several such types, he can choose any of them)." In your case, the most frequent one is 5 and when he eats one candy, the most frequent type is again the last one because its count is 4 and is highest. And Vlad also don't want to eat same candies in a row. That is why this case will give a NO.

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

Can anyone please point out for me the difference between these two submissions:

152864441(I used vector and got WA)

152864364 (I used array and got AC)

Thanks in advance!!!

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

    Most likely this is due to integer overflow with arrays.

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

      Can you elaborate more for me ? I'm still confused. Thank you very much!

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

        Look at expression in line 21:

        if((n == 1 && vec[0] > 1) || (vec[n — 1] — vec[n — 2] > 1))

        The condition behind the OR doesn't check for vector size, so for n == 1, then you are evaluating this: (vec[0] — vec[-1] > 1)

        Imagine this input:

        1

        1

        1

        Then:

        (n == 1 && vec[0] > 1) || (vec[0] — vec[-1] > 1)

        (1 == 1 && 1 > 1) || (1 — vec[-1] > 1)

        (true && false) || (1 — vec[-1] > 1)

        false || (1 — ?? > 1)

        So basically you are accessing vec[-1]. Depending on the value in that "illegal" memory position, it may be true or false. Same happens for arr[-1], but you just go lucky there with the memory value there at the time of the submit.

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

          Wow, now I get that! Thanks very much!

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

Can someone check my I get a memory limit to exceed the error in the c problem https://codeforces.com/contest/1660/submission/153739220

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

Does the solution of F1 take into account the adjacent situation?

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

How can I solve C. Get an Even String with dp ?