### pikmike's blog

By pikmike, history, 10 months ago, translation,

1257A - Two Rival Students

Idea: Roms

Tutorial

1257B - Magic Stick

Idea: BledDest

Tutorial
Solution (Ne0n25)

1257C - Dominated Subarray

Tutorial

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

Tutorial

• +65

 » 10 months ago, # |   +12 Tutorial for problem E isn't working
•  » » 10 months ago, # ^ |   +3 They also messed up the superscript in problem F
•  » » » 10 months ago, # ^ |   +6 Will be updated in a few moments. Sorry for the inconvenience.
•  » » 10 months ago, # ^ |   +4 Whoops, fixed
•  » » » 10 months ago, # ^ |   +3 Ok, now fix G. :)
•  » » » » 10 months ago, # ^ |   +32
•  » » 9 months ago, # ^ |   0 Hi, video tutorial for problem E: https://www.youtube.com/watch?v=i-2hXsCDDg8
•  » » » 4 months ago, # ^ |   0 This is really good. Underrated though.
•  » » » 3 months ago, # ^ |   0 Very nice!
 » 10 months ago, # | ← Rev. 2 →   0 Bruh editorial for F and G are the same for some reason[now fixed]
 » 10 months ago, # |   0 didn't understand what is written after "max ai<=bstx" in D
•  » » 10 months ago, # ^ |   0 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.
•  » » » 10 months ago, # ^ |   0 why are we calculating the bst array and what's the reason behind doing it the way it is being done in the editorial?
•  » » » » 10 months ago, # ^ |   0 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.
•  » » » » » 10 months ago, # ^ |   0 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
•  » » » » » » 10 months ago, # ^ |   0 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 :)
•  » » » » » » » 10 months ago, # ^ |   +1 Thats really a lot of help. Thanks for the effort :D
•  » » » » » » » 8 months ago, # ^ |   0 my submissionPLEASE HELP ME ..I HAVE DONE EXACTLY WHAT YOU HAVE SAID AND SPENT A LOT OF HOURS DEBUGGING .STILL NOT WORKINGTHANKS IN ADVANCE
 » 10 months ago, # |   0 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
•  » » 10 months ago, # ^ | ← Rev. 2 →   0 its work for O(n)
•  » » 10 months ago, # ^ |   +2 Each Monster is visited atmost twice. So O(n)
 » 10 months ago, # | ← Rev. 3 →   +4 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.
•  » » 10 months ago, # ^ |   +5 "...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$.
•  » » 10 months ago, # ^ |   0 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.
 » 10 months ago, # |   +4 Can someone give a better understanding for Problem E? I can't seem to understand how prefixes and suffixes can be used here.
 » 10 months ago, # |   0 Nice explanation and solution for the G.Thanks for the tips for NTT.
 » 10 months ago, # | ← Rev. 2 →   +1 Can you please explain the $LIS$ solution for $E$ too bledDest and PikMike?where the answer is $k_1 + k_2 +k_3 -|LIS|$
•  » » 10 months ago, # ^ |   +17 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).
 » 10 months ago, # |   0 problem D I use the same approach and got TLE :p 64910563
•  » » 10 months ago, # ^ | ← Rev. 3 →   0 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 .
•  » » » 10 months ago, # ^ |   0 never notice this, thanks for help!
 » 10 months ago, # | ← Rev. 3 →   +14 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
•  » » 10 months ago, # ^ |   0 nice solution
•  » » 10 months ago, # ^ |   0 My solution during the round was the same.64828680
 » 10 months ago, # |   0 PikMIke I think there is a typo in Tutorial of B. 3 can be transformed to 2 and 1 both. It says3 can be transformed only into 2
•  » » 10 months ago, # ^ |   0 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.
 » 10 months ago, # |   0 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}}$?
•  » » 10 months ago, # ^ | ← Rev. 2 →   0 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 :)).
•  » » » 10 months ago, # ^ |   0 My code are born with huge constants...So why using $\texttt{random_shuffle}$ could result in correct?
•  » » » » 10 months ago, # ^ |   0 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...
•  » » » » » 10 months ago, # ^ |   0 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.
•  » » » » » » 10 months ago, # ^ |   0 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.
•  » » » » » » » 10 months ago, # ^ |   0 Well, C++11 is allowed in national contest and above, but not the provincial contest.
•  » » » 10 months ago, # ^ |   0 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"?
•  » » » » 10 months ago, # ^ |   0 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.
 » 10 months ago, # |   +33 we always can incriminate this distanceWhat crime should we charge it with?
 » 10 months ago, # |   0 Could anyone can explain the LIS solution to E?
•  » » 10 months ago, # ^ |   +1 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
•  » » » 10 months ago, # ^ |   0 Thanks!The first sentence of your words make me realize the purpose of the quention.
•  » » » » 10 months ago, # ^ |   +4 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
 » 10 months ago, # |   0 Why is the G problem constructed correctly?
 » 10 months ago, # | ← Rev. 3 →   +7 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 rSo we just need to minimize cntl2 — cntl1
•  » » 10 months ago, # ^ |   0 I understand len 1 and len 2 is a constant. but why cntr2 — cntr3 is a constant? :( hard to understand...
•  » » 10 months ago, # ^ |   0 could you help me why there’s no cntm_i in solution code?/
•  » » 10 months ago, # ^ |   0 what is len 1 and len 3?
•  » » » 10 months ago, # ^ |   0 The number of assignments person 1 and person 3 start with
 » 10 months ago, # |   0 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.
•  » » 10 months ago, # ^ |   0 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.
•  » » » 5 months ago, # ^ |   0 Amazing
•  » » 10 months ago, # ^ | ← Rev. 2 →   0 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
 » 10 months ago, # |   0 Is there any flaw with my idea of a solution for G?You construct a Hasse diagram for a poset P such that $a •  » » 10 months ago, # ^ | 0 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?  » 10 months ago, # | 0 can anyone tell me how to solve problem D using DP  » 10 months ago, # | ← Rev. 2 → 0 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. •  » » 10 months ago, # ^ | 0 you may make some mistakes in your code. may you use binary algorithm, In the process，not ues l,but initial l.  » 10 months ago, # | 0 Problem F of last Educational round also uses NTT..  » 10 months ago, # | ← Rev. 2 → 0 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.  » 10 months ago, # | ← Rev. 2 → 0 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!  » 10 months ago, # | 0 Anyone can explain me problem E in brief ? Im not able to understand the tutorial.  » 10 months ago, # | 0 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  » 10 months ago, # | 0 Can anyone tell the heavily optimised brute force of F?  » 10 months ago, # | 0 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  » 10 months ago, # | 0 Awesome contest  » 9 months ago, # | ← Rev. 11 → 0 Awesome contest!  » 9 months ago, # | ← Rev. 2 → 0 Doubt in E.Can anyone explain how " minimizing$cnt_{l, 2} + cnt_{l, 3} + cnt_{m, 1} + cnt_{m, 3} + cnt_{r, 1} + cnt_{r, 2}$is the same as minimizing$cnt_{l, 2} - cnt_{l, 1}$for fixed$r$" ?  » 9 months ago, # | 0 A video tutorial for problem E: https://www.youtube.com/watch?v=i-2hXsCDDg8  » 6 months ago, # | ← Rev. 3 → +3 Shorter solution for problem E Let's indicate with$dp[i][j]$the number of moves required to distribute the first$i$problems satisfying the conditions and, if$i \neq 0$, in such a way that the problem$i$goes to the participant$j$($0 \leq i \leq n$,$1 \leq j \leq 3$). Then$dp[0][j] = 0$for each$j$. For$i$from$1$to$n$,$dp[i][j] = \min_{k \leq j}(dp[i - 1][k])$if the problem$i$was initially given to the participant$j$;$dp[i][j] = \min_{k \leq j}(dp[i - 1][k]) + 1$otherwise. The answer is$\min(dp[n][j])$. Complexity:$O(N)\$ https://codeforces.com/contest/1257/submission/72940420
 » 5 months ago, # |   0 For Problem E- let me divide into three segments l,m,r respectively. Calculate the prefix sum array a,b and c for first,second and third persons respectively where a[i] would denote the number of problems<=i assigned to person a. Let am denote the number of problems given to person a from segment m. Clearly the total cost =am+ar+bl+br+cl+cm. => total cost=k1-a[l]+b[l]+c[l]+br+cm => total cost=k1-a[l]+b[l]+c[l]+k2-b[m]+c[m]-c[l] => total cost=k1+k2+b[l]-a[l]+c[m]-b[m]. Maintain an array min[], where min[i] would denote minimum possible value of c[j]-b[j] for j>=i. Now fixing l from 0 to n,calculate min_cost=k1+k2+b[l]-a[l]+min[l]. Finally print the minimum of min_cost over all ls. 'Hope you find this helpful :).' `