When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

SoCloseButStillSoFar's blog

By SoCloseButStillSoFar, 15 months ago, In English

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.

1763A - Absolute Maximization

Idea: DreadArceus
Prepared by: DreadArceus

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

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

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

| Write comment?
»
15 months ago, # |
  Vote: I like it +24 Vote: I do not like it

Anyone got the DP solution for D please?

  • »
    »
    15 months ago, # ^ |
    Rev. 2   Vote: I like it +27 Vote: I do not like it

    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 K

    the 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)

    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

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

        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

    • »
      »
      »
      15 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Can you please tell why we always choose "(r-l+1) of highest distinct elements"?

  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
15 months ago, # |
Rev. 2   Vote: I like it -28 Vote: I do not like it

Hint for F before the editorial is out:

Hint 1
Hint 2
Hint 3
  • »
    »
    15 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    No, it is not true that the definition implies that the graph is a cactus.

    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it -25 Vote: I do not like it

      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?

      • »
        »
        »
        »
        15 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        A graph where simple cycles share no common vertex is a cactus graph, which is not what is described by the problem's conditions.

        • »
          »
          »
          »
          »
          15 months ago, # ^ |
            Vote: I like it -25 Vote: I do not like it

          Oh, now I saw that it's the set of vertices, not the set of edges. My bad, sorry!

  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what is a cactus graph

    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      "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

»
15 months ago, # |
Rev. 2   Vote: I like it +21 Vote: I do not like it

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.

  • »
    »
    15 months ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    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?

    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it +27 Vote: I do not like it

      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.

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

        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!

        • »
          »
          »
          »
          »
          15 months ago, # ^ |
          Rev. 3   Vote: I like it +61 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            7 months ago, # ^ |
              Vote: I like it -8 Vote: I do not like it

            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.

            • »
              »
              »
              »
              »
              »
              »
              7 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              How can you find the biggest cycle with a dfs? Isn't that the hamiltonian cycle problem, which is NP-complete?

              • »
                »
                »
                »
                »
                »
                »
                »
                7 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  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?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 months ago, # ^ |
                  Rev. 3   Vote: I like it -10 Vote: I do not like it

                  Shoot my b, this is NP

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

              I commend you on your efforts to prove P = NP, but this is very very poor.

    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I suppose this blog may help.

»
15 months ago, # |
  Vote: I like it +3 Vote: I do not like it

editorials with hints are appreciated:)

»
15 months ago, # |
  Vote: I like it +14 Vote: I do not like it

Is it rated ? Rating changes are rolled back without notice..

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

    Did you find out why it happened? I'd really like those points back :(

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

      They are removing the cheaters ! :) they will come back

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

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

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.

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

In problem C, solution, first paragraph, $$$m > l$$$ should be $$$m > r$$$.

  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks. Fixed it.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      can't understand case 3:
      case 3 is that :
      3
      4 9 5
      
      we can use this way
      (1,3) -> 1 9 1
      (1,3) -> 0 9 0
      (1,2)-> 9 9 0
      (1,3) or (2,3) ->9 9 9
      so that sum is 9+9+9 = 27 ?
      not 18?</br>
      
      • »
        »
        »
        »
        6 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        On second operation your array would become 0 0 0 :)

        Edit: just to elaborate

        The operation is applied to the whole subarray. So in your case the array would look like this 4 9 5 -> (1, 3) -> 1 1 1 -> (1, 3) -> 0 0 0

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like 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?

  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks, makes sense.

      • »
        »
        »
        »
        15 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I like your solution, although more difficult to implement. Could you explain how you come up with it ?

        • »
          »
          »
          »
          »
          15 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like 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.

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think you meant a suffix array there in problem B health solution.

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

Problem D, Mistake (typo) in first para of solution and spoiler under Hint1.

Fix
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for pointing it out! Will correct it.

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Just curious.. How to solve D with the bonus constraints ?

»
15 months ago, # |
  Vote: I like it +19 Vote: I do not like it

Thanks for such a amazing round guys :)

»
15 months ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

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...
Code
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you for sharing

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

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!

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Sorry for the delay in problem F's editorial. I hope it gives you more to think about!

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks for sol

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

For problem E Can anyone explain how for P = 4.

the answer is 5, 6

crimsonred, ...nvm, DreadArceus ?

cant the graph be like this:

which gives answer as 4, 0

  • »
    »
    15 months ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    Here there are 6 ordered pairs but we need exactly 4.

    Pairs:- $$$(1,2), (1,3), (1,4), (2,3), (2,4),(3,4)$$$

    • »
      »
      »
      15 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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)

      • »
        »
        »
        »
        15 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes and the directed edge (1,3) is unnecessary.

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

C was interesting. At first it looked like another mathematical array problem, but the solution turned out to be simple.

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

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

    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.

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

      Great, thanks for clarifying. I think it was a good decision to add such condition and make it solvable with other ideas as well :)

»
8 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

in Problem B testcase:

1

2 7

6 8

1 8

should give NO as per online judge, isn't it should give YES

  • »
    »
    6 months ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    same doubt

    after first attack:

    H: [0, 1]

    K: 7 — 1 = 6

    after second attack:

    H: [0, 0]

    K: 0

    all the monsters are killed before k becomes 0. correct me if i'm wrong

    UPD:

    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