Problem C video solution with live coding: https://youtu.be/XRjHt1rnzqs

Is O(nklog²n) solution gives TLE for E??

Learn English

I have to admit C was really intuitive and fun though it could just be me but ABC were easier than usual.

Thanks for this round! :)

for Problem C, Are these 2 conditions correct (t_i is amount bet in ith round):

1. (k — 1) * t_i > t_1 + ... + t_i-1 (if at any point we need to restart it covers for previous losses) for all i in 1 <= i <= x

2. k * (a — (t_1 + ... + t_x)) > a

We initially start with t_1 = 1

I am getting signed integer overlfow on my submission (not sure why) :

#include "bits/stdc++.h"

#define  int            long long

using namespace std;

signed main()
{
    fast_io
    test {
        int k, x, a, t = 1, sm = 1;
        cin >> k >> x >> a;
        for (int i = 2; i <= x; ++i) {
            t = sm / (k - 1ll) + 1ll;
            sm += t;
        }
        if (k * (a - sm) > a) cout << "Yes\n";
        else cout << "No\n";
    }
    return 0;
}

@FairyWinx. please attache codes with comments

You forgot to translate the English title

Can someone tell me what I could do to make this submission pass (it works in C++ (https://mirror.codeforces.com/contest/1929/submission/246588961) but not in Python (https://mirror.codeforces.com/contest/1929/submission/246588699) nor does it with PyPy). I know C++ is better on codeforces but I'm just curious if there would be a way to make it work with Python.

Problems E and F are very good!

Can someone explain what the problem D was ?

Wow now I want someone to explain the statement of C and it's editorial XD

E and F were both Div2E-level according to the AC count and my impression. Don't be afraid to assign the same score to multiple problems next time. It makes the competition more strategic and fun (players can focus on their favorite topics).

I am really confused in problem C. Why can't we bet 1 coin every single time?? if we win, we keep getting k+1 more coins and in the worst case, even if we lose x number of times at any point of time, we only lose x coins. And once we lose x number of times, we can bet an amount such that we cover all the previous losses. If we use this strategy, we will always get more coins specially for the second last input given in the question (25, 69, 231). But the output for this input is NO. Where am i going wrong can anyone explain?

How do you prove the conclusion for E?

Can you prove the claim you stated in E?

Can someone please give me a clear solution of problem C ... like I could not understand why at every step its mandatory to chose such a number which would nullify the previous losses ..

Upd: understood now

I am confused on Problem E. Could anyone prove that "we will have total $$$O(k)$$$ different sets?". When I was thinking it, I thought the total of sets is $$$O(2^k)$$$. Now I think it is lower than $$$O(2^k)$$$, but I can't understand why it will reduce to $$$O(k)$$$. Thanks.

In problem E, "precomputing the set of pairs removed by each edge for each edge" could be done in $$$O(n + k)$$$.

A path covers an edge if and only if the two ends of the path ($$$a_i, b_i$$$) is on different sides of this edge, where each side is a subtree. Let's focus on one of the two sides. Each time a traversal of a subtree is finished, find that set of this subtree. The set belongs to exactly an edge, except the whole tree.

Details are in submission 246548785.

fast Editorial

I'm sorry that I can't understand why in D, we need to sum up dp[] and that is the ans."as we can select such a set of vertices exactly from one subtree from the dynamic programming states" is hard for me to understand, can anyone tell me why?

Can D problem be solved by using combinatorics, inclusion-exclusion principle and rerooting.

Like by at each root, calculating how much be the total number of good sets, where this root is always a part. Like, we could easy calculate this number using combinatorics and the number of leafs in the subtree of direct children of root.

But there would be extra contribution by each root, like 3-member set would be added thrice, each when considering each part of this set as root.

Could someone explain if they did it this way?

Simple Round, AK in 1:07

I solved the problem $$$E$$$ with $$$FWT,O(nk+2^kk)$$$,amazing! here

E was stunning

C is crazy

Maybe I misunderstand the problem D. Can someone correct for me, I think the problem said: "Find all set of vertices such that no 3 vertices are connected", is it right?

Upd: Nevermind, i really misunderstand :((

I think you should use YocyCraft's explanation for problem C.

Thanks

problem c was literally great , don't know why I couldn't solved it during the contest. Tried just now and actually solved it , don't know why this is happening since last few contests, my rank is going down and down :( .

Почему в случае "3 3 6" ответ "Нет"? Может кто-то найдет ошибку в моей логике, но смотрите. Саша знает, что он может проиграть не более X раз подряд, стало быть он точно знает, что если он уже проиграл X раз подряд, то следующая ставка будет ТОЧНО выигрышной. Тогда давайте ставить 1 монетку всегда, кроме того случая, когда игра ТОЧНО выигрышная, будем обозначать П — проигрыш, а В — выигрыш. Рассмотрим 2 случая, когда Саша проиграл X подряд и X+1 раз будет точно выигрышным, и случай когда ТОЧНО выигрышных ситуаций нет. Пусть у нас идет последовательность ПППВ, мы проиграли 3 подряд, значит следующая игра выигрышная, значит Саша может ставить на нее все деньги. Как говорилось ранее, на игры которые не точно выигрышные мы ставим 1 монетку, тогда за 3 проигрыша мы потеряли 3 монетки, 6-3 = 3, тогда мы ставим 3 и выигрываем 6, в сумме имеем 9, то есть, мы ушли в плюс. Теперь рассмотрим ситуацию, когда точно выигрышных игр нет, тогда мы будем ставить всегда 1 монетку. Несложно заметить, что худший случай — ППВППВ.... Тогда перед каждой победой мы проигрываем 2 монетки, 6 — 2 = 4, имея 4 монетки мы ставим одну и выигрываем 2, итого мы имеем опять 6 монеток. В условии сказано, что Саша должен иметь возможность бесконечно не уходить в минус "Другими словами, правда ли, что для любого целого числа n , Саша сможет делать ставки так, чтобы при любых их результатах, не противоречащих описанным выше правилам, в какой-то момент времени у него было хотя бы n монет." В чем я не прав?

About problem E:

Every edge can be included or excluded on any of the k paths. Therefore there are 2^k possible values S[i] can have. Could anyone explain to me, why the set S = {S[1], S[2], ..., S[n]} has at most k different elements?

Worst Problemset ever in C it read at least n and in answer the author has considered greater than n

For problem $$$E$$$, if $$$paths[i]$$$ is a bit-mask whose $$$j^{th}$$$ bit is set if the $$$i^{th}$$$ edge is within the $$$j^{th}$$$ path, the proof that the number of distinct values in $$$paths$$$ is $$$O(k)$$$ (Please let me know if you notice any incorrect ideas in the proof, or if you want any clarifications):

Claim1: We can can calculate $$$paths$$$ using a recursive DFS. For a node $$$node$$$ whose parent edge is $$$x$$$, given that we calculated $$$paths[y]$$$ for every child edge $$$y$$$ of $$$node$$$, $$$paths[x]=xor\_sum(paths[y]) \oplus xor\_sum(2^z)$$$ (where $$$z$$$ are the indices of paths which have $$$node$$$ as one of its endpoints (if any).

Proof of claim1:

1) Reason for $$$xor\_sum(2^z)$$$: For one of such paths $$$z$$$, if the $$$z^{th}$$$ bit is set in one of $$$paths[y]$$$, this means it is a path that started below $$$node$$$ and ends at $$$node$$$, otherwise, it is a path starting at $$$node$$$ and should move to above $$$node$$$ to reach the other endpoint.

2) For a path with index $$$j$$$, if the $$$j^{th}$$$ bit is set in at least one of $$$paths[y]$$$, we have the following cases:

i) It is set in one of the child edges only, this means it is a path whose one of its endpoints is under $$$node$$$, and the path should move to above $$$node$$$ to reach the other endpoint (or possibly $$$node$$$ itself is the other endpoint as shown in (1)).

ii) It is set in two of the child edges, this means $$$node$$$ is the LCA (Lowest Common Ancestor) of the endpoints of this path.

Based on the previous, a parent edge $$$x$$$ will possibly introduce a new value in $$$paths$$$ only if it has at least $$$2$$$ children edges with non-zero $$$paths$$$ values.

Claim2: The number of such edges $$$x$$$ that will possibly introduce a new value is $$$O(k)$$$.

Proof of claim2:

We can imagine each distinct value in $$$paths$$$ as a connected component. When the $$$j^{th}$$$ bit is set in $$$paths[i]$$$, this set bit could come from any of the $$$j^{th}$$$ path endpoints, so, assume each endpoint introduces a different connected component.

Recalling that $$$y$$$ are the children edges of $$$x$$$, when we xor $$$2$$$ values of $$$paths[y]$$$ as a step towards calculating $$$paths[x]$$$, it is like merging the corresponding $$$2$$$ imaginary connected components. The upper bound of the initial number of connected components is $$$2k$$$ ($$$1$$$ connected component for each path endpoint in isolation). Hence, the upper bound of the merge operations is $$$2k-1$$$, as count of connected components decreases by $$$1$$$ after each merge operation.

I believe the upper bound of non-zero distinct values in $$$paths$$$ is $$$3k-3$$$ (Except for $$$k=1$$$, where we will have 1 non-zero distinct value). An example that demonstrates this upper bound:

For $$$k=5$$$, where the paths are: [20, 13], [21, 11], [19, 9], [17, 7], and [15, 5], we will have $$$12$$$ distinct non-zero values in $$$paths$$$ ($$$3 \cdot 5 - 3$$$), which are (Values of $$$paths$$$ are written in sets for simplicity):

1. $$$paths$$$ [(18, 20)] = {[20, 13]}     ((18, 20) is the edge, [20, 13] is the path)
2. $$$paths$$$ [(18, 21)] = {[21, 11]}
3. $$$paths$$$ [(16, 19)] = {[19, 9]}
4. $$$paths$$$ [(14, 17)] = {[17, 7]}
5. $$$paths$$$ [(12, 15)] = {[15, 5]}
6. $$$paths$$$ [(16, 18)] = {[20, 13], [21, 11]}
7. $$$paths$$$ [(14, 16)] = {[20, 13], [21, 11], [19, 9]}
8. $$$paths$$$ [(12, 14)] = {[20, 13], [21, 11], [19, 9], [17, 7]}
9. $$$paths$$$ [(10, 12)] = {[20, 13], [21, 11], [19, 9], [17, 7], [15, 5]}
10. $$$paths$$$ [(8, 10)] = {[21, 11], [19, 9], [17, 7], [15, 5]}
11. $$$paths$$$ [(6, 8)] = {[19, 9], [17, 7], [15, 5]}
12. $$$paths$$$ [(4, 6)] = {[17, 7], [15, 5]}

Submission

What does compressed tree mean in E? Any link i can refer to?

Do we have to take the worst case scenario every time in C? Like let it be so that we lose consecutively then we get the win. If so, how is 2 3 15 a yes?

REGARDING C — (Sasha and the Casino) Can someone please explain how the answer to '2 3 15' is 'YES'? Can you provide me with a combination of bets (Y value and win/loss) that will result in a winning outcome?

Can we use Euler Tour + Greedy for E?

Problem D has a bijection with count of connected induced subgraphs of a tree. I've written about how to prove and construct such a bijection here

Can someone prove or disprove this greedy approach for Problem E:

Guessing it should take $$$O(nk)$$$ time for each iteration and we repeat it $$$k$$$ times at worst. Total complexity $$$O(nk^2)$$$ time