Блог пользователя majk

Автор majk, 5 лет назад, По-английски
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Разбор задач Codeforces Global Round 6
  • Проголосовать: нравится
  • +159
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Wow, fastest editorial out there!

»
5 лет назад, # |
  Проголосовать: нравится +97 Проголосовать: не нравится

Gap between E and F is HUUUUUGGGGGEEEEE :C

»
5 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

Fast Editorial and system testing :)

»
5 лет назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

epic F...

»
5 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

wow fastest guide ever i have seen

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For D, you have given solution for min dept, how to find number of depts?

I did a greedy solution 67115957, can anyone please tell me why i am getting TLE.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Yeeee. This is the fastest guide I've ever seen

»
5 лет назад, # |
  Проголосовать: нравится +81 Проголосовать: не нравится

For E , what ideally we should have done -" It is obvious that we cannot do better and this number is necessary. Let's prove that it is also sufficient. "

What most people did — " It is obvious that we cannot do better and this number is necessary. Let's submit."

»
5 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

How to solve D with rule 1 changed to d(a, b) and d(b, c) instead of d(a,b) and d(c, d)? If I understand that correctly, it means we cannot greedily match balances and we need to preserve (more or less) the original graph structure.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Yes, I also thought that it was important in the contest, but if you carefully read and understand all the limitations in the first operation, it will become clear that you can get any situation that is described in the solution.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      Yeah, I know, I managed to reread the problem statement after 1 hour and solved it, but I am wondering about a harder problem now :P

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

https://mirror.codeforces.com/contest/1266/submission/6708325 Please someone can find mistake in my first question solution..

»
5 лет назад, # |
Rev. 3   Проголосовать: нравится -27 Проголосовать: не нравится

Thanks for the quick editorial!!!

»
5 лет назад, # |
  Проголосовать: нравится +74 Проголосовать: не нравится

H is very cool, one of my favorite problems now. Thanks!

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hello majk !

I want to ask something about problem C. Since it is a constructive algorithm task ; could you please describe the thought process involved while arriving at the construction.

PS : I also solved the problem in the contest ; however it took me a lot more time to derive the construction.

Thanks in advance !

  • »
    »
    5 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

    Here is how I thought of it it, Since we have to produce minimum magnitude and all Gcds should be distinct, I thought the gcds should be of the form 1,2,3,4,5. I didn't know of this will work, but just a trail. I tried to produce gcd = 1. This can easily be done by writing 2,3. I also noticed that 1 cannot be written anywhere as it make gcds of column and row same. So in the first row I wrote 2,3,4,5,6,....,m + 1.after this I observed that I can make gcds of each column the topmost element if each column is a multiple of the topmost element. After this, I thought that if I multiply the first row by some number and write it in the second row, the gcds of the second row will be the number it was multiplied with as I can take the number common and the gcds of remaining elements is one. It's easy to see how this works after this.

    • »
      »
      »
      5 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks! I was just thinking like you, but missed to notice a silly mistake I was making in my logic, now I understand my mistake.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    I think my solution for C plainly describes the thought process involved. here

    I created two arrays(one for row and one for column) that contains the targeted minimum disjoint gcd values that can be achieved ie { 1,2...r...(r+c) }then I filled the matrix by multiplying each row array element with column array element. By analyzing output you can infer {1...r} values can be achieved by taking gcd of each row and remaining {r+1...c} can be achieved by taking gcd of each column.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It would be really helpful if someone could provide the thought process required for C,as it is a constructive algo?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Since we want to minimise GCD we may want to start with putting 1 but we can't do so because it will make the GCD of that particular row and column 1 which will not satisfy condition that GCD values must be distinct. Firstly, try a simpler case like when r = 1 and c > 1, we can have values like 2,3,4,...c-1. Similarly, for case when c = 1 and r > 1. Now, Let us consider case when r = 3 and c = 3. Then in first row we can have 4,5,6 which have GCD = 1. Now observe that for second row we can multiply the first row by 2, which gives for second row 8,10,12 which will have GCD as 2. Similarly, third row will be 12,15,18 having GCD as 3. And for the first column GCD will be 4, second column GCD will be 5 and for third column GCD will be 6. So set of distinct values of GCD = {1,2,3,4,5,6} and also we can say that r+c will always be the optimal value.

»
5 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

good contest !

Thanks majk !

»
5 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Why is it clear in problem D that we can't do better than sum of balances divided by 2?

»
5 лет назад, # |
  Проголосовать: нравится +75 Проголосовать: не нравится

I have a linear-time solution (67124772) to F.

The idea is to make extensive use of the trivial data structure that maintains a set of integers and supports the following operations:

  1. Add value $$$v$$$ to the set (in $$$\mathcal{O}(v)$$$ time)
  2. Decrement value $$$v$$$ that appears in the set (in $$$\mathcal{O}(1)$$$)
  3. Output the maximum value in the set (in $$$\mathcal{O}(1)$$$)

To do this, just store for every value how many times the value appears in the set, and maintain the maximum.

We'll loop from $$$k = 1$$$ upwards, and maintain $$$dp[i] = $$$ number of subtrees of $$$i$$$ with depth at least $$$k$$$ (including parent). Then at step $$$k$$$ we have $$$ans[2k] = \max(\max_{i} dp[i], \max_{a, b \text{ adjacent}} dp[a] + dp[b] - 2)$$$ and $$$ans[2k-1] = \max_{i} dp[i] + \text{at least one of the subtrees of i has depth exactly } k-1$$$.

To maintain $$$dp[i]$$$, note that when we increase $$$k$$$ and calculate the new value $$$dp'[i]$$$, we have $$$dp'[i] = \sum_{t \in conns[i]} \max(1, dp[t]) - 1$$$. Hence we can store a queue of nodes whose some neighbour had their $$$dp[i]$$$ decreased to one in the previous step. The nodes in the queue are exactly the nodes whose $$$dp[i]$$$ will decrease in this step (multiple times if they appear multiple times). Since initially $$$dp[i] = deg(i)$$$, and they can only decrease, and we do updates to them in $$$\mathcal{O}(1)$$$ time, this part takes linear time.

We'll use one copy of the data structure to maintain values of $$$dp[i]$$$. To maintain the values we need to calculate $$$ans[2k-1]$$$, we'll maintain the values $$$dp[i] + \mathbb{I}[dp[i] \text{ got decremented in the previous step}]$$$ in another copy of the data structure.

Lastly, to maintain the values to calculate $$$ans[2k]$$$, we'll maintain for every node a copy of the data structure storing the current values of $$$dp[i]$$$ for its children. Note that every $$$dp[i]$$$ appears in exactly one such data structure, so to initialise and maintain them we again do only linear work. We'll also have a data structure storing the "active" values $$$dp[i] + \max_{c \in childs[i]} dp[c] - 2$$$. Whenever $$$dp[i]$$$ decreases, we decrement its active value, its parents children data structure, and its parents active value if $$$dp[i]$$$ was the unique maximum in the data structure. All the operations we'll ever do again take in total time equal to the sum of degrees, which is linear.

  • »
    »
    5 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +20 Проголосовать: не нравится

    I have a similar solution to you, and the complexity is also linear: 67162965.

    We notice that the number of subtrees of $$$i$$$ with depth at least $$$k$$$ is always smaller than that of $$$k - 1$$$. So, instead of looping $$$k$$$ from $$$1$$$ upwards, we loop $$$k$$$ from $$$n$$$ downwards, which will make every variable in the computation non-decreasing, so we don't have to use any data structures; straight up updating every variable using the $$$max$$$ function is enough.

    Edit: Courtesy to GreymaneSilverfang for helping me with this discovery :D

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In D editorial can someone explain "We have just reduced the total debt by z, which is a contradiction."

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    We assume that the debt is already minimal, and there is a vertex triple such that ... We managed to reduce the debt, so it wasn't minimal. This means that for a minimal debt, there cannot be such triple.

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

[DELETED]

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

In question D
for input:
6 4
1 2 6
2 3 4
4 5 3
5 6 5
is this a correct solution?:
4
1 6 5
4 3 3
5 2 2
1 3 1

Edit: It is .. nevermind

»
5 лет назад, # |
  Проголосовать: нравится +39 Проголосовать: не нравится

In problem H:

These two conditions are in fact necessary and sufficient.

How to prove that these conditions are sufficient?

»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

https://mirror.codeforces.com/contest/1266/submission/67100495

Can someone tell why my solution is failing in D. Is there something to do with it out of bounds?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Thanks for the contest!

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In problem D
"It follows that any solution in which every vertex has either outgoing or incoming edges is constructible using finite number of applications of rules."
I couldn't understand why... How to prove it? Can someone explain?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    "It follows that any solution in which every vertex has either outgoing or incoming edges is constructible using finite number of applications of rules." Because if there is combination of vertices like a->b->c then this combination surely results in a decreased total debt i.e. why using any number of operations we can achieve the state of graph where every vertex has either incoming or outgoing edge.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thank you,but why "any solution is constructible"...?
      I understood there exists the graph which we can construct where every vertex has either outgoing or incoming edges,but I don't think it is clear that we can construct "any" graphs that satisfies the condition.
      (I'm sorry if I misunderstood the editorial)

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        For example, imagine that there is a answer a->b 10, c->d 10. In order to get another answer, we add two edges a->c 10 and c->a 10, then we could use the first rule to get another answer a->d 10, c->b 10

»
5 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

I'm really interested in yosupo's and eatmore's solutions to problem H.

It looks they are quite different from the intended solution.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    For each vertex, we assign a level as the shortest distance for the vertex N.

    Core part is making function succ(l, State={position, color, time}) -> new_State: this function simulate the state while a token reach one of the vertex whose level is l(we assume the first position of token is a vertex whose level is higher than l). We can memoize this function by (l, color of vertexes whose level is higher than l).

    How many states this function memoized? ... actually I don't have any proof(so, my solution is unproved, sorry). My intuition say that it is exponential, but quite small (even in the worst case).

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    My solution uses simulation with memoization.

    Suppose that we start in some state, and the token is in vertex $$$i$$$. If we know only the state of vertex $$$i_1=i$$$, we can simulate one step (or two, if the first step moves the token to the same vertex). Then, the token lands at vertex $$$i_2\ne i_1$$$. If we know the state of vertices $$$i_1$$$ and $$$i_2$$$, we can simulate more steps until the token lands at vertex $$$i_3\ne i_1,i_2$$$. This way, it is possible to construct the following lazy DP: the state is $$$(i,k,\textrm{state of }i_1\ldots i_k)$$$, and the value is $$$(i_{k+1},\textrm{new state of }i_1\ldots i_k,\textrm{number of steps})$$$.

    The simulation function (run in my solution) takes the following arguments: initial vertex, current state and a set of vertices. It runs the simulation until the current vertex is not in the set. There is also an option to limit the number of steps. It starts with $$$k=1$$$ and $$$i_1=i$$$ to compute $$$i_2$$$, $$$i_3$$$ and so on. To compute DP for some $$$k$$$, it runs the same procedure recursively with starting vertex $$$i_k$$$ and the set $$${i_1,\ldots,i_k}$$$. For $$$k=1$$$, a straightforward simulation is used (this requires at most two steps).

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Could anyone help me why the following solution is incorrect for C? I hope my logic was correct.

https://mirror.codeforces.com/contest/1266/submission/67161724

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Your logic is half correct,your solution does produce disjoint gcd arry or diverse matrix,but it is failing to produce the diverse matrix that minimises the magnitude For eg. dry run your program for 3 3,you will get it.

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

Two doubts for problem D editorial

  1. how did you conclude this " This means that we can just find balances, and greedily match vertices with positive balance to vertices with negative balance.The total debt is then Σd=∑v|bal(v)|2 , and it is clear that we cannot do better than that"

  2. how do we find the final debts i.e. the second half of the answers , the remaining edges.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    1. Since the bal of all the vertices can either be positive or negative (positive for incoming edge and negative for outgoing edge), and you have to match the positive vertices with negative vertices (as the person who is in debt has to pay it to someone and it doesn't matter who pays to whom, all that matters is what one person owes has to be fulfilled by 1 or more than 1 vertices), when you take the sum of all the absolute values of the balances, you are left with 2 times the total debt, because of the fact that you are taking the sum of absolute values. It won't be wrong to say that the total sum of all the balances, after matching all the positives with negative will be zero, because, in the end, all the people in debt have to repay it. Hence, the claim in the editorial is rightfully the minimum.
    2. You take each positive balance, take the absolute value of one negative vertex, take the minimum of the positive and abs(negative), add the index of negative, the index of positive and min value to your final result, and keep on greedily matching positive and negative vertices.
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Is it like to minimize the debt we have to pay all the loan back so that the overall debt decreases and that is why we are matching the positive ones with negative ones so as to make positive ones as small as possible. Do we have to think like this ??

»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

In E if we consider a = {1,1} and queries are — (1, 1, 2) and (2, 1, 1) then p will be {0,0} how is it possible to not create anything?

»
5 лет назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

In problem H,why are these two conditions sufficient?

  • »
    »
    4 года назад, # ^ |
    Rev. 5   Проголосовать: нравится +8 Проголосовать: не нравится

    For a valid state, we take the subgraph of all active arcs.

    It's easy to see that there exists exactly one vertex such that:

    • The active arc starting from it ends at v.

    • The path from 1 to the said vertex does not include v.

    Then the only possible predecessor of v is the said vertex.

    The rest is induction.

    upd:

    I seem to have missed the case when v=1...

    Forget what I've said before.

    take the directed multigraph, where each arc appears exactly the number of times it is traversed.

    Given the constraints of the matrix, it's easy to see that there exists an Euler path(if it's connected, hence the condition we're checking).

    Consider constructing an Euler path the following way:

    Start from 1;

    If the vertex we're at has been traversed odd number of times, take the blue arc; else take the red arc.

    It could be checked that this Euler path is the legitimate path.

    P.S.

    Since all other vertices must be traversed before v, it could be checked that they should all be able to go to v using only active arcs.

»
5 лет назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится
#include <bits/stdc++.h>
#define ll long long
#define ibs ios_base::sync_with_stdio(false)
#define cti cin.tie(0)
using namespace std;//coded by abhijay mitra
#define watch(x) cout << (#x) << " is " << (x) << endl
int main()
{
    ibs;cti;
    int t;cin>>t;
    while(t--){
        ll x; cin>>x;
        if (x>15) {x%=14;x+=14;}
        if(x>14 and x<21) cout<<"YES\n";else cout<<"NO\n";
    }
    return 0;   
}

B solution

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Here is a Detail explanation for Div2 D Here. Hope could be helpful to someone

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In the editorial of problem G, "the answer is $$$|p|⋅(|p|+1)−∑LCP[i]$$$", shouldn't it be $$$|p|⋅(|p|+1)/2−∑LCP[i]$$$ ?