Vladosiya's blog

By Vladosiya, history, 2 months ago, translation, In English

1932A - Thorns and Coins

Idea: denk

Tutorial
Solution

1932B - Chaya Calendar

Idea: Vladosiya

Tutorial
Solution

1932C - LR-remainders

Idea: MikeMirzayanov

Tutorial
Solution

1932D - Card Game

Idea: goncharovmike

Tutorial
Solution

1932E - Final Countdown

Idea: step_by_step

Tutorial
Solution

1932F - Feed Cats

Idea: denk

Tutorial
Solution

1932G - Moving Platforms

Idea: denk

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

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

Tutorial after 3 days. Why?

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

hii can anyone help me with my solution[submission:247597946] for which I am getting tle for test case 2. My Idea :- I have used cumulative sum to get the number of cats at any position i and prevnum array to point to the index (x) if i use the index (i) to feed my cats , than simply use dp to calculate dp[n] .Plss help me to get past TLE.!!

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

In F, we consider all values from 1 to N. If we only checked points that are either start of end of an interval, then it gives WA. Why could that be?

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

    See the case below. It is optimal to pick the middle of the 3..5 segment.

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

    check start and (end + 1) of every interval instead as the state changes at (end + 1) for an interval and not at end

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

Here's a derivation to the solution to E.

Let the initial string/number $$$a_na_{n-1}...a_1$$$.

A change of:-

$$$n$$$ digits occurs $$$a_n$$$ times.

$$$n-1$$$ digits occurs $$$9*a_n + a_{n-1}$$$ times.

$$$n-2$$$ digits occurs $$$9*(a_na_{n-1})+a_{n-2}$$$ times.

Thus, the final answer is:-

$$$= n*a_n+(n-1)*(9*a_n + a_{n-1})+(n-2)*(9*a_na_{n-1}+a_{n-2})+...$$$

$$$= n*a_n+(n-1)*(a_na_{n-1} - a_n)+(n-2)*(a_na_{n-1}a_{n-2}-a_na_{n-1})+...$$$

$$$= n*a_n-(n-1)*a_n+(n-1)*a_na_{n-1}-(n-2)*a_na_{n-1}+(n-2)*a_na_{n-1}a_{n-2}-...$$$

$$$= a_n+a_na_{n-1}+a_na_{n-1}a_{n-2}+...+a_na_{n-1}...a_1$$$

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

Thanks for very fast editorial

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

For F, what if the range of intervals was [1, 1e9]. how can we solve this question then?

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

    we could use co-ordinate compression, the number of unique co-ordinates wont exceed 2n

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

In problem G,my code got a "Wrong Answer" on test 2. Can anyone give me a hack? Many thanks.

https://mirror.codeforces.com/contest/1932/submission/247682595

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

    I had the same issue but then I added 1 to the new step count since its given that moving to another platform counts as a step.

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

      I have understood it.Thank you.

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

Very good contest, I hope CodeForces can provide us with more and better games!

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

I like how they put a "2012" reference in the last test case of problem B.

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

Here's my solution using Segment Tree for Problem F. https://mirror.codeforces.com/contest/1932/submission/247752578

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

Alternative (linear) solution for F:

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

Hi,

Can anyone please help me with debugging this submission for Problem G. https://mirror.codeforces.com/contest/1932/submission/247832499, i am WA at testcase 30. For the same logic but small change in variable assumption it is getting accepted https://mirror.codeforces.com/contest/1932/submission/247832770.

The difference is submission 247832499 has dp[i] = steps at which value of connected platforms will become equal i.e. l+s*dp[i] will match with previous platform where dp[i] will be minimum.

While submission 247832770 has dp[i] = 1 + steps at which value of connected platforms become equal i.e. l+s*(dp[i]-1) will match with previous platform where dp[i] will be minimum. Both codes are mostly same just dp[i] has shifted with value 1.

Sorry for bad formatting of the comment!!

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

Correction in third last line, in editorial of G..

k′=b′−1a′modH --> k′=b′−1a′modH′

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

Can someone help me with C? My code's working, but I keep getting time limit error. The code is written in Python. My submission is: 248030291

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

Can anyone tell me what category of problems does E lie in? And where can I find similar problems?

»
13 days ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

254672207 Could anyone let me know why i TLE-ed? O(n) solution with similar idea as the editorial, just reversed

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Even though Python can handle large integers (note that every $$$a_i$$$ can be as large as $$$10^4$$$), operations on them are slow. When following the solution provided by the editorial, i.e. handling commands in reverse order, then you can keep applying mod m which is much faster (as the product stays under $$$m$$$).

»
17 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem G, why do we take x modulo (H / dd) ?