Блог пользователя Vladosiya

Автор Vladosiya, история, 8 месяцев назад, По-русски

1932A - Шипы и монеты

Идея: denk

Разбор
Решение

1932B - Календарь Чая

Идея: Vladosiya

Разбор
Решение

1932C - LR-остатки

Идея: MikeMirzayanov

Разбор
Решение

1932D - Карточная игра

Идея: goncharovmike

Разбор
Решение

1932E - Финальный отсчёт

Идея: step_by_step

Разбор
Решение

1932F - Кормление кошек

Идея: denk

Разбор
Решение

1932G - Перемещающиеся платформы

Идея: denk

Разбор
Решение
Разбор задач Codeforces Round 927 (Div. 3)
  • Проголосовать: нравится
  • +33
  • Проголосовать: не нравится

»
8 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Tutorial after 3 days. Why?

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяцев назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

Thanks for very fast editorial

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

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

»
8 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
8 месяцев назад, # |
Rev. 3   Проголосовать: нравится +4 Проголосовать: не нравится

Alternative (linear) solution for F:

Spoiler
»
8 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

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

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Question regarding Problem G.

The original equation is like this,

$$$ xb + yH = a $$$

By using extended Eucledian algorithm, we can find a particular solution $$$(x_o, y_o)$$$,

$$$ x_o b + y_o H = GCD(b, H) $$$

Multiply $$$\frac{a}{GCD(b, H)}$$$ on both sides, so that we can get the original equation,

$$$ x_o \frac{a}{GCD(b, H)} b + y_o \frac{a}{GCD(b, H)} H = a $$$

However this is just a particular solution, the general solution should be like this,

$$$ (x_o \frac{a}{GCD(b, H)} + t H) b + (y_o \frac{a}{GCD(b, H)} - tb) H = a $$$

Now all we need to do is to find the smallest non-negative integer solution for this $$$(x_o \frac{a}{GCD(b, H)} + t H)$$$

However in the editorial code,

x *= a / dd
x %= H / dd

What is the reason of doing this and why is H/dd was used instead of H. Are there any mistake in my derivation?

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 месяцев назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

.

  • »
    »
    7 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    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

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

spent an hour thinking how can i store remainders,,, never thought of a reverse logic,

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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