How to solve C, I?

# | User | Rating |
---|---|---|

1 | Benq | 3783 |

2 | jiangly | 3666 |

3 | tourist | 3611 |

4 | Um_nik | 3536 |

5 | inaFSTream | 3477 |

6 | fantasy | 3468 |

7 | maroonrk | 3464 |

8 | QAQAutoMaton | 3428 |

9 | ecnerwala | 3427 |

10 | Ormlis | 3396 |

# | User | Contrib. |
---|---|---|

1 | Um_nik | 185 |

2 | adamant | 177 |

2 | awoo | 177 |

4 | nor | 169 |

5 | maroonrk | 165 |

6 | -is-this-fft- | 164 |

7 | antontrygubO_o | 155 |

8 | ko_osaga | 151 |

8 | dario2994 | 151 |

10 | SecondThread | 149 |

How to solve C, I?

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/30/2023 04:34:54 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

How to solve L?

Instead of taking sum of 1 to 2. take sum for 1 to 2,3,4..,n . And then do ans/(n-1) at the end.

Now since graph is connected assume you first build the bfs tree and then add extra edges. To do that do dp with states as number of vertices left and number of vertices in current level.

I didnt think about "/(n-1)" part and made same solution without division, and wondered "why is MOD a prime number"

Can you provide a bit more details? I see just an obvious way to do it in

O(n^{4}).Try build bfs tree from the farest blocks to the nearest.

Nice idea, thank you! Now I understand the whole solution :)

Samples to problem K are very nice!

I solved I with following idea:

Consider only central part of backet with width

r: where centers of balls can be. Cut it byrfrom down and up. Now we have a boxh- 2rbyr, and the game is the following:The first player chooses any point on bottom of the box (representing Center of first ball he chooses), after that player one by one choose points inside the box which lie higher than previous chosen point and which are at diatance exactly 2

rfrom previous chosen point. One who can't choose a point inside a box loosesNow just simulate winning losing positions from the top to the bottom of the box. You will see they are periodic with . It will be easy to see than that if integer part of is even than first player wins, otherwise second player wins

How to solve A?

First, the vertices

uandvare connected in the complete graph iff there is a path between them in the starting graph which contains only vertices with indices strictly less thanmin(u,v) (anduandvtheirselves as its endpoints, of course).Second, let's find for each vertex

iall possible pairs of vertices for which there is a path described above whereiis the minimal vertex. It turns out that these endpoints are exactlyiand every vertex with index >iwhich is connected to any vertexvsuch thatvis in the same connected component asiif we consider only vertices from 1 toi(that is, there must be a path betweenvandiover vertices ≤i).So if we denote such set for

ibyS_{i}then it means that all vertices fromS_{i}must have different colors, and that means that the answer is (because knowing this we can now paint vertices fromnto 1 and each restriction gives us the corresponding number of ways to color each vertex). We can find out all these numbers building some DSU and adding all vertices from 1 tonthere.I know this may be difficult to read, but I tried to write a brief scetch here, not a formal proof.

What a beautiful solution, thank you very much for explanation!

How to solve G?

C: first, I've implemented a simple solution that can only does bets of form for a fixed value of

n, and made it print the optimal first bet for each starting amount of form . When I putnequal to a power of two, a pattern emerged. Here's an example forn= 16:In other words, the optimal move for where i is odd is equal to .

It turned out that the optimal first move in this case does not depend on the value of

p, and that the optimal first move is also the optimal move on subsequent steps, as no matter if we win or lose we get to a state which divides by a higher power of two and thus the next bet will be bigger as required by the problem.Note that I don't have a proof, it's just what emerged from the above experiment.

In order to determine the probability of winning for a starting state that is not of the form we will use the fact that the probability of winning is a continuous function. So we will represent the starting amount

xis an infinite binary fractionx= 0.011100011010..., compute the probability of winning for each prefix of this fraction, and find the limit as the prefix goes to infinity.We can compute the probability of winning for each prefix using the above observation and a relatively simple DP: if the prefix of length

kis equal to , then we'll compute the probabilityu_{k}of winning if the starting amount is and the probabilityv_{k}of winning if the starting amount is .The DP relation becomes: if

p_{k}is even (in other words, thek-th binary digit after the point is zero), thenu_{k}=u_{k - 1}, andv_{k}=p*v_{k - 1}+ (1 -p) *u_{k - 1}(since if we have , out first bet will be ). Similarly, ifp_{k}is odd, thenv_{k}=v_{k - 1}, andu_{k}=p*v_{k - 1}+ (1 -p) *u_{k - 1}.Now we can quickly determine the probability of winning for any prefix of our infinite binary fraction. In order to find their limit we have to remember that the fraction is periodic, find the transformation that a whole period applies to

u_{k}andv_{k}which ends up being something of formu_{k + m}= α *u_{i}+ (1 - α) *v_{k},v_{k + m}= β *u_{i}+ (1 - β) *v_{k}, which means we're constantly chopping our segment by 1 - α on the left and by β on the right, so the limit divides our segment as 1 - α to β, in other words it is , wheretis the length of the preperiod.I won't be entirely surprised if this is equivalent to something much more straightforward :)

Rick Astley — Never Gonna Give You Up.

The formal proof section of C is brutal. You've been warned. Petr s comment provides a more understandable albeit unproven method to solve the problem. The Handwaiving section describes some intuition behind the pattern. Also I'm a bit curious how many teams solved C by ignoring the nondecreasing part because they didn't like it and making the maximum possible bets because it seems logical to try end the game as fast as possible (and it is indeed correct if the nondecreasing restriction is dropped).

Bonuses: In some problems time limits were set to allow some solutions with unoptimal complexity to pass. It was done so for a reason because tighter TLs would lower the quality of those problems. The list of problems with their target complexities:

A: O(n a(n) + m), where a is the inverse Ackermann function. Basically the complexity should be dominated by a single pass over all edges with DSU.

B: O(n log n)

J: O(2^n m)

Finally I would like to apologize for unnecessarily tight time limit in L. Enforcing constant optimizations was not intended at all. Our two solutions worked for 0.2s and 0.5s and we didn't really find a way to make an even slower solution and thought that it should be ok.

WoW

My bad, analysis already posted.

How can I see problems and editorials?

https://drive.google.com/file/d/1aV_UGxlTh00PsiqUnKN_mOGoL26KrhuO/view?usp=sharing

Thank you, but haveyou got problems too?

Actually editorial link is posted above by VooV. I don't think problems are visible publicly.

I have seeing these discussions of GPs for quite some time now, and I also want to participate. But idk any way to register on the cryptic site, or this one. This is highly off-topic for this post, but any help is appreciated. :)

I was wondering also

How to solve G?

this is old thread. see this one: https://codeforces.com/blog/entry/105142

No, he knew what he was doing :)

ahhahahhah

lol