Aris's blog

By Aris, history, 2 years ago, In English

1690A - Print a Pedestal (Codeforces logo?)

Idea: MikeMirzayanov

Tutorial
Solution

1690B - Array Decrements

Idea: MikeMirzayanov

Tutorial
Solution

1690C - Restoring the Duration of Tasks

Idea: MikeMirzayanov

Tutorial
Solution

1690D - Black and White Stripe

Idea: MikeMirzayanov

Tutorial
Solution

1690E - Price Maximization

Idea: Vladosiya, Aris

Tutorial
Solution

1690F - Shifting String

Idea: MikeMirzayanov

Tutorial
Solution

1690G - Count the Trains

Idea: Aris

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

| Write comment?
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it -21 Vote: I do not like it

speedforces

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

Wasn't it round 797?

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

For users (like me) trying to learn implementation, I suggest looking at jiangly's submissions of these problems.

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

For G, can someone please give a proof to "remove in total no more than 2*n elements from the set".

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

    The set contains the starts of trains. Initially there could be at most n trains. When the speed of a train is reduced, you can at most create one new train. This adds m additional trains. It is possible that every element could be removed from the set, so in total, n+m elements can be removed from the set.

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

      is it possible that some subset of trains are getting removed and added? I mean after we remove a starting train from the set, it can be added as well afterward. doesn't this yield to an n^2 solution?

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

        Not sure what you mean. Each operation can only create one new train. The operation can only create a new train with start index at the index of the operation. Indices before the operation will not be affected and indices after will either match the new value at the index of operation (and thus will be within the same train) or will not be affected.

»
2 years ago, # |
  Vote: I like it +5 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 (or edit compressed parameters) to increase/decrease the constraints.

If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).

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

Hi, for problem $$$A$$$, since $$$n \leq 10^5$$$ we can use brute force. But I want to know $$$\mathcal{O}(1)$$$ solution. I saw codes from top people from standings. But I don't understand the idea

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

    We want to have the minimal value of h1.

    We know that h1 + h2 + h3 = n, so we should maximize the values of h2 and h3 in order to minimize the value of h1.

    The "best case" scenario would be that n mod 3 = 0, so that we can set: h3 = n/3 — 1, h2 = n/3 = h3 + 1, h1 = n/3 + 1 = h/2 + 1. (because n / 3 is a whole number)

    This is the best case because h1 > h2 > h3 is required by the problem statement.

    If n mod 3 = 1, then (n — 1) mod 3 = 0. We can perform the above solution for n — 1 and get: h1 = (n-1) / 3 + 1, h2 = (n-1) / 3, h3 = (n-1) / 3 — 1. We have one extra block though, and the only way to place it without disrupting the inequality (h1 > h2 > h3) is to place it at the top of h1, making h1 = (n-1) / 3 + 1.

    If n mod 3 = 2, we can follow the above process once again, this time placing our second extra block at the top of h2 making h2 = (n-2) / 3 + 1. Since h1 = (n-2) /3 + 2, the inequality is not disrupted and h1 stays minimal.

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

    Without any ifs greedy solution:

    n — input; h1, h2, h3 — pedestals;

    We now that that h2 >= h3 + 1 and h1 >= h2 + 1 >= h3 + 2 => n = h1 + h2 + h3 >= 3 * h3 + 3 => max h3 equals h3=(n-3)/3 (rounding down).

    Than just set s = n - h3

    Using the same logic s = h1 + h2 >= 2 * h2 + 1 => max h2 equals h2 = (s - 1) / 2 (rounding down again). And h1 = s - h2

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

    in contest submission: 159731522

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

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

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

Can anyone share their approach for problem F?

Why are we always considering the minimum shift? As we are taking LCM, it might be better to take a larger number if the LCM with ans is getting minimized.

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

    deleted.

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

      consider this string abcabcabc there is a period of length 3 so shifts are [3,6,9] notice that all shifts are multiple of period 3 so that minimal number is the best as it
      contains the minimal number of prime factors.

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

        Understood! Thanks!

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

        but what if shifts like 2,5 are possible?

        upd: got it sorry.if a,b is possible then a-b is also possible.

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

In problem F, the rotation of string will cost o(n^2) time. it's ok for this problem. But I want to know is there any o(n) approach to do this work?

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

    You can use KMP algorithm for $$$O(n)$$$ search, or hashing will also give you average of $$$O(n)$$$ time.

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

    Damn, I didn't even see that the constraints were so less up until I saw your comment. My approach was using a rolling string hash, which works in O(n) time and O(n) space.

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

Submision:https://codeforces.me/contest/1690/submission/159836832

Getting a TLE on 147, Can I get that testcase ?

My solution appears to be O(m log n)

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

In problem F, I have another approach, using the Chinese Remainder Theorem.

My approach:

  • Apply one operation to avoid result 0
  • Use DFS to find the cycles
  • Apply operations individually in each cycle, find the "first" and "second" time when it is same as the input after applying the shifts.
  • Create the equations like "x % (second — first) = first"
  • Apply the Chinese Remainder Theorem and add one to the answer (because of the first step of my approach)

I hope this could be useful for someone.

My code: https://codeforces.me/contest/1690/submission/160003457

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

Is there any DP idea for problem D, as at every W we have a choice to color it or not. If we color it then it contributes 1 to our cost and increases the max length of consecutive B so far by 1, if we choose not to color it, then from here max length becomes 0. Initially I thought of this approach but couldn't code it out. Am i thinking right/wrong in this direction ?

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

    The problem can be solved with two pointers. If you want to solve it by DP, you surely can, but that code will also boil down to a two-pointer code essentially. Since we want to maintain k consecutive Blacks, we do not have a choice for W to add it or not. If it happens to come inside our string of length G then we have to consider it otherwise not.

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

can someone tell me where this is failing? 160027351

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

    Take the string $$$abab$$$ for example, it only need $$$2$$$ operations to repeat itself, but your code will calculate it as $$$4$$$

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

Is time complexity $$$m \log^2n$$$ per test case not allowed in G? I'm getting TLE for this submission 160038706. I've used segment tree with lazy propagation, and I've also used binary search. I'm making a range query for every iteration in the binary search, that's why its $$$m \log^2n$$$.

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

    Don't quite know why you are getting TLE, but I used binary search + segment tree with lazy propagation and it passed. Here's my submission : https://codeforces.me/contest/1690/submission/159839709

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

      That's a nice method, initially, I had written the exact same segment tree implementation as you (the cp-algorithms one lol), but I wasn't able to figure out the distinct numbers part, so I had to modify the type of queries I was making. Complexity wise our codes seem to be the same, maybe yours has a lower constant factor? If someone can pinpoint the reason for me getting TLE that would be really helpful.

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

In F why does having the same character at multiple positions doesn't come into consideration?

I.E. Couldn't there be a string such that the resultant string is the same as the original but indices are not the same since the same characters are occupying each other's place?

Example:

Original string and indices:

A B A B
0 1 2 3 // indices

After some permutations:

A B A B
2 1 0 3 // original indices of chars

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

1690B - Array Decrements CODE: 161337471

PLZ CAN ANYONE TELL WHAT I AM DOING WRONG WITH THE CODE

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

Can anyone help me figure out why 162651629 is getting run time error? I tried using cfstress.com but for some reason, it doesn't work. All my manual testing doesn't produce a run time error either.

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

    CF Stress returns that verdict because your code doesn't compile on my machine, due to this line:

    min(mini, (long long)times / s.size());
    

    It complains that that the second argument is long long unsigned. Explicitly typecasting this makes it compile, resulting in a counter example: Ticket 15364

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

Another div 3 is coming soon

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

1690C The time limit exceeds on the fourth test for whatever reason.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Alternative solution to G which uses 2 segment trees: https://codeforces.me/contest/1690/submission/194648218

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

for problem G, I use a segment tree to keep track change made in the array and count the number of different elements in the array after each query my submission : https://codeforces.me/contest/1690/submission/262284939

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

In the problem D Back and white stripe , isnt the no. of segments of length k in string of size n is

(n-k+1) instead of n-k written on the editorial