FairyWinx's blog

By FairyWinx, history, 4 weeks ago, translation, In English

Problem A. Idea by Igorbunov

Hint 1
Solution

Problem B. Idea by FairyWinx

Hint 1
Hint 2
Hint 3
Hint 4
Solution

Problem C. Idea by FairyWinx

Hint 1
Hint 2
Hint 3
Solution

Problem D. Idea by FairyWinx

Hint 1
Hint 2
Solution

Problem E. Idea by FairyWinx

Hint 1
Hint 2
Hint 3
Solution

Problem F. Idea by TeaTime, tutorial by imachug

Editorialist's note: I didn't submit the solution myself, but I proved it theoretically, aggregated solutions of problemsetters as well as participants, so I'm fairly sure it's correct, but you might want to treat it with more suspicion.

Hint 1
Hint 2
Hint 3
Solution
 
 
 
 
  • Vote: I like it
  • +78
  • Vote: I do not like it

»
4 weeks ago, # |
Rev. 2   Vote: I like it +54 Vote: I do not like it

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:

stupid

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

»
4 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

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

»
4 weeks ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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!
»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +39 Vote: I do not like it

    If $$$a$$$ is relatively prime to $$$n$$$, $$$a$$$ must also be relatively prime to $$$n-a$$$.

    The proof is simple: assume $$$n-a$$$ is not relatively prime to $$$a$$$, then that implies some $$$d>1$$$ divides $$$n-a$$$ and $$$a$$$. However, this implies that $$$d$$$ also divides $$$n-a + a = n$$$, so $$$a$$$ is not relatively prime to $$$n$$$, a contradiction.

    Given this, the pairs are just $$$(a, n-a)$$$, where $$$a$$$ is relatively prime to $$$n$$$, so there are $$$\varphi(n)$$$ of them.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      an easier proof: $$$gcd(a,n)=gcd(a,n-a)$$$. simply think of how the euclidean algorithm works.

»
4 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You seem to never update any values in your matrix by using == instead of =.

»
4 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

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.
»
4 weeks ago, # |
  Vote: I like it -6 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +26 Vote: I do not like it

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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Excuse me, I have some confusion:

    How to avoid this situation:

    A flow go to the node $$$u_i$$$ where $$$s_{u_i} = 0$$$ , instead of going to the $$$v_i$$$ where $$$s_{v_i}=1$$$. However, $$$v_i$$$ needs this flow to make its value $$$b_{v_i}$$$ equal to $$$a_{v_i}$$$.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You're absolutely right, this was a bug. I saw some code related to that in people's solutions, but didn't realize that's what it was doing. Should be fixed now. Read starting from "What about vertices with $$$s_v = 0$$$?".

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    :/

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Imagine getting drunk, could not be me

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem C , how can i get the new problem ?

»
4 weeks ago, # |
  Vote: I like it -20 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

good problems to attack my brain.

(though I've just had a vp

»
4 weeks ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

Problem A

  • since
$$$ {lcm(a,b)}= {ab \over gcd(a,b)} $$$
  • given
$$$ {lcm(a,b) \over gcd(a,b)} <= 3 $$$
  • then
$$$ {{ab} \over (gcd(a,b))^2 } \le 3 $$$
  • since
$$$ 1<=a<=b<=n $$$

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
$$$ b= m a $$$

where m is an integer.

$$${ab \over {(gcd(a,b))^2}}= {{a*a*m \over (gcd(a,am))^2}}= {a*a*m \over a^2}= m$$$
  • hence
$$$m \le 3$$$
  • 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]
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Another answer for A is

    ans = (n/3)*5 + (n/2 - n/3)*3 + (n-n/2)

    derived from code below

    		int ans=0;
    		
    		for (int i = 1; i <= n; ++i)
    		{
    			ans+= min(3,(n/i))*2 - 1;
    		}
    
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -19 Vote: I do not like it

    Programmer aren't mathematicians, you don't need to prove the solution

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey, a specific doubt related to your proof :

    When you say that "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.", don't you mean if lcm(a,b)/gcd(a,b) == 2 then b should be 2a, AND NOT what you have currently mentioned?

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Nope, because in gcd(a,b) = x, both a is multiple of x and b is multiple of x

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In D, the answer is:

$$$ \begin{align} [x^k]\frac{(1+x)^n}{1-x} \end{align} $$$

which can be computed using FFT.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I realized that is is absolutely unnecessary to use FFT here after reading the editional. I tried to find the generating function for the answer but it turned out to be just the sum of binomial coefficients.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    For all k, $$$[x^k](1+x)^n$$$ is just $$$\binom{n}{k}$$$. Notice that $$$[x^k]F(x)/(1-x)$$$ is summing up the coefficients of $$$[x^j]F(x)$$$, where $$$j\le k$$$. So the answer is the sum of binomial coefficients.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Well, let $$$g = \gcd(a, b)$$$ and $$$a = ga_0$$$ and $$$b = gb_0$$$, where $$$\gcd(a_0, b_0) = 1$$$. So, here we have $$$\mathrm{lcm}(a, b) = \frac{ab}{\gcd(a, b)} = \frac{g^2a_0b_0}{g} = ga_0b_0$$$. Thus, $$$\frac{\mathrm{lcm}(a, b)}{\gcd(a, b)} = a_0b_0 \leq 3$$$. So, here we have $$$3$$$ cases:

    • $$$a_0b_0=3$$$, in this case we have $$$(a_0, b_0) = (1, 3), (3, 1)$$$, thus, we have $$$(a, b) = (3k, k), (k, 3k)$$$. Note that it is sufficient for $$$3k \leq n$$$, because this automatically gives $$$k \leq n$$$. Thus, here there are $$$2\lfloor \frac{n}{3} \rfloor$$$ solutions. (Because $$$(a, b)$$$ is not the same as $$$(b, a)$$$)
    • Similar logic to the above case. Answer is $$$2 \lfloor \frac{n}{2} \rfloor$$$ in this case.
    • Similar logic to the above case. Answer is $$$n$$$ in this case.

    Adding all of them up, we have the answer as $$$2\lfloor \frac{n}{3} \rfloor + 2 \lfloor \frac{n}{2} \rfloor + n$$$.

»
4 weeks ago, # |
Rev. 5   Vote: I like it +62 Vote: I do not like it

In problem E, the answer is:

$$$ \begin{align} ans &= \sum_{k=1}^{n} \sum_{a=1}^{\lfloor \frac{n}{k} \rfloor} \sum_{b=1}^{\lfloor \frac{n}{k}\rfloor} lcm(n-ak-bk,k) [gcd(a,b)=1] [ak+bk \le n] \\ &= \sum_{k=1}^{n} \sum_{a=1}^{\lfloor \frac{n}{k} \rfloor} \sum_{b=1}^{\lfloor \frac{n}{k} \rfloor} \frac{k(n-ak-bk)}{gcd(k,n)} [gcd(a,b)=1] [ak+bk \le n] \\ &= \sum_{k=1}^{n} \frac{k}{gcd(k,n)} \sum_{a=1}^{\lfloor \frac{n}{k} \rfloor} \sum_{b=1}^{\lfloor \frac{n}{k} \rfloor} (n - ak - bk)[ak+bk \le n] \sum_{d | gcd(a, b)} \mu(d) \\ &= \sum_{k=1}^{n} \sum_{d=1}^{\lfloor \frac{n}{k} \rfloor} \frac{k}{gcd(k,n)} \mu(d) \sum_{a=1}^{\lfloor \frac{n}{kd} \rfloor} \sum_{b=1}^{\lfloor \frac{n}{kd} \rfloor - a} n - akd - bkd \\ &= \sum_{k=1}^{n} \sum_{d=1}^{\lfloor{\frac{n}{k}}\rfloor}\frac{k}{gcd(k,n)}\mu(d)(\frac{n \lfloor \frac{n}{kd}\rfloor (\lfloor \frac{n}{kd} \rfloor - 1)}{2}+\frac{k d \lfloor \frac{n}{kd} \rfloor (1 - {\lfloor \frac{n}{kd} \rfloor}^{2})}{3}) \\ &= \sum_{k=1}^{n} \sum_{d=1}^{\lfloor{\frac{n}{k}}\rfloor}\frac{k}{gcd(k,n)}\mu(d)(\frac{\lfloor \frac{n}{kd} \rfloor (1 - \lfloor \frac{n}{kd} \rfloor) (2kd\lfloor \frac{n}{kd}\rfloor + 2kd - 3n)}{6}) \end{align} $$$

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

»
4 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

should problem A really be rated 800 ?

»
4 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

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}$$$.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't think this might be very helpful, but if you know a little bit of recursion, you can take a look at my submission. (Although there are way easier implementations. For eg. submission)

»
4 weeks ago, # |
  Vote: I like it +32 Vote: I do not like 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)$$$.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D video editorial with code!

»
4 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Sorry for posting such an unhelpful and immature comment. Your down votes made me realize that. I shall be careful next time.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      As for me, personally I think your comment is helpful. I've been troubled by understanding the problem for a long time. Now I have understood it! Thank you! :)

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Please Explain B

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Its good if you are not stopping there because you should not. Just one more observation is required that you should look at minimum number in array a.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      my question was not specific to this problem, but i used it as an example, i hope that helped you understand what i was trying to convey better

»
4 weeks ago, # |
Rev. 2   Vote: I like it +14 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is not the classical 2-SAT algorithm though. The "default" solution to 2-SAT is computing SCC on the graph of implications. What you're doing is much more generic than 2-SAT, it's kind of gradient descent.

    Did anyone try some sort of simulated annealing?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    I hacked your solution and got "unexpected verdict", which usually means a solution that the author marked as correct failed on the hack. Anyway, I tested your code locally and it failed on the test case (basically, just make a directed path of length $$$10^4$$$).

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh oof, I guess my AC was just a bit of luck as well as some weak test cases (they probably only put 1 test case with m = 10000)

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        No, there were some test cases with large $$$m$$$. Your method fails when there's a long path of edges that need to be oriented correctly, and maybe the author's test cases were randomly generated in a way that doesn't create long paths.

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    hey, your explanation is pretty good, I got to the same kind of reasoning during the contest. Could you (or anyone!) elaborate on the idea of calculating the n-th row of Pascal's triangle fast? Based on your solution I can see that it is based on Fermat's theorem but I cannot understand it fully.

    Any link to the place where this is explained would be helpful!

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      hey, nth row is basically the nCr constants of binomial expansion of (1+1)^n.

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

i'm someone who never understand what the description of solution want to convey?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Damn. I heard the complexity from a friend who heard it from a friend who apparently didn't read the original Karzanov's paper but just read someone's analysis on the internet and misinterpreted it.

    Shit happens. Anyway.

    Firstly, the complexity is reachable, albeit on a different type of networks. You can read Alexander V. Karzanov, On finding a maximum flow in a network with special structure and some applications to find out more.

    Secondly, a slightly worse but still subquadratic complexity holds. I updated the tutorial with the proof.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think you should either add the Russian version of the analysis for problem F, or say that there is an English version, because in Russian it says that there's no editorial yet and someone might think that there's no editorial at all.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    As far as I have understood... First of all its obv that for all i, ai <= bi. Then it is necessary that for each element it should be either ai = bi or bi <= bi+1 + 1. Now given that these conditions are satisfied, we can always make both arrays equal in the following way. If at each step we pick the min element such that ai != bi, we are sure that bi <= bi+1 + 1. So lets suppose ai <= ai+1 then we can simply increment ai to ai + 1. The other case, ai > ai+1, is never possible because if ai+1 != bi+1 then we would have chosen ai+1 as the smallest element else if ai+1 = bi+1, then bi > ai > bi+1... which means bi > bi+1 + 1 which contradicts our initial condition. Hence, we will always be able to increment the min element until it reaches its target for each element.

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      Thanks man! Great explaination . I love the proof

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can any one provide a proof why dfs works in problem B (solution: 170656544)

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone provide the solution explanation of problem B ?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Let us try to construct the matrix starting from $$$(r,c)$$$. Assume the matrix is as follows when there is one X on $$$(r,c)$$$. (This is the fifth example btw)

    ......
    ......
    ......
    .X....
    ......
    ......
    

    Note that this mark on $$$(r,c)$$$ cannot affect other rows or columns, we fill a full diagonal with marks. After this step the matrix is as follows.

    ....X.
    ...X..
    ..X...
    .X....
    X.....
    ......
    

    Now, let's find some other cells we need to fill. After we fill these cells which have $$$k$$$ horizontal distance relative to the line, we can see that it has $$$k$$$ vertical distance as well.

    ....X.
    X--X..
    |.X|..
    |X.|..
    X--X..
    ......
    

    And, of course, these marks did not affect other rows or columns, so we need to construct diagonals based on these cells as well.

    .X..X.
    X..X..
    ..X..X
    .X..X.
    X..X..
    ..X...
    

    And after that we need to construct marks based on the new diagonals, and the diagonals based on the marks, and so on.This goes on until the matrix fits the criteria. By inductive proof (same logic as we did above), we can prove that the diagonals we just marked are the one $$$(r,c)$$$ is on, and the ones whose horizontal/vertical distance to the original diagonal is a multiple of $$$k$$$. This gives us a formula, $$$r+c \equiv x+y \,(mod\, k)$$$ (think of the grid as a graph on a plane, really. you'll get my point). Therefore, the proof is finished and you can construct a relatively simple code based on what we just proved.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I think for problem F, it is rather easier to solve this way: For each edge $$$(u,v)$$$, do the followings:
1. If $$$s[u]=1$$$ and $$$s[v]=1$$$, then add a directed edge between $$$(u,v)$$$ with capacity $$$1$$$.
2. If $$$s[u]=1$$$ and $$$s[v]=0$$$, then add a directed edge between $$$(u,n)$$$ with capacity $$$1$$$.
3. If $$$s[u]=0$$$ and $$$s[v]=1$$$, then add a directed edge between $$$(n,v)$$$ with capacity $$$1$$$.
4. If $$$s[u]=0$$$ and $$$s[v]=0$$$, then do nothing.
And after that, for each vertex $$$u$$$, we do the followings:
1. If $$$s[u]=1$$$, set $$$a[u]:=\frac{(d_{-}(u)-d_{+}(u) - a[u])}{2}$$$
2. If $$$s[u]=0$$$, set $$$a[u]:= 0$$$
Where $$$d_{+}(u)$$$ is the number of outgoing edges from $$$u$$$, and $$$d_{-}(u)$$$ is the number of incoming edges into $$$u$$$. Lastly, set $$$a[n]:= \frac{(d_{-}(n) - d_{+}(n) + \sum_{u \ne n}{a[u]})}{2}$$$. If we think $$$a[u]$$$ is a demand associated with each vertex, then the problem can be reduced to find the feasible flow in circulation network.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.