В задаче А n/2 и n/3 надо умножать на 2 дополнительно чтобы считать реверснутые пары

I have another solution for D.

We will try to count the number of people for whom we can guarantee that they won't win. Let's call it $$$ans$$$.

Then the answer will be $$$2^n - ans$$$

Let's look at stupid solution and try to optimize it:

int solve(int n, int k) { //returns 'ans'
    if (n < k || n < 0) {
        return 0;
    }
    if (k == 0) {
        return power(2, n); //let's say if k == 0, then we can guarantee than nobody wins.
    } else {
        //we choose one of our children to be the winner (left or right), let it be left
        int ans = solve(n - 1, k); //left child
        ans += solve(n - 1, k - 1); //right child
        return ans;
    }
}

Pretty familiar, right?)

Let's iterate over values of $$$n$$$, and try to find a number of times, when $$$k$$$ will be equal to zero. Let's call this new $$$n$$$ = $$$m$$$. Then we will end up with $$$k$$$ = 0 exactly $$${n - m - 1 \choose k}$$$ times! Why? At first I thought that it has to be $$${n - m \choose k + 1}$$$, but our last move is always fixed! We have to go to $$$solve(n - 1, k - 1)$$$, because we are finding the first time, when $$$k$$$ = 0. Logic here is the same as in Pascal's Triangle.

My solution: 170668170

Auto comment: topic has been translated by purplesyringa (original revision, translated revision, compare)

IMPORTANT ISSUE(S)

• My solution for C is literal garbage and shouldn't have worked but it did, please, anyone uphack me if you could! 170616890
• ($$$\LaTeX$$$ for D is broken please fix) — upd: noticed fix. thanks!

In problem E, why the number of pairs (a,b) that are co-primes and sums to n is phi[n]? I only knew that phi[n] counts the number of integers between 1 and n which are coprime to n.

Why does my solution get memory exceeded for Problem B? https://codeforces.me/contest/1717/submission/170674893

Two corrections:

1. $$$A$$$'s solution: Answer should be $$$n+2\cdot (\lfloor \dfrac{n}{2} \rfloor + \lfloor \dfrac{n}{3} \rfloor)$$$ not $$$n+\lfloor \dfrac{n}{2} \rfloor + \lfloor \dfrac{n}{3} \rfloor$$$ to account for ordered pairs.
2. $$$C$$$'s hint $$$1$$$: It should be we've got a problem if $$$b_i>b_{i+1}+1$$$ not $$$b_i\geq b_{i+1}+1$$$ as $$$b_i=b_{i+1}+1$$$ is fine.

Auto comment: topic has been updated by purplesyringa (previous revision, new revision, compare).

I just published the tutorial for problem F. I had to write it myself instead of translating the problemsetter's editorial because apparently one the original editorialist's solution was hacked, he got sad and got drunk. I'm only half kidding. So I took the opportunity to provide more of a chain of thought rather than a concise tutorial. Hope you don't mind.

thank you for the round, next time keep your math problems to yourself.

good problems to attack my brain.

(though I've just had a vp

Problem A

• since

• given

• then

• since

gcd(a,b) will be in range [1, n], therefore if gcd(a,b)==1 then a=1 and b is multiple of 1 , if gcd(a,b)==2 then b should be multiple of 2 , for gcd(a,b)==3 (b=3*a) ...etc.

• thus

where m is an integer.

• hence

• b=a*m , where m={1,2,3}
• now when m=1 therefore b=a , since 1<=a<=n there will be n solutions
• • example : (1,1), (2,2) ,(3,3)....(n,n)
• for m=2 b=2*a there will be 2* [n/2] solutions
• • example : (1,2) , (2,1), (2,4), (4,2)....([n/2],2*[n/2]),(2*[n/2],[n/2])
• for m=3 b=3*a there will be 2* [n/3] solutions
• • example : (1,3),(3,1), (2,6),(6,2)....([n/3],3*[n/3]),(3*[n/3],[n/3])
• so by proof solution is: n+ 2*[n/3]+2*[n/2]

In D, the answer is:

which can be computed using FFT.

can someone please explain the solution to problem A in easy steps?

In problem E, the answer is:

Where $$$\mu(n)$$$ is mobius function. This can be computed in $$$O(N \log N)$$$

should problem A really be rated 800 ?

Alternate way of looking at D

Consider the path from each leaf to the root. The path will see "winning" and "losing" edges. Now associate an $$$n$$$-bit binary number to each leaf. This number will have a $$$1$$$ at position $$$i$$$ if the $$$i^{th}$$$ edge on the path was a winning edge and $$$0$$$ otherwise. Convince yourself that this number will be different for each leaf. Now for a leaf to win, all $$$0$$$s in its number must be changed to $$$1$$$. So Madoka will assign lower valued leaves, binary numbers with less number of $$$0$$$s. It is easy to see that the answer is the largest number having $$$k$$$ zeroes in its assigned number which is $$$\sum_{i = 0}^{min(n,k)} \binom{n}{i}$$$.

Can Anyone Explain Problem B. Madoka and Underground Competitions I am Struggling to implement it

Another way to solve E:

$$$\sum lcm(c,\gcd(a,b)) = \sum \frac{c \cdot \gcd(a,b)}{\gcd(a,b,c)} = \sum \frac{(n-a-b) \cdot \gcd(a,b)}{\gcd(a,b,n-a-b)} = \sum \frac{(n-a-b) \cdot \gcd(a,b)}{\gcd(a,b,n)}$$$

We can fix $$$\gcd(a,b) = d$$$, and calculate $$$cnt[d] ~- $$$ number of pairs $$$(a;b)$$$ that $$$\gcd(a,b)$$$ has $$$d$$$ as divisor.

$$$cnt[d] = \displaystyle \sum_{k=2}^{k \cdot d < n} { (k-1) * (n-a-b)} = \displaystyle \sum_{k=2}^{k \cdot d < n} { (k-1) * (n-k \cdot d)}$$$

Then we have to make inclusion/exclusion to make $$$cnt[d] ~- $$$ number of pairs $$$(a;b)$$$ that $$$\gcd(a,b) = d$$$.

So, the answer will be $$$\displaystyle \sum_{d=1}^{d \le n} { \frac {cnt[d] \cdot d} {\gcd(d,n)}} $$$.

Overall, $$$O(NlogN)$$$.

Почему ф(n-c/d) в Е? Думаю что а может быть больше чем n-c.

Problem D video editorial with code!

Problem D can be converted as follows:

Given a complete binary tree with $$$2^n$$$ different leaf nodes, and initially $$$2^n-1$$$ portals that connect each internal node with its left child node.

Madoka starts at the root node. From one internal node, she can move to its left child node instantly (in zero minutes) via portal. But to move to its right child node, she must walk, and it takes one minute.

Now she wants to know the number of different leaf nodes she can possibly reach within $$$k$$$ minutes.

For example, in a tree with $$$4$$$ leaf nodes and $$$3$$$ bridges, initially, Madoka can already reach one leaf node (the left most one) without taking time. If $$$k=1$$$, she can possibly reach $$$3$$$ different leaf nodes (all but the right most one). If $$$k \ge 2$$$, then all $$$4$$$ leaf nodes.

How does one stop over-complicating the solution, for C, we know, we got to know b[i]<=b[i+1]+1, how do we stop there, my mind will want the proof, or at least be pessimistic enough to not let me code the solution because I would assume it should be more complicated than that, any tips?

Lmao, I think problem F can be solved with some cheesy 2-SAT with random walks. Just keep randomly swapping edges and keep track of indegrees of each node. We know each node v that has s[v] == 1 has a certain required in degree and a required out degree.

If for all nodes, your current in degree is at the required in degree, you have a valid solution. If for all nodes, your current in degree is at the required out degree, you have a valid solution by flipping all the edges. This makes it a lot better than regular 2-SAT since you have 2 possible hits instead of just one, I think this is why you can go quite a bit under the O(n^2) requirement for regular 2-SAT.

I was able to get an AC while upsolving while just using 10^7 iterations, (I expected I'd need more). My solution is literally just 100 lines and I was able to code it tipsy.

Useful Link about 2-SAT: https://www.cl.cam.ac.uk/teaching/1920/Probablty/materials/Lecture7.pdf

I've got a good solution for D.

https://postimg.cc/94p4yLvq

In the image above: Basically, I'm trying to find out for each position, how many changes it would take to make that position holder win (when every time Madoka choose left one to win.) So the last line shows, how many changes we will have to make to make that node holder win. (0,1,1,2,...)

We can observe now, suppose we have found out for first 2^i positions. So what will the changes needed for the next 2^i positions?
first 2^i: 1,2,3,4,..k...2^i; second 2^i : 1,2,3,4...k...2^i;

Second k would need changes=changes first k needs+1; (It is easy to see that)

Now we can observe a pattern here. Pascal Triangle Pattern; if n=1 (N=2^1): 0 needed by 1, 1 needed by 1; if n=2 (N=2^2) : 0 needed by 1, 1 needed by 2, 2 needed by 1; ....so on so it would look like: 1 1 1 1 2 1 1 3 3 1 ...

so the final thing we wanna do is just find nth row of pascal triangle and do the prefix sum till min(k,n); and this would be our answer. Coz we are just trying to count how many positions can sponsor make win. So say they can make any position amongst the k positions, then answer would be k. coz Madoka would put the first k smallest there.

Excuse for the poor explanation.

I suck at these kind of problem C. Also, how to get familiar with these type of induction proofs?

Is the complexity analysis in F correct? I know Dinic's complexity reduces to $$$E\sqrt{V}$$$ on special type of unit graph, but this graph is weighted. Intuitively it feels that the algorithm will be fairly fast, but is there a rigorous proof of complexity in this case?

Can someone please explain problem C's solution in some simple language?

can anyone provide the solution explanation of problem B ?

It would be helpful if the first few test cases always contained edgecases/ tricky ones. That way we can upsolve a problem without looking at tutorial or other's solution. Consider this submission. I have no idea what went wrong. I even can't debug it because I don't know the case.