### majk's blog

By majk, 5 years ago,
• +159

| Write comment?
 » 5 years ago, # |   +11 Wow, fastest editorial out there!
 » 5 years ago, # |   +97 Gap between E and F is HUUUUUGGGGGEEEEE :C
 » 5 years ago, # |   +15 Fast Editorial and system testing :)
 » 5 years ago, # |   +30 epic F...
 » 5 years ago, # |   +4 wow fastest guide ever i have seen
 » 5 years ago, # |   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 years ago, # |   0 Yeeee. This is the fastest guide I've ever seen
 » 5 years ago, # |   +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 years ago, # |   +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 years ago, # ^ |   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 years ago, # ^ |   +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 years ago, # ^ |   0 Sorry, confused in the letters :D
 » 5 years ago, # |   0 https://codeforces.com/contest/1266/submission/6708325 Please someone can find mistake in my first question solution..
•  » » 5 years ago, # ^ |   +3 Your link is incorrect. This one I think you mentioned. Try this test: 100. Your output I think red, instead of cyan.
•  » » » 5 years ago, # ^ |   0 thanks for your reply.. i found my mistake
 » 5 years ago, # | ← Rev. 3 →   -27 Thanks for the quick editorial!!!
 » 5 years ago, # |   +74 H is very cool, one of my favorite problems now. Thanks!
•  » » 5 years ago, # ^ | ← Rev. 2 →   +45 Then I have a bonus for you: remove the condition that vertex $n$ is reachable from every vertex reduce n to $36$ answer the question whether the token will end up in $n$ or not, and if so, at what time
•  » » » 5 years ago, # ^ |   +13 It looks like this bonus is a previous code jam problem from a while ago: https://code.google.com/codejam/contest/2075486/dashboard#s=p4&a=2
•  » » » » 5 years ago, # ^ |   +14 Damn! It's really difficult to come up with something original.
 » 5 years ago, # |   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 years ago, # ^ | ← 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 years ago, # ^ | ← 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 years ago, # ^ |   +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 years ago, # |   0 It would be really helpful if someone could provide the thought process required for C,as it is a constructive algo?
•  » » 5 years ago, # ^ |   +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 years ago, # |   +15 good contest !Thanks majk !
 » 5 years ago, # |   +7 Why is it clear in problem D that we can't do better than sum of balances divided by 2?
 » 5 years ago, # |   +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: Add value $v$ to the set (in $\mathcal{O}(v)$ time) Decrement value $v$ that appears in the set (in $\mathcal{O}(1)$) 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 years ago, # ^ | ← 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 years ago, # |   0 In D editorial can someone explain "We have just reduced the total debt by z, which is a contradiction."
•  » » 5 years ago, # ^ |   +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 years ago, # | ← Rev. 2 →   0 [DELETED]
 » 5 years ago, # | ← 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 1Edit: It is .. nevermind
 » 5 years ago, # |   +39 In problem H: These two conditions are in fact necessary and sufficient. How to prove that these conditions are sufficient?
 » 5 years ago, # |   +3 https://codeforces.com/contest/1266/submission/67100495Can someone tell why my solution is failing in D. Is there something to do with it out of bounds?
•  » » 5 years ago, # ^ |   +33  a[u] = 0; a[v] = a[v]+a[u]; You should swap these two lines.
•  » » » 5 years ago, # ^ |   +3 Shit. How could I make such mistake. Thanks for help.
 » 5 years ago, # |   0 Thanks for the contest!
 » 5 years ago, # |   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 years ago, # ^ |   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 years ago, # ^ |   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)
•  » » » » 4 years ago, # ^ |   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
•  » » » » » 4 years ago, # ^ |   0 Thanks,I got it
 » 5 years ago, # |   +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 years ago, # ^ |   +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 years ago, # ^ |   +29 I can make a test which makes it memoize $O(n2^{n/2})$ states.
•  » » 5 years ago, # ^ |   +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 years ago, # |   0 Could anyone help me why the following solution is incorrect for C? I hope my logic was correct.https://codeforces.com/contest/1266/submission/67161724
•  » » 5 years ago, # ^ |   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 years ago, # | ← Rev. 2 →   +8 Two doubts for problem D editorial 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" how do we find the final debts i.e. the second half of the answers , the remaining edges.
•  » » 5 years ago, # ^ |   0 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. 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 years ago, # ^ |   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 years ago, # |   +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 years ago, # ^ |   +1 Hey, I was also stuck on this. However, the question states that ti < ai.
 » 5 years ago, # |   +25 In problem H,why are these two conditions sufficient?
•  » » 4 years ago, # ^ | ← 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 years ago, # |   -11 #include #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
 » 4 years ago, # |   0 Here is a Detail explanation for Div2 D Here. Hope could be helpful to someone
•  » » 4 years ago, # ^ |   0 This is the worst and the most unrigorous explanation I have ever seen.
•  » » » 4 years ago, # ^ |   0 Well Sorry for that.I will try to improve
 » 4 years ago, # |   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]$ ?