### SoCloseButStillSoFar's blog

By SoCloseButStillSoFar, 12 months ago,

We hope you liked the problems! Unfortunately, problem C turned out to be harder than usual. Please read its editorial, we hope you'll find that the intended solution is not that hard.

Hint 1
Hint 2
Need more hints?
Solution

# 1763B - Incinerate

Idea: og_
Prepared by: og_

Hint 1
Hint 2
Solution 1
Sort by power solution
Solution 2
Sort by health solution

# 1763C - Another Array Problem

Idea: .utk.
Prepared by: .utk.

Hint 1
Hint 2
Solution
Brute force solution
Case work solution

# 1763D - Valid Bitonic Permutations

Idea: warks
Prepared by: warks

Hint 1
Hint 2
Hint 3
Solution
Code

# 1763E - Node Pairs

Idea: crimsonred
Prepared by: ...nvm, DreadArceus, crimsonred

Hint 1
Hint 2
Solution
Code

# 1763F - Edge Queries

Prepared by: ...nvm, DreadArceus

Hint 1
Hint 2
Hint 3
Hint 4
Solution
• +123

 » 12 months ago, # |   +24 Anyone got the DP solution for D please?
•  » » 12 months ago, # ^ | ← Rev. 2 →   +27 from tourist's submission lets have dp[l][r] as number of ways we can construct our array from l to r, with elements [n-(r-l+1)+1, n] (basically (r-l+1) of highest distinct elements) regardless of Kthe next element we are gonna put is n-(r-l+1), so we try to extend out dp to the left and to the right to calculate dp[l-1][r] and dp[l][r+1]. Do not forget to check if the element we put next is valid to restrictons given wth (i, j, x, y)
•  » » » 12 months ago, # ^ |   0 I understood the solution of D that is provided in the editorial. But trying to understand the dp approach for the same. I saw many solved it by dp but not able to get my head around. Please explain anyone.
•  » » » » 12 months ago, # ^ |   +3 You can watch neal's video on Youtube. He fills numbers from left and right bounds to inner instead. Because the sequence is "bitonic", values filled must be in increasing order (you climb up to the peak from 2 sides).So, the same thing goes here: because you are filling from middle toward outer, values filled must be in decreasing order (you go down from the peak).See my submission: 186149744
•  » » » » » 12 months ago, # ^ |   0 Thanks :)
•  » » » » » 12 months ago, # ^ |   0 Thanks for sharing it.
•  » » » » » 10 months ago, # ^ |   -10 hahaha, just tagging tourist & neal like brothers.
•  » » » 12 months ago, # ^ | ← Rev. 2 →   0 Can you please tell why we always choose "(r-l+1) of highest distinct elements"?
•  » » 11 months ago, # ^ |   0 I used a similar DP to tourist's that might be slightly easier to understand. If anyone is interested, check my submission here. I also added some comments that might help in understanding.
 » 12 months ago, # | ← Rev. 2 →   -28 Hint for F before the editorial is out: Hint 1The provided definition of the given graph, actually means a cactus graph. no, it doesn't, my bad :facepalm: Hint 2What are the kind of edges we want to cut if we want to keep the path connected? Answer of Hint 2We want to cut the edges that lie on a simple cycle. Hint 3If we want to decompose a graph into simple cycles, what algorithm do we use? Answer for Hint 3We use the Biconnected Components algorithm. After using it, the graph of BCCs become a tree. Now we can use LCA/Mo's on trees/whatever algorithm we would use on trees, on this trees of BCCs.
•  » » 12 months ago, # ^ |   +2 No, it is not true that the definition implies that the graph is a cactus.
•  » » » 12 months ago, # ^ |   -25 Oh, I didn't realize that in the graph given there are no vertex in common between two simple cycles, that's my bad. Do we have a name specifically for this kind of graphs?
•  » » » » 12 months ago, # ^ |   0 A graph where simple cycles share no common vertex is a cactus graph, which is not what is described by the problem's conditions.
•  » » » » » 12 months ago, # ^ |   -25 Oh, now I saw that it's the set of vertices, not the set of edges. My bad, sorry!
•  » » 12 months ago, # ^ |   0 what is a cactus graph
•  » » » 12 months ago, # ^ |   0 "In graph theory, a cactus (sometimes called a cactus tree) is a connected graph in which any two simple cycles have at most one vertex in common. Equivalently, it is a connected graph in which every edge belongs to at most one simple cycle, or (for nontrivial cactus) in which every block (maximal subgraph without a cut-vertex) is an edge or a cycle." — Wikipedia
•  » » » 12 months ago, # ^ |   0 A connected graph in which no two simple cycles have more than one vertex in common.
 » 12 months ago, # | ← Rev. 2 →   +21 How does the validator for F work? I tried the Petersen graph (https://codeforces.com/contest/1763/hacks/878513) and the validator accepted it, but I believe it does not satisfy the condition of the problem statement. Did I input the graph wrong, or is it actually a valid test case?After some more experimentation, I feel that either I have grossly misunderstood the precondition as described in the problem or the validator is completely inconsistent with that precondition.
•  » » 12 months ago, # ^ |   -11 Hey, thanks for pointing this out.The validator for problem F removes bridges and then ensures that all the subgraphs remaining have no articulation points. This is enough to fail all the graphs that will cause solutions to the problem to fail.The Petersen graph doesn't have a Hamiltonian cycle and thus fails the condition given in the statement but will not fail any solutions or the validator.Since we cant find Hamiltonian cycles in all the subgraphs efficiently, the validator is made like this. According to the statement, the Petersen graph should fail though, sorry for the confusion.Do you have any suggestions to improve the validator?
•  » » » 12 months ago, # ^ |   +27 Thanks for the explanation. The condition in the problem statement seems like it might be infeasible to check. Probably the correct thing to do would have been to use a different condition or disallow hacking.
•  » » » » 12 months ago, # ^ |   +10 We had wanted to disable hacking but, in the end, thought that this validator would be enough. We were only thinking about the cases that cause solutions to fail and overlooked graphs like these.Sorry for the inconsistent validator. We will do better next time!
•  » » » » » 12 months ago, # ^ | ← Rev. 3 →   +61 It is possible to allow hacking in these kind of problems. We know that this reduces to largest cycle decomposition, with no intersections, as having two intersecting cycles implies there is larger cycle that contains both. Or in essence, the sum of sizes of all distinct largest cycles of each node is $n$. Therefore we can require it to be printed alongside the input when hacking. You can set up the problem to be interactive, to allow extra input in the hack alongside the input data. It would be interesting to have the hack format only available when you solve the problem, because it may serve as too large a hint to the solution.To verify the correctness of the largest cycle decomposition, you can iterate over all cycles in decreasing order of size. Notice that when you remove the largest cycle, no remaining connected component can have more than 2 edges towards the cycle, as that would imply there exists a strictly larger cycle. Now this implies there is no other cycle going through the largest cycle, so you can simply delete it, and look at the next largest cycle, independent of the nodes and edges of the largest cycle. This amortizes to $O(n\log{n})$ when implemented using a DSU with roll backs and a map.For the future, I would recommend all problem-setters to disallow hacking, or either only allow a subset of cases in hacks. It is not reasonable to allow input that does not satisfy the condition of the statement, because it's not guaranteed that every solution uses the same observation, even if it's true for the validator solutions, and may cause your round to be unrated.
•  » » » » » » 3 months ago, # ^ |   -8 I think I have a different way of the checking the validity of the graph.I'm pretty sure the restriction means that you basically have a cactus (each edge is in at most one cycle), except that the cycles can have spanning chords. So we can construct the block-cut tree of the graph and make sure that all the meta-nodes contain a cycle which only has spanning chords. You can find the cycle with DFS, then make sure all the additional edges in the component are all chords on the cycle.Please LMK if this check is incorrect.
•  » » » » » » » 3 months ago, # ^ |   0 How can you find the biggest cycle with a dfs? Isn't that the hamiltonian cycle problem, which is NP-complete?
•  » » » » » » » » 3 months ago, # ^ |   0 Because this is a special case we can find any cycle with the DFS, then continue finding cycles, and patch them together at the chords. If we have two adjacent cycles that share more than one edge, then we can immediately say this test is invalid.I thought about implementing this and submitting it to the judge to check if all the tests meet this condition, but it was quite annoying, so I didn't implement it.Basically we are taking advantage of the structure of the graphs we are looking for making the problem easier I think.
•  » » » » » » » » » 3 months ago, # ^ |   0 Are you saying to get all of the back edges in the dfs tree and check those? What if you have 1-2-3-4, where 3 and 4 have back edges to 1?
•  » » » » » » » » » 3 months ago, # ^ |   0 No I'm not saying that.What I am saying is you find some cycle in this component (any cycle it doesn't matter).Then you look at the endpoints with some un-visited edges going out, and you DFS again from there, finding another cycle that ends at either of your neighbors in the previous cycle. If you find a cycle that doesn't end at one of your neighbors, then you immediately quit because the graph is invalid; otherwise, you know the edge between you and your neighbor in the previous cycle must be a chord, so you can ignore that edge, and now patch these two cycles together into a single cycle. Now rinse & repeat. The process will terminate in linear time with respect to the size of the component.
•  » » » » » » » » » 3 months ago, # ^ | ← Rev. 3 →   -10 Shoot my b, this is NP
•  » » » » » » » 3 months ago, # ^ |   +3 I commend you on your efforts to prove P = NP, but this is very very poor.
•  » » » 12 months ago, # ^ |   0 I suppose this blog may help.
 » 12 months ago, # |   +3 editorials with hints are appreciated:)
 » 12 months ago, # |   +14 Is it rated ? Rating changes are rolled back without notice..
•  » » 12 months ago, # ^ |   +1 Did you find out why it happened? I'd really like those points back :(
•  » » » 12 months ago, # ^ |   +1 They are removing the cheaters ! :) they will come back
 » 12 months ago, # |   0 I think it is impossible to write a validator for F. I think that for graphs that are connected enough such that each two vertices share a circle,it is still hard to find whether there exists a hamilton circle.
•  » » 12 months ago, # ^ |   0 I think that biconnected graphs are enough to satisfy my condition,and finding a hamilton cycle for such graphs is equivalent with finding one in any graph.
 » 12 months ago, # | ← Rev. 5 →   0 When calculating ifac[i] we can calculating each (fac[i]^(mod-2))%mod individually, with time complexity is O(n*log(mod)), which may cause TLE when n is large. We can just calculate ifac[n]=(fac[n]^(mod-2))%mod, and ifac[i]=ifac[i+1]*(i+1)%mod, where i iterate from n-1 to 0, with complexity O(n+log(mod)), which is reduced to about 1/30.
 » 12 months ago, # |   +4 In problem C, solution, first paragraph, $m > l$ should be $m > r$.
•  » » 12 months ago, # ^ |   0 Thanks. Fixed it.
 » 12 months ago, # |   0 The author seems to be simulating the attacks in problem B, but since health can be up to a billion, couldn't simulating the attacks with a while loop cause TLE? In my case I used the quadratic formula to avoid this problem. What am I missing here?
•  » » 12 months ago, # ^ |   0 The problem statement states that $0 \le k \le 10^5$. The power of each monster is at least $1$. If there are still some monsters alive, $k$ will decrease by at least $1$ every iteration. If $k$ reaches zero before all monsters die, the answer is "NO". Thus, the loop will run for a maximum of $10^5$ iterations per test case before $k$ reaches zero, and since there are at most $100$ test cases, the loop will run for $10^7$ iterations in total at maximum, well within the time limit.
•  » » » 12 months ago, # ^ |   0 Thanks, makes sense.
•  » » » » 12 months ago, # ^ |   0 I like your solution, although more difficult to implement. Could you explain how you come up with it ?
•  » » » » » 12 months ago, # ^ |   0 I needed a way to calculate the number of attacks necessary to kill a given monster, but I hadn't noticed the subtlety that vgtcross pointed out, so instead I found a formula for the amount of damage dealt over m attacks, given Genos power level. Then I solved for m such that the damage dealt was equal to the monster's health, h, and took the ceiling of the solution as my number of attacks. Then Genos power level was reduced accordingly and I moved on through the list of monsters.
 » 12 months ago, # |   0 I think you meant a suffix array there in problem B health solution.
•  » » 12 months ago, # ^ |   0 Thanks. Fixed it.
 » 12 months ago, # |   0 I m doing the following solution for the problem B but it is giving WA on pretest 5 for 47th test case I am not able to figure out what is the mistake. Can anyone here help me out?186097185
 » 12 months ago, # |   +4 Problem D, Mistake (typo) in first para of solution and spoiler under Hint1. Fixi′=n−j+1, j′=n−i+1 (Should be +1, not -1, in both places)
•  » » 12 months ago, # ^ |   0 Thanks for pointing it out! Will correct it.
•  » » 12 months ago, # ^ |   0 Thanks! Fixed now.
 » 12 months ago, # |   0 Just curious.. How to solve D with the bonus constraints ?
•  » » 12 months ago, # ^ |   +8 Use binomial formula: sum(C(n,k))=2^n where k=0 to n
•  » » 12 months ago, # ^ |   0 You may refer to this comment. A similar approach was also described by satyam343 during testing as well. Hope this helps :)
•  » » » 12 months ago, # ^ |   0 Thanks a lot !
 » 12 months ago, # |   +19 Thanks for such a amazing round guys :)
 » 12 months ago, # | ← Rev. 2 →   +7 I like $D$ a lot :)$D$ can be done entirely without any math--just with dynamic programming.The first observation is that within a bitonic permutation, the position of the element 1 is either at the beginning of the array or at the end of the array. Likewise, element 2 is either adjacent to element 1 or at one of the endpoints. etc.So we can imagine constructing our "increasing" beginning part separately than our decreasing ending part. Say we have the permutation [2, 3, 6, 5, 4, 1]. Start with element 1: [], [1]................element 2: [2], [1]................element 3: [2, 3] [1]................element 4: [2, 3] [4, 1]................element 5: [2, 3] [5, 4, 1]................element 6: [2, 3, 6] [5, 4, 1] or [2, 3] [6, 5, 4, 1] (doesn't really matter)dp[left][right] is the number of ways to construct our sequence if we use only numbers from 1...left + right, with left numbers in the decreasing part and right in the increasing part.Transitions are easy: dp[left][right] += dp[left - 1][right] (add something to the left) dp[left][right] += dp[left][right - 1] (add something to the right) Now we just have to check to make sure that the index and value matches with $i, j, x, y$, which can be done easily. Spoiler...Also permutation has to be bitonic, not strictly increasing/decreasing, so take care of that!!! Codevoid solve () { int n, i, j, x, y; cin >> n >> i >> j >> x >> y; i--, j--, x--, y--; int64_t MOD = 1e9 + 7; int64_t dp[n + 1][n + 1]; for (int left = 0; left <= n; left++) { for (int right = 0; right <= n; right++) { dp[left][right] = 0; } } dp[0][0] = 1; for (int left = 0; left <= n + 1; left++) { for (int right = 0; left + right <= n; right++) { int val = left + right - 1; if (left != 0) { if (((left - 1 == i) == (val == x)) && ((left - 1 == j) == (val == y))) { dp[left][right] += dp[left - 1][right]; } } if (right != 0) { if (((n - right == i) == (val == x)) && ((n - right == j) == (val == y))) { dp[left][right] += dp[left][right - 1]; } } dp[left][right] %= MOD; } } int64_t val = 0; for (int left = 0; left <= n; left++) { val += dp[left][n - left]; val %= MOD; } int64_t ans =(val * (MOD + 1)/2) % MOD; ans -= (i == x && j == y); ans -= (i == n - x - 1 && j == n - y - 1); cout << ans << '\n'; } 
•  » » 12 months ago, # ^ |   0 Olympia, can you please explain more clearly, what do you mean by (in taking your permutation example), start with element 1, ... With element 2, .... so on ?What are you trying to say , I am not able to get that?
•  » » » 12 months ago, # ^ |   0 Start placing the elements in increasing order of value. That is, first decide if the element with value 1 is in the "increasing" or "decreasing" half; then decide if the element with value 2 is in the "increasing" or "decreasing" half; then decide if the element with value 3 is in the "increasing" or "decreasing" half; and so on.As in the example, I started placing elements with value 1, then 2, then 3, then 4, then 5, then 6.
•  » » » » 11 months ago, # ^ |   0 Now I got your point , Olympia Thank you very much for helping sir.
•  » » 7 months ago, # ^ |   0 Thank you for sharing
 » 12 months ago, # |   +4 Hi,A (partial) solution that I could come up with for problem F:Let $x$ be some vertex and $C$ be the largest cycle containing $x$. By the problem statement, all cycles $C'$ to which $x$ belongs to must be a subset of $C$. Define $\sigma(x) = \{(p,q) \in E \text{ | } p \in C \text{ and } q \in C\}$.Also let $\tau(x) = |\sigma(x)|$Now, I claim that if $x$ lies on a simple path between any given two nodes $a$, $b$, then every $e \in \sigma(x)$ lies on a simple path between $a$ and $b$. Further every such edge is non-critical. (We say an edge $e$ lying on a simple path between $a$ and $b$ is non-critical if $G-e$ has a path between $a$ and $b$.) I do not have a formal proof for this, but you can see this by trying out examples on a piece of paper.Now we can abstract away the set of vertices contained in each longest cycle as a super node. Each such super node will contain a pointer to the value $\tau(x)$ where x is any point on the cycle. Further nodes not contained in any cycle can also be considered as supernodes (for simplicity) comprising of just the node itself and having $\tau$ value as 0. Any edge in the original graph connecting two largest cycles will be considered as an edge between the two supernodes (corresponding to these largest cycles) in the new graph.Now the new graph will just be a tree (notice this means it will also be connected). We can store which vertices belong to which supernode in a array. Now given $a$ and $b$, we find out the supernode containing $a$ and $b$, say $A$ and $B$ resp. We just find the sum of $\tau$ values along the path from $A$ to $B$ (including the end points). This I think can be done in $O(1)$ (?) through prefix sums. I am not sure how to implement it in a tree, but I am pretty sure it can be done as array prefix sums is just a special case of this.Please do let me know in case you find a mistake in my reasoning, or wish to improve it. Thanks!
 » 12 months ago, # |   0 Sorry for the delay in problem F's editorial. I hope it gives you more to think about!
 » 12 months ago, # |   0 thanks for sol
 » 12 months ago, # | ← Rev. 2 →   0 Hi!I don't know what's the issue with my codes (Problem B)...I had a different approach while solving it in the contest, this avoided TLE in pretests during the contest but gave TLE during system testing. 185981259 Now, I am solving it using the author's approach but getting TLE on test 2. 186230779Can someone please point out what I can do to correct it?
 » 12 months ago, # |   0 Hey, I have a question about why the time complexity of B-solution1 is $O(nlogn)$.
•  » » 12 months ago, # ^ |   0 Firstly the sorting takes O(NlogN) After that we iterate through the vector while also decreasing k. This is O(N) not O(N*K) because K doesn't get reseted so the sum over all operations in that for loop is N + K. This thought process is similiar to the one that to 2pointers uses.
 » 12 months ago, # |   0 anybody solved C using binary search ?
 » 11 months ago, # | ← Rev. 4 →   0 For problem E Can anyone explain how for P = 4.the answer is 5, 6cant the graph be like this:which gives answer as 4, 0
•  » » 11 months ago, # ^ | ← Rev. 2 →   +3 Here there are 6 ordered pairs but we need exactly 4.Pairs:- $(1,2), (1,3), (1,4), (2,3), (2,4),(3,4)$
•  » » » 11 months ago, # ^ | ← Rev. 2 →   0 Thank you,I kept thinking (u, v) as a directed edge and completely forgot that ordered pairs were asked.BTW this will be answer for p = 4?The p reaches pairs are : (1, 2), (1, 3), (2, 3), (4, 5)and the unidirectional pairs are : (1, 4), (1, 5), (2, 4), (2, 5), (3, 4), (3, 5)
•  » » » » 11 months ago, # ^ |   0 Yes and the directed edge (1,3) is unnecessary.
 » 11 months ago, # |   0 In problem number 3 Another Array Problem , For N=3 when largest element is at middle why we do Case 1: We can apply the operation on (1,2), then we can convert all the elements of the array into max(a3,|a2−a1|). Let number if 1 3 1 for i=1,j=2 we convert a[1],a[2]=(3-1)=2 final array = 2 2 1 then if we apply for i=2,i=3 we get array 2 1 1 , sum=4 but with the case 1 we can able to get 6 why ....... please correct me....
 » 11 months ago, # |   0
 » 11 months ago, # |   0 C was interesting. At first it looked like another mathematical array problem, but the solution turned out to be simple.
 » 11 months ago, # |   0 Does anyone know of another blog that discusses the solution to problem F?
 » 11 months ago, # |   0 About problem F:Is the "tree of BiConnected Components" mentioned in the editorial the same as the block-cut tree of the graph? From the description I think it is not, and I think that the solution when using the block-cut tree of the graph is quite similar, but maybe simpler. I also think that when using the block-cut tree, the solution works for any graph, without needing the condition mentioned in the statement. Did anyone do the same? Or could someone explain why the condition in the statement is necessary for the solution to be correct?
•  » » 11 months ago, # ^ |   +8 You are correct. The block-cut tree solution works for any graph. A few participants did solve it that way.However, F was not intended to require knowing about block-cut trees. The condition in the statement makes this problem solvable with a few creative ideas as well.
•  » » » 11 months ago, # ^ |   +1 Great, thanks for clarifying. I think it was a good decision to add such condition and make it solvable with other ideas as well :)
 » 11 months ago, # |   0 Please help me with the time complexity of this solution code Please help me with the time complexity of this solution code Every help will be highly appreciated
 » 11 months ago, # |   0 Why there isn't any code solution?? It's really easy to understand code more than theory..
 » 10 months ago, # |   0 I am using min heap to solve problem B, but confused for the case when power is equal for all monsters but health is different for them. so, in this case if i am solving by creating min heap over power of monsters, in what order i must attack the monsters?
 » 10 months ago, # |   0 IN solution 2 of problem B you forgot to sort the array containing health of monsters.
 » 5 months ago, # | ← Rev. 3 →   0 in Problem B testcase:12 76 81 8should give NO as per online judge, isn't it should give YES
•  » » 3 months ago, # ^ | ← Rev. 4 →   0 same doubtafter first attack:H: [0, 1]K: 7 — 1 = 6after second attack:H: [0, 0]K: 0all the monsters are killed before k becomes 0. correct me if i'm wrongUPD:Ok I got it, K is decreased by the amount of the power of the minimum ALIVE monster. So we don't subtract the power of the first monster after first attack as it will be killed after the attack. So we have to subtract the power of the second which makes K <= 0