### 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

Idea: crimsonred

Hint 1
Hint 2
Solution
Code

# 1763F - Edge Queries

Hint 1
Hint 2
Hint 3
Hint 4
Solution  Comments (84)
 » Anyone got the DP solution for D please?
•  » » 12 months ago, # ^ | ← Rev. 2 →   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)
•  » » » 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.
•  » » » » 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
•  » » » » » Thanks :)
•  » » » » » Thanks for sharing it.
•  » » » » » hahaha, just tagging tourist & neal like brothers.
•  » » » 12 months ago, # ^ | ← Rev. 2 →   Can you please tell why we always choose "(r-l+1) of highest distinct elements"?
•  » » 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 →   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.
•  » » No, it is not true that the definition implies that the graph is a cactus.
•  » » » 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?
•  » » » » A graph where simple cycles share no common vertex is a cactus graph, which is not what is described by the problem's conditions.
•  » » » » » Oh, now I saw that it's the set of vertices, not the set of edges. My bad, sorry!
•  » » what is a cactus graph
•  » » » "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
•  » » » A connected graph in which no two simple cycles have more than one vertex in common.
 » 12 months ago, # | ← Rev. 2 →   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.
•  » » 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?
•  » » » 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.
•  » » » » 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 →   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.
•  » » » » » » 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.
•  » » » » » » » How can you find the biggest cycle with a dfs? Isn't that the hamiltonian cycle problem, which is NP-complete?
•  » » » » » » » » 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.
•  » » » » » » » » » 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?
•  » » » » » » » » » 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 →   Shoot my b, this is NP
•  » » » » » » » I commend you on your efforts to prove P = NP, but this is very very poor.
•  » » » I suppose this blog may help.
 » editorials with hints are appreciated:)
 » Is it rated ? Rating changes are rolled back without notice..
•  » » Did you find out why it happened? I'd really like those points back :(
•  » » » They are removing the cheaters ! :) they will come back
 » 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.
•  » » 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 →   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.
 » In problem C, solution, first paragraph, $m > l$ should be $m > r$.
•  » » Thanks. Fixed it.
 » 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?
•  » » 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.
•  » » » Thanks, makes sense.
•  » » » » I like your solution, although more difficult to implement. Could you explain how you come up with it ?
•  » » » » » 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.
 » I think you meant a suffix array there in problem B health solution.
•  » » Thanks. Fixed it.
 » 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
 » 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)
•  » » Thanks for pointing it out! Will correct it.
•  » » Thanks! Fixed now.
 » Just curious.. How to solve D with the bonus constraints ?
•  » » Use binomial formula: sum(C(n,k))=2^n where k=0 to n
•  » » You may refer to this comment. A similar approach was also described by satyam343 during testing as well. Hope this helps :)
•  » » » Thanks a lot !
 » Thanks for such a amazing round guys :)
 » 12 months ago, # | ← Rev. 2 →   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: [], ................element 2: , ................element 3: [2, 3] ................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 = 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'; } 
•  » » 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?
•  » » » 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.
•  » » » » Now I got your point , Olympia Thank you very much for helping sir.
•  » » Thank you for sharing
 » 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!
 » Sorry for the delay in problem F's editorial. I hope it gives you more to think about!
 » thanks for sol
 » 12 months ago, # | ← Rev. 2 →   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?
 » Hey, I have a question about why the time complexity of B-solution1 is $O(nlogn)$.
•  » » 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.
 » anybody solved C using binary search ?
 » 11 months ago, # | ← Rev. 4 →   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 →   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 →   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)
•  » » » » Yes and the directed edge (1,3) is unnecessary.
 » 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,a=(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....
 »
 » C was interesting. At first it looked like another mathematical array problem, but the solution turned out to be simple.
 » Does anyone know of another blog that discusses the solution to problem F?
 » 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?
•  » » 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.
•  » » » Great, thanks for clarifying. I think it was a good decision to add such condition and make it solvable with other ideas as well :)