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

Pathetic problem statement(s).

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;
}

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?

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?

I still dont know what does 1929C - Sasha and the Casino mean.I was stuck in it.

Simple Round, AK in 1:07

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

E was stunning

An error. The spoiler name of Problem F is wrong. It should be "solution" instead of "soloution".

@FairyWinx Please fix this.

C is crazy

The contest was so cool and awesome!

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 still cannot get the idea of problem C, can someone please explain it for me in detail? I don't understand the part that "we bet 1 at first, then we bet the minimum number such that the win covers our loss". Or if you have a more understandable solution, please tell me (it's ok if it consume more time to execute). Thanks a lot.

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 :( .

in problem B , the second testcase while we need 3 diagonals why dont we colour the corner cell? It will take 3 diagonals.

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

Please do ignore this comment. I think I have figured out why this happens.

Can someone please tell me why my code for B worked after i used

within my code instead of just printing the output like

for(int i=0;i<t;i++){
    long long  n,m;
    cin>>n>>m;
    if(m<=n*2){
        cout<<ceil(static_cast<double>(m)/2)<<endl;
    }
    else if((m>2*n && m<=4*n-4)){
        cout<<ceil(static_cast<double>(m)/2)<<endl;
    }
    else if(m==4*n-3){
        cout<<(2*n)-1<<endl;
    }
    else if(m==4*n-2){
        cout<<(2*n)<<endl;
    }
}

It failed on testcase 3 which considered the case for a large input like 99999991 399999863 etc...

Sorry if there are any errors in my style of asking for help. This is probably my first comment and I am open to guidance.

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

deleted

Haha wow...I thought problem B was way harder than any other problem B I've seen. Then again, I have almost zero experience doing these kinds of geometry problems or making observations about them. It was really instructive for me and I thought the solution was very clever. Thanks for this problem.

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

In test case: 25 69 231

In the worst case, I would lose 69 times, but on 70th time if I bet 162 (cuz 231 — 69) then i would get 162*25 back, so total money in my pocket would be 3819, which is clearly more than 231, so why is the answer a NO?

I think it's cringe that $$$x \le 100$$$ in C. I don't know how anyone could have allowed the task with 64bit overflow on round.

.

//This code also gives accepted result-
void solve()
{
    int n, k;
    cin >> n >> k;
    ll diagonals = 4 * n - 2;
    if (k == diagonals)
        cout << (int)(n * 2) << endl;
    else
        cout << int(ceil((double)k / 2.0)) << endl;
}

Why in problem C, Test case 3 3 6 is a NO? Let's say I lose 3 times first, each time I bet 1 coin and lose, then I am left with 3 coins. Now I bet all 3 coins and get 3*3=9 coins back, which is more than initial coins. Someone please explain!

Is problem c inspired from here ?