PikMike's blog

By PikMike, history, 4 weeks ago, translation, In English,

1257A - Two Rival Students

Idea: Roms

Tutorial
Solution (adedalic)

1257B - Magic Stick

Idea: BledDest

Tutorial
Solution (Ne0n25)

1257C - Dominated Subarray

Idea: adedalic

Tutorial
Solution (adedalic)

1257D - Yet Another Monster Killing Problem

Idea: Roms

Tutorial
Solution (Roms)

1257E - The Contest

Idea: Vovuh

Tutorial
Solution (BledDest)

1257F - Make Them Similar

Idea: Vovuh

Tutorial
Solution (BledDest)

1257G - Divisor Set

Idea: adedalic

Tutorial
Solution (adedalic)
 
 
 
 
  • Vote: I like it
  • +65
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

Tutorial for problem E isn't working

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

Bruh editorial for F and G are the same for some reason[now fixed]

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

didn't understand what is written after "max ai<=bstx" in D

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The greedy solution to the problem involves repeatedly defeating as many monsters as we can in every day. Suppose that on a given day, we have already defeated all monsters before index cnt. We will iterate from cnt, and find the range of monsters which we can defeat on this day, using the bst array as described in the editorial. To move on to the next day, we will set our cnt to the first monster that could not be defeated on this day, and repeat the process, incrementing our answer each time or printing -1 if we ever find that there is a monster that we cannot defeat under any circumstances.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      why are we calculating the bst array and what's the reason behind doing it the way it is being done in the editorial?

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The $$$bst$$$ array allows us to decide whether or not it is possible to defeat a certain range of monsters. $$$bst[i]$$$ represents the hero with the most power, given that they have $$$i$$$ or more endurance, which allows us to quickly answer the question: Given some range of $$$k$$$ monsters with maximum power $$$p$$$, is it possible, using the heroes that you have, to defeat these monsters? The answer is yes if $$$p\leq bst[p]$$$, otherwise no.

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          How do we intuitively think about it. This is a new way to solve a problem that I have encountered. Can you please suggest some similar problems so that it becomes clearer?

          thanks

          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I don't think I know of any problems that are like this, but here's some attempt at making the solution more intuitive:

            At each day, you want to kill as many monsters as possible. This is because to reach a certain day, what has happened before does not matter. Let's consider the first case from sample input:

            Monsters: $$$(2, 3, 11, 14, 1, 8)$$$
            Heroes: $$$((3, 2), (100, 1))$$$

            To kill the first two monsters, there are two ways of doing so: we can use the hero $$$(3, 2)$$$ once, or by using the hero $$$(100, 1)$$$ twice. The first option will take one day, while the second will take two days. Since what happened before we have reached the state of two killed monsters does not matter, we want to minimize the time it takes to do that. If you still have trouble understanding why it's optimal to kill as many monsters each day as possible, I encourage you to try to come up with a counterexample to better understand why.

            To see how we can kill as many monsters as possible per day, there is a simple $$$O(nm)$$$ solution. Let's say we start the day on the first monster in the sample input.

            Can we beat the first monster, with power $$$(2)$$$? We answer this by looping through all of the heroes that we have. It is possible for hero one, because the monster does not have a greater power. It is also possible for hero two, for the same reason.

            Now, let's extend our range. Can we beat the first two monsters, which have power $$$(2, 3)$$$? It is possible for hero one, because it has power greater than or equal to all of these monsters, and it has endurance $$$2$$$. It is not possible for hero two, because although it has enough power, it does not have enough endurance.

            With the first three monsters, we have the powers $$$(2, 3, 11)$$$. For both heroes, it is no longer possible to beat this whole range because they both do not have enough endurance to do so.

            From our first day, we now see that we can beat at most two monsters. We increment our answer, and repeat the process starting at the third monster, which we could not beat on the first day. It is also necessary to identify monsters which you cannot beat, given any number of days.

            However, our simple $$$O(nm)$$$ solution is clearly not fast enough to pass with the given constraints. Here is where the $$$bst$$$ array comes in. However, before we even consider the $$$bst$$$ array, let's first think about another array, $$$a$$$, such that $$$a[i]$$$ tells us the maximum power out of all heroes with endurance $$$i$$$. Let's make a new list of heroes for this: $$$((3, 1), (4, 1), (1, 1), (7, 3))$$$. Then, $$$a[1]$$$ would be $$$4$$$, $$$a[2]$$$ would be $$$0$$$ (uninitialized), and $$$a[3]$$$ would be $$$7$$$. Effectively, what this does is remove heroes that we would never use. The value of $$$a[1]$$$ is $$$4$$$, because we will never need to use $$$(3, 1)$$$ or $$$(1, 1)$$$. But if we look closely, We can see that even $$$(4, 1)$$$ will never be used. This is because $$$(7, 3)$$$ can act as $$$(7, 2)$$$ and $$$(7, 1)$$$ as well. To pick the maximum power for a range of heroes with length $$$k$$$, we take the maximum of $$$a[k], a[k + 1] ...$$$, or in other words, the suffix maximum.

            What the $$$bst$$$ array represents is the best option to choose if we are given some range of monsters with a certain length, and is simply the suffix maximum of the array $$$a$$$ that we described above. This can be found in linear time, but I will not explain it here as there are plenty of resources online to help you out with that :)

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

              Thats really a lot of help. Thanks for the effort :D

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

And for how long does solution for D work? I thought about similar idea during the round but didn't write this, because I thought it is too slow

»
4 weeks ago, # |
Rev. 3   Vote: I like it +4 Vote: I do not like it

Hi, I don't understand your construction for the Hasse diagram in G completely. Since you say that divisor of $$$deg(i)$$$ lies on level $$$i$$$, I will assume that you mean each prime is to be taken as seperate element of the final set. You say that $$$deg(2.3.2) = 3$$$, and also that if $$$x|y \implies deg(y)>deg(x)$$$, but if the set of primes is $$${2,3,2}$$$ then don't $$$(1,0,0)$$$ and $$$(0,0,1)$$$ lie on the same level but each divides the other (Where I have written $$$1$$$ means it contains that prime, and $$$0$$$ if it doesn't)?

Also, it would be great if you would provide some link for standard notation on this, I'm familiar with posets but haven't used it formally in proofs yet.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    "...I will assume that you mean each prime is to be taken as separate element of the final set..."

    Why did you assume that? $$$2 \cdot 3 \cdot 2 = 12$$$. It has the following divisors: $$$[1, 2, 3, 4, 6, 12]$$$ with following degrees $$$deg = [0, 1, 1, 2, 2, 3]$$$. So $$$1$$$ is on the level $$$0$$$, $$$2$$$ and $$$3$$$ — on the level $$$1$$$, $$$4$$$ and $$$6$$$ — on the level $$$2$$$ and $$$12$$$ is on the level $$$3$$$.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think he treats (1, 0, 0) and (0, 0, 1) about which you talk about as the same element, in particular in the Hasse diagram, because they give the same result after doing the multiplication.

    The problem later comes down to calculating the number of different elements in the middle layer. Although, I am not sure what we should do if there are two middle layers, i.e. when n is odd. Maybe it can be proven that they have the same sizes--I know this is true if every prime in the factorisation of our number occurs exactly once.

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

Can someone give a better understanding for Problem E? I can't seem to understand how prefixes and suffixes can be used here.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice explanation and solution for the G.

Thanks for the tips for NTT.

»
4 weeks ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Can you please explain the $$$LIS$$$ solution for $$$E$$$ too bledDest and PikMike?

where the answer is $$$k_1 + k_2 +k_3 -|LIS|$$$

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

    For each person, you may order their problem numbers however you want. So let's just represent them uniquely by sorting them. Now consider the sequence obtained by concatenating 3 of the sequences in order. Our goal is to obtain the sequence 1, 2, ..., n by doing as little following operation as possible: pick a number, and insert it to any position you want.

    Note that minimizing the operation is equivalent to maximizing the number of numbers which we do NOT perform the operation on. Such numbers should preserve their order during our operations and since our final sequence is increasing, so should they. Therefore, the number is bounded by the length of LIS of the original sequence. Note that when we perform our operations, it's always possible to obtain this bound by just picking every number NOT in the LIS and putting them in the right position. Therefore, our answer is N — (the length of LIS).

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

problem D I use the same approach and got TLE :p 64910563

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

    you memset bst array to 0 . which require 200000*1000 times . thats why you got TLE . just memset only n elements of that array every test case .

»
4 weeks ago, # |
Rev. 3   Vote: I like it +14 Vote: I do not like it

Alternate solution for E:

First, precalculate $$$p_i$$$, which denotes the contestant that starts with the $$$i$$$-th problem, for all $$$n$$$ problems.

Define function $$$f(i, j)$$$ to be the minimum number of moves required to correctly distribute the first $$$i$$$ problems if you can only use the first $$$j$$$ contestants.

$$$f(0, j) = 0$$$, $$$f(i, 0) = \infty$$$, and $$$f(i, j) = \min (f(i, j-1), f(i-1, j) + [p_i \neq j])$$$. Square brackets denote Iverson brackets, i.e. $$$1$$$ if the predicate is true and $$$0$$$ otherwise.

This recurrence can be easily computed using DP. The final answer is $$$f(n, 3)$$$. Sample code: 64862033

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

PikMIke I think there is a typo in Tutorial of B. 3 can be transformed to 2 and 1 both. It says

3 can be transformed only into 2

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In the tutorial, they're talking about performing only one spell (move). In one move, you can transform 3 to only 2. In the next move, you can transform 2 back to 3, or to 1, so eventually, you can transform 3 to 1, in 2 moves.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

So why did the naive brute-force, which iterated through $$$0$$$ to $$$2^{30}-1$$$, fails on the $$$92$$$-th test with verdict $$$\color{red}{\texttt{Wrong Answer}}$$$?

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

    About your submission 64859912 that failed on test 92, it was because your vector $$$a$$$ would have less than $$$n$$$ elements after removing duplicated elements, but I see you fixed that in your next submission 64860800.
    I uncommented your $$$\text{random_shuffle}$$$ line and resubmitted, and somehow it got accepted in 3354 ms 65024581 :)). I also implemented your algorithm myself, and it ran even faster in 2074 ms 65024286 :)).

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      My code are born with huge constants...

      So why using $$$\texttt{random_shuffle}$$$ could result in correct?

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Actually it turns out not the random-shuffling got it accepted, but because I used C++17 instead of C++11 :))

        I guess the C++17 version has some new optimizations...

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Now I am in a country that does not even allow the use of C++11 in official contests...

          I think it may still be some undefined behaviors, and C++17 is smart enough to sort them out, or, some functions behave differently, or both.

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            You're from China, and even China doesn't allow C++11 ???

            I don't think it is about undefined behavior, just some optimizations deep inside the compiler.

            • »
              »
              »
              »
              »
              »
              »
              4 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Well, C++11 is allowed in national contest and above, but not the provincial contest.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So this problem is really no difference for meet-in-the-middle and brute-force, right?

      I mean, it is not such a wise choice to put a problem that can be solved with the most naive brute-force on the position of problem F... Maybe swapping it with E or D could result in a better contest. (I VPed it)

      Or is the whole purpose of the problem "to scare you so that you will not use brute force with $$$2^{30}$$$ constraints"?

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think the authors didn't intend to let the brute-force solution to pass because of its high complexity. But when implemented optimally, it still runs faster than some meet-in-the-middle implementations.

»
4 weeks ago, # |
  Vote: I like it +33 Vote: I do not like it

we always can incriminate this distance

What crime should we charge it with?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Could anyone can explain the LIS solution to E?

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

    The E-question decision is obviously monotonous: First, the problem is transformed into a sequence of 123 with length n. Now we need to select two breakpoints and divide it into 3 segments, so that the number of 3 in the 1+ second segment of the 1st segment and the third segment in the third segment The sum of the sum. You can think of it this way, first select the first point, consider where the second point is optimal, the number of the following 2 is fixed, assuming G, consider the number of 3 in a suffix -2 The number is represented by P[i], and the answer is max(P[i]+G+ the number of the first 1) Then we can make the suffix P[i] the largest. Because the operation of max is obviously monotonous

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks!The first sentence of your words make me realize the purpose of the quention.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        the translation has something wrong.if you can't understand what I am talking about you can add my QQ number 196413732 or Deep_Kevin in Wechat

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is the G problem constructed correctly?

»
4 weeks ago, # |
Rev. 3   Vote: I like it +7 Vote: I do not like it

For E (how to get cntl2-cntl1):

cntm1 + cntr1 + cntl2 + cntr2 + cntl3 + cntm3 =

len1 — cntl1 + cntl2 + cntr2 + len3 — cntr3 =

cntl2 — cntl1 + (len1 + len3 + cntr2 — cntr3)

(len1 + len3 + cntr2 — cntr3) — constant for constant r

So we just need to minimize cntl2 — cntl1

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I understand len 1 and len 2 is a constant. but why cntr2 — cntr3 is a constant? :( hard to understand...

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    could you help me why there’s no cntm_i in solution code?/

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what is len 1 and len 3?

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The number of assignments person 1 and person 3 start with

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I didn't understand how I could iterate through the array to find the duplicate elements in it with the time complexity being O(N) in problem C. All I could think of was O(N^2) complex solution which is a brute force approach. Can someone explain me how O(N) is possible. TIA.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Problem C makes use of the two-pointer approach. Let $$$i$$$ and $$$j$$$ represent the left bound and right bound of the subarray that you are looking at right now. Initially, $$$i = 0$$$, and $$$j = 0$$$. Increment $$$j$$$ until you have at least two of some number in your subarray. This will be the shortest dominated subarray starting at $$$i$$$. Now, to find the shortest dominated subarray starting at $$$i + 1$$$, we realize that removing the element at $$$i$$$ from our can result in one of two outcomes:

    1) The element at $$$i$$$ was one of the duplicate elements in our subarray from $$$i$$$ to $$$j$$$. Then, our subarray is no longer dominated, and we will move $$$j$$$ until our subarray is dominated again.
    2) The element at $$$i$$$ was not one of the duplicate elements in our subarray from $$$i$$$ to $$$j$$$. Then the subarray from $$$i + 1$$$ to $$$j$$$ is dominated.

    We will repeat this process until $$$j$$$ reaches the end of our array, which is a total of $$$n$$$ times, resulting in $$$O(n)$$$ complexity.

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

    You can use map to store index of the particular element and after that calculate which two indexes has minimum difference and adding to that difference is your answer.

    like : if element is 2 and it appear at 1,6,8 index you can store as list[2].push_back(1,6,8) and this can be done for rest of elements and calculate difference of consecutive element (6-1) and (8-6) so our answer will be (8-6)+1

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any flaw with my idea of a solution for G?

You construct a Hasse diagram for a poset P such that $$$a<b$$$ for distinct a, b iff $$$a | b$$$. Then, you want to find the maximal antichain size, so by Dilworth, this is equivalent to counting how many times you erase the top level of the poset.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't know what you mean by "counting how many times you erase the top level of the poset". How would you find the maximal antichain size, which by Dilworth's is equal to the minimal chain decomposition size, efficiently enough?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone tell me how to solve problem D using DP

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

In problem D can anyone explain why ?? sorting the heroes by decreasing endurance and then then killing the monsters so that we can finish it in minimum number of days does not work. My solution fails on test 2 case 18 giving 4 instead of 5.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you may make some mistakes in your code. may you use binary algorithm, In the process,not ues l,but initial l.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem F of last Educational round also uses NTT..

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

Can someone counter case(help me find the flaw or what else i have to do ) my solve for E 65107304 . the idea : for contestant_1 iterate i from 1 to n; keep 1 to i and throw the rest away. So, res variable stores the best value for i such that we throw the minimum while filling the missing ones. The same for contestant 2 ... i start from i+1 to n; use thrown away numbers from const_1 or bring them from const_3...and throw the rest away.

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

I tried implementing the above solution code in python https://codeforces.com/contest/1257/submission/65126544 Can anyone point out as to why i am getting a runtime error. Thanks!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone can explain me problem E in brief ? Im not able to understand the tutorial.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem E,I have a good solution. First we divide 1<->n to 3 parts,1<->i,i<->j,j<->n We Enum j from 1-n and we calc best i We assume we have a fixed j and best i now,and if j is fixed,i is best position Now, we move j to next pos if a[j] in third persons hands,no matter where i is , ans += 1,because a[j] must give to first person or second person, if a[j] in second persons hands, it is easy to find that ans -= 1,because,you don't need to give it to third person, and you can not give it to first person,because that would not make ans better. if a[j] in first persons hands. either ans not change(we give it to second person) or we make i == j ,to see if that would make ans better My solution is https://codeforces.com/contest/1257/submission/65466989

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell the heavily optimised brute force of F?

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D, instead of making a bst array I made a vector of pairs where each element is (power , endurance) and the vector is sorted in increasing order of power. Then I did a step for(ll i=m-2;i>=0;i--)w[i].se=max(w[i].se,w[i+1].se); After this I can calculate the max endurance of a warrior available that can defeat monster of power i using lower_bound(w.begin,w.end,i).So I will iterate over the monsters such that a new day is required when endurance of a hero is over or we need a new hero but its endurance is lesser than the no of days since the current hero is fighting (or else this hero can replace him and new day won't come). But I got TLE in test 16. https://codeforces.com/contest/1257/submission/66306408

»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Awesome contest