Vladosiya's blog

By Vladosiya, history, 8 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

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

Tutorial after 3 days. Why?

»
8 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.!!

»
8 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?

  • »
    »
    8 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
    
  • »
    »
    8 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

»
8 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$$$

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

Thanks for very fast editorial

»
8 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?

  • »
    »
    8 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

»
8 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://codeforces.net/contest/1932/submission/247682595

  • »
    »
    8 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.

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

      I have understood it.Thank you.

»
8 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!

»
8 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.

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

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

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

Alternative (linear) solution for F:

Spoiler
»
8 months 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://codeforces.net/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://codeforces.net/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!!

»
8 months 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′

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

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

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

.

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

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

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

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

    Using 'auto [dd,x,y] = eucl(b,H)', we got one possible solution to the equation — 'xb+yH=dd' (here (dd is the gcd). Now, we multiply 'a/dd' to the above equation to get — '(x*a/dd)*b + (y*a/dd)*H = a'. Now we have one solution {x0,y0} — {(x*a/dd),(y*a/dd)} to the equation but we want the one having smallest positive x0 value. general solution for the above equation would be — {x,y} = {x0 + k*(H/dd) , y0 — k*(b/dd) }. so the samlest possible 'x' would be 'x%(H/dd)' . check out this for more clarification — https://cp-algorithms.com/algebra/linear-diophantine-equation.html

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

For B

I tried binary search to find the smallest number greater than previous year and divisible by current ai, but it gave wa on test 3. Can someone help me find the error?

Binary search submission for B