### BledDest's blog

By BledDest, history, 7 weeks ago, translation, ,

Hello Codeforces!

Codeforces Round #608 (Div. 2) will be held on Dec/15/2019 12:15 (Moscow time). The round will be rated for Div. 2 contestants. There will be 6 problems for 2 hours. Please, notice that the start time is unusual.

The round will be rated for the participants with rating lower than 2100. The statements will be available in Russian and English.

The round coincides with (and is based on) a local Saratov's olympiad for high school students. That's why we ask the participants of the olympiad to stay silent and don't share the statements of the contest with anyone. Unfortunately, we cannot add all the problems to the round, it will contain only six problems.

The problems were proposed and prepared by Alexander fcspartakm Frolov, Adilbek adedalic Dalabaev, Vladimir Vovuh Petrov and me.

We also would like to express our gratitude to Mike MikeMirzayanov Mirzayanov for the permission to make a mirror and Codeforces and Polygon platforms, to our coordinator Dmitry _kun_ Sayutin or his help with testing the problems and preparing the round, and to the team of testers: MrPaul_TUser, Stresshoover, Supermagzzz, artsin666, defolaut, Peinot, PrianishnikovaRina, sladkayaKlubnichka, Ivan19981305, lankin.i, Pavlova, Decibit, dmitrii.krasnihin, AlexSap, unreal.eugene.

Scoring distribution: 500 — 1000 — 1250 — 1750 — 2250 — 3000.

Good luck!

• +155

 » 7 weeks ago, # |   0 Is this the first time that two div 2 contests(607 and 608) will be held at the same day? :O
 » 7 weeks ago, # |   +24 First time to see 2 rounds in one day...I think it's important to make something clear: I successed to register in #608 as official contestant because my rating is 2100- now. If I compete in #607 and become 2100+, will I still be official? If someone with 2100+ rating register in #608 now as unofficial contestant, and he become 2100- after #607, will he automatically become official or not? If rating changes in #607 can make conversion between official and unofficial, will rating update before #608 start? You know, #608 starts only 2 hours after #607 ends.
•  » » 7 weeks ago, # ^ |   0 I think they will not have time to recalculate the rating
•  » » » 6 weeks ago, # ^ |   +2 recalculated
 » 6 weeks ago, # |   0 Will you be sharing the problems of the Olympiad (apart from the 6 that you added for this contest) after the contest is over ?
 » 6 weeks ago, # |   -18 Hope to see less ad-hocs in this contest
•  » » 6 weeks ago, # ^ |   +32 But isn't it better to see more ad hocs, neither than more realizations and case-working etc?
•  » » 6 weeks ago, # ^ |   +1 Hope to see less greedy problems in the contest
•  » » » 6 weeks ago, # ^ |   0 D was greedy .....what happened???
•  » » » » 6 weeks ago, # ^ |   +3 You can tell me better
 » 6 weeks ago, # | ← Rev. 3 →   -59 ...
 » 6 weeks ago, # |   0 Delayed 10 minutes
•  » » 6 weeks ago, # ^ |   -10 Why?
•  » » » 6 weeks ago, # ^ |   +14 The round coincides with (and is based on) a local Saratov's olympiad for high school students. Any delay there will also reflect here. It can be a possible reason.
•  » » 6 weeks ago, # ^ |   -7 What was the delay for?
•  » » 6 weeks ago, # ^ |   0 I don't understand why do u mention it here. People anyway get to know themselves.
•  » » » 6 weeks ago, # ^ |   0 discussion for fun, why do u complain to it? :3
 » 6 weeks ago, # |   -19 delay 10m :))
•  » » 6 weeks ago, # ^ |   -6 why
•  » » » 6 weeks ago, # ^ | ← Rev. 3 →   -27 greater than 9000 participants. I think so
•  » » » 6 weeks ago, # ^ |   -9 I think they wanted the number of participants be a little more.something like 10000
•  » » » » 6 weeks ago, # ^ |   -13 The strategy didn't work. They still only have 9025 people registered. Only 27 people have registered in the last 5 minutes.
•  » » » » » 6 weeks ago, # ^ |   +1 They got to 9000 though; that's a nice number too.
•  » » » » » » 6 weeks ago, # ^ |   +1 true true
•  » » 6 weeks ago, # ^ |   +17 Thought it was 10 hours.
•  » » 6 weeks ago, # ^ |   +15 10 minutes more of being an expert :p
•  » » » 6 weeks ago, # ^ |   +3 10 minutes more of being a Pupil (* shifting towards newbie)
•  » » » 6 weeks ago, # ^ |   0 Same :)
•  » » » 6 weeks ago, # ^ |   +5 You sure??
 » 6 weeks ago, # |   +3 delayed :|
•  » » 6 weeks ago, # ^ |   0 it happens when you are just few ratings away from expert
 » 6 weeks ago, # |   +3 gl hf
 » 6 weeks ago, # |   -13 delayforces
 » 6 weeks ago, # |   -39 It feels pretty bad when contest time delayed.
•  » » 6 weeks ago, # ^ |   +22 come on it's only ten minutes
 » 6 weeks ago, # | ← Rev. 3 →   0 Delay strikes after a long time.
 » 6 weeks ago, # |   -25 delayed 10 min ... another 10 min ...
 » 6 weeks ago, # |   0 I hope this is an entertaining contest and 2 hours with very good problems. I want to start !!
•  » » 6 weeks ago, # ^ |   +2 Muahhhh, you're going down my son
 » 6 weeks ago, # |   +23 It took me 22 minutes to solve A,B,C combined and another 22 minutes just to understand problem D.
 » 6 weeks ago, # | ← Rev. 4 →   -12 ...
•  » » 6 weeks ago, # ^ | ← Rev. 3 →   -7 ...
•  » » » 6 weeks ago, # ^ |   0 I want none of my submissions to be evaluated. Why?I thought I was doing a virtual contest.
•  » » » » 6 weeks ago, # ^ |   0 lol
•  » » » » 6 weeks ago, # ^ |   0
•  » » » » » 6 weeks ago, # ^ |   0 lol
 » 6 weeks ago, # |   0 what is pretest 13 for D?
 » 6 weeks ago, # | ← Rev. 2 →   +30 For many contestants:
•  » » 6 weeks ago, # ^ |   0 You solved E though!was it some sort of a pattern I was able to find some patterns but couldn't connect the dots :/
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   +21 I used two binary searches: one for odd values, one for even values. I took the maximum value among the binary search results. To determine if a certain value appears in at least K sequences, we can use an O(log N) validation. Suppose our current mid-point value in the binary search is called v. We will iteratively extend the range of possible values of x in F(x) that will have v in their sequence. If v is odd, then this set will be {[v, v], [2 * v, 2 * v + 1], [2 * (2 * v), 2 * (2 * v + 1) + 1], ..., [2 * prevLowerBound, 2 * prevUpperBound + 1]} until the upper bound is <= n. If v is even the set will be {[v, v + 1], [2 * v, 2 * (v + 1) + 1], [2 * (2 * v), 2 * (2 * (v + 1) + 1) + 1], ..., [2 * prevLowerBound, 2 * prevUpperBound + 1]}. If the size of the set is >= k, the mid-point is possible, and we will try a greater value.
•  » » » » 6 weeks ago, # ^ |   +14 Not that it changes much but that formula has a nice graphic interpretation as following:Suppose you build a binary heap with number 1, 2, ..., N ( A binary tree with node u having 2*u and 2*u + 1 as it's childs ). Then the occurrence of v is Subtree size of v if v is odd, and Sum of subtree size of v and v + 1 if v is even.
•  » » » » 6 weeks ago, # ^ |   0 How can we calculate k using lower bound and upper bound?
•  » » » » 6 weeks ago, # ^ |   0 If you don't mind can you elaborate that checking for k occurence part(I understood the bin search),say n=11 and k=3,how to find if number 5 has 3 occurences?
•  » » » » » 6 weeks ago, # ^ |   +1 The first range of values for x in f(x) that will have 5 in their sequence is [5,5] ([v, v], because 5 is odd). Then we will calculate the next range: [2 * 5, 2 * 5 + 1] = [10, 11]. Then the next range is [2 * 10, 2 * 10 + 1] = [20, 23]. We now detect the upperbound is out of range (> n) and we add all x's in this range that are <= n to our counter, which are 0 in this case. So 5 has a total of three occurences. Notice that when any x in a range is divided by 2 it is able to reach some x in the preceding range of x's. So it will always be able to reach our starting value.
•  » » » » » » 6 weeks ago, # ^ | ← Rev. 3 →   0 Thanks for replying,but if n is very large say 1e18 and k is also large and we want to find f(5),won't there be large no of iterations?because we have to generate k numbers?I tried something similar here and got TLEhttps://codeforces.com/contest/1271/submission/66964444
•  » » » » » » » 6 weeks ago, # ^ | ← Rev. 6 →   0 We will not because we always multiply the lowerbound and upperbound by 2. This means we can only multiply a maximum of log_2(1e18) times by 2 until we reach 1e18. The trick is to use a lowerbound an d upperbound of possible ranges of x to count all numbers in between these bounds, so we don't have to iterate over all these values individually. So this will be only O(log(N)). So the final complexity is O(log(N)^2). You can check my submission for the implementation of this approach. The reason for TLE in your code is that you also call f(x + 1), which makes the function >= O(N).
•  » » » » 6 weeks ago, # ^ |   0 Well, I use a weird method: We first calculate the path of n and store it in one list, then for every even number x in path(n), add x-2 to another list. And a weird but true statement is that the answer will only occur in the two lists. Since the size is O(log n) and checking can be done in O(log n), This solution is O(log^2 n)
•  » » » 6 weeks ago, # ^ |   +7 It could be solved using binary search as well as by observing pattern although I solved it using Pattern.Pattern:For K of the form $2^p-1$ then for $n>=k$ series will be : {1},{2,2,...upto K times},{3},{4,4,...upto k times},{5},{6,6...}... and so on.For K of any other form, find maximum p such that $2^p-1$ < K and let newK = $2^p$. For above kind, the series will be($n>=k$) : {1},{2,2,....upto newK times},{4,4,...upto newK times},{6,6,...upto newK times}....and so on.Code : 66962250
 » 6 weeks ago, # |   +8 Why am I feeling that B has weak pretests ?
•  » » 6 weeks ago, # ^ |   0 SAME BRO
 » 6 weeks ago, # |   0 How to solve D?
•  » » 6 weeks ago, # ^ |   0 How to handle the portals part ?Was not able to think that whether we have to move from u to v or vice-versa.Nice problem anyways.
•  » » 6 weeks ago, # ^ |   +19 It is always optimal to defend castle as late as possible. Do dp on what is the maximal sum of importance values if you are in castle i and have j warriors.
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 It is always better to defend a castle as late as possible. There will be DP[position][count of warriors]. So, while going to the next state, you assign some warriors to defend castles. Here, it's obvious that you want to defend castles with maximum importance whether you want to defend the current castle or previous castle(s) by portals.
 » 6 weeks ago, # |   +3 WAS E Binary search as I failed to submit the solution in time
•  » » 6 weeks ago, # ^ |   0 Yes, I did it using binary search
•  » » 6 weeks ago, # ^ |   0 It was
•  » » 6 weeks ago, # ^ |   0 Actually, you can compute the exact formula for the number of paths on which particular x lies (it quite depends on the parity of x). Then, using this formula, you find the maximal odd x1 and the maximal even x2 for which the numbers of paths are at least k and output the maximal number among x1, x2, and 1 (because 1 is a corner case for the formula).
•  » » » 6 weeks ago, # ^ |   0 What is that formula? Can you please explain?
•  » » » » 6 weeks ago, # ^ | ← Rev. 3 →   +9 Assume that $x$ lies on the path of $A$. Then $A = 2^{a_t} \cdot (2^{a_{t-1}} \cdot (...(2^{a_1} \cdot x + 1)...) + 1) + (0$ or $1)$$(it can be easily seen by trying to invert the function $f$). By using induction, we get that $A = 2^{a_t + ... + a_1} \cdot x + 2^{a_t + ... + a_2} + ... + 2^{a_t} + (0$ or $1).$$ If $x$ is odd, then $a_1 > 0$, else $a_1 \geq 0.$ Let's say $y = 2^{a_t + ... + a_2} + ... + 2^{a_t} + (0$ or $1).$$Then, obviously, if $x$ is odd and greater than $1$, $x$ lies on the path of every number of the form $2^a \cdot x + y$, for $0 \leq y \leq 2^a - 1$, and if $x$ is even, then $x$ lies on the path of every number of the form $2^a \cdot x + y$, for $0 \leq y \leq 2^{a+1} - 1$. Now, let's fix $a$ (the power of two) and count the number of numbers of such form. For odd $x$ there are $2^a$ such numbers and for even $x$ there are $2^{a+1}$ such numbers. Assume that $A$ is the largest number of such form that is not greater than $n$ ($n \geq A = 2^a \cdot x + y$). Then if $x$ is odd, then x is contained in the following number of different paths: $2^0 + 2^1 + ... + 2^{a-1} + y + 1 = 2^a + y,$$ and if $x$ is even, then $x$ is contained in the following number of paths: $2^1 + 2^2 + ... + 2^a + y + 1 = 2^{a+1} + y - 1.$\$ We also know that $n \geq 2^a \cdot x + y$. Intuitively, we want to maximize $x$, so we have to minimize the number of paths that contain $x$, so we have to make it the least possible value that is not less than $k$. One can easily see that for odd $x$ we can make $2^a + y = k$, and for even x we can make $2^{a+1} + y - 1 = k$ and the values of $a$ and $y$ will be uniquely determined. Thus, $x$ will be the largest number of respective parity that is not greater than $(n - y) / 2^a$ (from the maximality of $A = 2^a \cdot x + y$). Now, how to compute the answer: let $a = [log_2(k)]$. For odd $x$ we let $y = k - 2^a,$ then $x = (n - y)/2^a$ (if $x$ will be even, decrease $x$ by one). For even $x$, if $k < 2^{a+2} - 1$, then $a := a-1$; let $y = k - 2^{a+1} + 1$, then $x = (n - y)/2^a$ (if x will be odd, decrease $x$ by one).
•  » » » » » 6 weeks ago, # ^ |   0 what is a1,a2,...at?
•  » » » » » » 6 weeks ago, # ^ | ← Rev. 2 →   +1 They are just some almost random non-negative integers. $a_2, ... ,a_t$ should be positive and the restriction on $a_1$ is already mentioned. Now I'll try to show how to get that form of $A$. Let's inverse $f:$ Assume $x$ lies on some integer $A$'s path. If $x$ is odd, then there must have been $2 \cdot x$ before $x$. If $x$ is even, then there could be both $2 \cdot x$ or $x + 1$ before $x$. Suppose we multiplied $x$ by two $a_1$ times and then added $1$ and got $2^{a_1} \cdot x + 1$, then we multiplied the resulting $x$ by $2$ another $a_2$ times and got $2^{a_2} \cdot (2^{a_1} \cdot x + 1) + 1$. By continuing this process until we reach $A$, we will get the representation of $A$ through $x$ and $a_1, ... ,a_t$.
•  » » » » » » » 6 weeks ago, # ^ |   0 Thanks,got it
•  » » » » » 6 weeks ago, # ^ |   0 I have this question ^^.If $x$ is odd then $a_1 > 0$, then $a_t + ... + a_1 > 0$ "If $x$ is odd and greater than 1, $x$ lies on the path of every number of the form $2^{a}⋅x+y$" => So can $a$ is 0?"Then if $x$ is odd, then $x$ is contained in the following number of different paths:" $2^{0}+2^{1}+...+2^{a−1}+y+1=2^{a}+y$Shouldn't it be $2^{1}+...+2^{a−1}+y+1=2^{a}+y-1$Thanks in advanced. <3
•  » » » » » » 6 weeks ago, # ^ |   +3 I am sorry, I didn't mention the case when $a = 0$. Actually it can be $0.$ When $a$ is $0$, we get that $y \leq 2^0 - 1 = 0$ and the path of such $A = 2^0 \cdot x + 0$ containes $x$, so we also have to consider the case when $a = 0.$ In that representation of $A$, I considered only $A > x$, but the number of different paths is computed correctly with the consideration of the case $a=0.$
•  » » » » » » » 6 weeks ago, # ^ |   0 Got it. Thanks so much
•  » » » » » 6 weeks ago, # ^ |   0 That is impressed! But too difficult to understand. Math is hard.
 » 6 weeks ago, # |   +25 Lol my B is gonna fail . Looks like in going for master to expert in one day
 » 6 weeks ago, # |   0 How to solve E? I tried using Binary Search.
•  » » 6 weeks ago, # ^ | ← Rev. 3 →   +4 I had a pattern-matching closed form a, b = input().split() a = int(a) b = int(b) if b == 1: print(a) else: chopped_even = bin(b+1)[3:] len_even = len(chopped_even) best_even = ((a-int(chopped_even, 2))//(2**len_even))*2 chopped_odd = bin(b)[2:] len_odd = len(chopped_odd) best_odd = ((a - b) // (2**len_odd))*2 + 1 print(best_even if best_even > best_odd else best_odd) 
•  » » 6 weeks ago, # ^ | ← Rev. 3 →   0 I came up with a DP approach to problem E but I missed submitting it by a few seconds :( I wanted to become cyan but I guess, next time :"-( I am so sad rnAnyways, did anybody else come up with a DP solution to E? I used sort of "improved" memoization. The code became kinda long though.
•  » » » 6 weeks ago, # ^ |   0 I tried to use digit dp for E, what dp did you use?
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   +6 There is no E submitted from your account :)
•  » » » » 6 weeks ago, # ^ | ← Rev. 3 →   +3 I didn't submit because what I wrote wasn't working correctly.Basically, I wanted to calculate f(x) = number of elements in whose path, x came. so, dp[x] = dp[2x] + dp[x+1] + 1 if x is evenelse if x is odd, dp[x] = 1 + dp[2x]but this function was taking a huge amount of time AND memory, hence I tried to compute the same thing, which this function is doing, but used digit dp my digit dp compared two numbers n and x and output in how many ways can I add digits to the right of x to make its length = length of n and still maintain x<=n. Actually, the number of numbers, in whose path x comes will just be the number of ways we can append 1 or 0 to the right of x such that len(x)<=len(n) && x<=n so the len(x) = len(n) part was handled by the digit dp and when len(x)
•  » » 6 weeks ago, # ^ | ← Rev. 3 →   +22 Suppose we have function — f(x) that gives number of paths with x inside. I just checked some values if f(n, x) >= k. What values? I dk why it works it but seems that enough to check x + dif, x — dif, where dif >= 0 and dif <= 3, and x — is prefix of binary representation of n. Submission for details
•  » » » 6 weeks ago, # ^ |   0 How did you calculate f(x)?
•  » » » » 6 weeks ago, # ^ |   +13 If you can compute the function $g(x)$ which denotes the number of integers up to $n$ that start with the binary representation of $x$, then $f(x) = g(x)$ for odd $x$ and $f(x) + f(x+1)$ for even $x$ by "retracing" the steps of $f$. $g$ is easily computed, you can look at my submission for example.
 » 6 weeks ago, # |   +22 I think, I was solving at least 3 different versions of the fourth task until I understood right one.
 » 6 weeks ago, # |   -8 How to solve E , can anyone help me .
•  » » 6 weeks ago, # ^ |   0 Check it out here https://codeforces.com/blog/entry/72164?#comment-564659
 » 6 weeks ago, # |   0 How to solve B?
•  » » 6 weeks ago, # ^ |   +2 1-the answer exists if all elements are equal to "B" or "W" 2-(For every element equal B) start from the first index of the array and if the current element is w make it b and change the adjacent element too.If it's w don't touch it make i++.make the process until to the end of the string.At the end check whether all elements are equal to B or not. 3-do the same thing for W
•  » » » 6 weeks ago, # ^ |   +3 Why does it work, and how did you think of it?
•  » » 6 weeks ago, # ^ |   +3 Notice that the parity of the number of $W$'s and $B$'s doesn't change with each operation. Hence, if there are an odd number of $W$'s and $B$'s, it's impossible.Now, w.l.o.g, let's assume that the number of $W$'s are even. We shall try to remove all the $W$'s. Switching $WB$ makes it $BW$. This 'shifts' $W$ to the right. Let $w_i$ be the index of the $i^{th}\ \ W$ in the string. For each odd $i$ perform operations $w_i\dots w_{i+1}-1$.Doing so 'shifts' the odd $W$'s to the even ones and removes them both.
•  » » » 6 weeks ago, # ^ |   0 I was able to get the parity condition,but i could not implement the solution along with saving the indices.
•  » » » » 6 weeks ago, # ^ |   0 First consider how many B's (suppose m) and W's (suppose n) are in the given string. Secondly, observe that doing any operation, either the number of B's become m-2 and number of W's become n+2 or the other way round. Another possibility is the number of B's and W's will not change. This happens when you swap B W -> W B. Thus, we can conclude that either the number of B must be even or the number of W must be even or both.After that, i just iterate through the string and swap accordingly. I declare another variable to count the swap and put the index into an array. Hopefully it helps.
 » 6 weeks ago, # |   0 Can someone explain Question D? D has very unclear statement.Any hints to Solve E? I was able to form a fibonacci sequence at each level, but The I couldn't proceed further.Thanks.
•  » » 6 weeks ago, # ^ |   0 E: path(x) contains y IFF in binary form either y or y ^ 1 is the prefix of x.
•  » » » 6 weeks ago, # ^ |   0 Why? If $x$ is $10101$ and $y$ is $1011$, $y \oplus 1 = 1010$ is a prefix of $x$ but $y$ is not contained in $path(x)$.
•  » » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 Math is hard.What I meant is either y ends with 1 and is a prefix of x or ends with 0 and either y or y + 1 is a prefix of x.
•  » » 6 weeks ago, # ^ |   +3 My (unimplemented) idea:Let's count the max number of soldiers we can leave at each castle. The values will always increase. (Can be done in linear time) Suppose we have 0, 1, 1, 3, 5, 5.From the sequence we can see that we can - leave 2 people in any of 5th or 6th castle - leave 2 people in any of 4th-6th castle - leave 1 person in any of 1th-6th castleThen let's have a priority queue pq with the importances of the castles. - Add to pq the importances of the 5th and 6th castles + all the castles accessible from these two via portals. Take 2 best from the queue - Add the 4th castle (+ accessible from it via portals), take 2 best from the queue - add the 2nd and the 3rd (+ accessible from those), take 1 bestReturn the sum of all the taken importances.
•  » » » 6 weeks ago, # ^ |   0 I tried this, got WA. It could be an implementation error though.
•  » » » » 6 weeks ago, # ^ |   0 It'r really a whole lot of coding, there are lots of places for errors.
•  » » » » » 6 weeks ago, # ^ |   0 I got AC with almost same approach : submission
•  » » » » » » 6 weeks ago, # ^ |   0 Looks really impressive. Though it took you 80 mins in total.
•  » » » 6 weeks ago, # ^ |   +5 There is no need to place more than one soldier for defence.My implementation was just the optimal strategy: 1) defend castles as late, as possible 2) when you don't have enough strength, get rid of the least valuable castlesIt takes somewhere around nlogn, since I were using sets for storing protected castles
•  » » » » 6 weeks ago, # ^ |   0 There is, if all are placed in different castles.What is as late as possible in your strategy? If I'm at the 3rd castle, and there is a portal from the 7th to the 3rd I don't protect the 3rd, but if it's my last chance to protect the 3rd castle then I do? That may work indeed.
•  » » » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 Yes, you got it right
•  » » » 6 weeks ago, # ^ |   0 Can you please explain me the question? DIscussing solution won't help me unless I am clear about question.Thanks.
•  » » » » 6 weeks ago, # ^ |   0 Q: Given n castles. You have to destroy all the castles. Each castle needs a[i] warriors to destroy it. After destroying castle you will get extra b[i] warriors. Initially, you have k warriors to start with. You have to destroy the castles sequentially. (1,2,3..n) Now you have given some relations. Ex-(u->v) which means you can send warrior from uth castle to vth castle. To defend the castle you need at least 1 warrior. But you can defend the castle either when you were at that particular castle or the relations you have. And the relation can be applied when you were present at that particular castle. Ex-(3->1) you can only send warrior from 3rd castle when you have destroyed 3rd castle. And each castle has c[i] importance value. You have to maximize the sum of importance value of defended castles.
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 It's DP. dp[index][numWarriors] = optimum value when you are starting from index = index with numWarriors.
•  » » 6 weeks ago, # ^ |   0 Check solution to E here https://codeforces.com/blog/entry/72164?#comment-564659
 » 6 weeks ago, # |   +1 How to solve C?
•  » » 6 weeks ago, # ^ |   +5 when the schools place is (x,y) the place for the tent must be (x+1,y) or (x,y-1) or (x-1,y) or (x,y+1)
 » 6 weeks ago, # |   0 how to solve D with DP?
•  » » 6 weeks ago, # ^ |   +1 It is always better to defend a castle as late as possible. There will be DP[position][count of warriors]. So, while going to the next state, you assign some warriors to defend castles. Here, it's obvious that you want to defend castles with maximum importance whether you want to defend the current castle or previous castle(s) by portals.
•  » » » 6 weeks ago, # ^ |   0 Thanks a lot, so how to transfer ? I can not find the way to use portals
•  » » » » 6 weeks ago, # ^ | ← Rev. 3 →   0 I miss understood the problem statement damnit. ( I thought to defend a node, Defends all neighbouring nodes so I was like ooof)You can always store the last U that can reach V for every V then make a graph out of these edges only and sort the edges for each node V according to the score descendingly Then it is just basic DP
•  » » » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 Yes, you have explained it well! :)
 » 6 weeks ago, # |   -8 This did not went well. I got some bug in C, was not able to find it, assume it is a sign error while fiddling with the quadrants.For E something similar, causing Test16 to timeout, I assume an endless loop in the binary search.Test output will show what's wrong. :/D was stupid problem statement, did not try it at all. There is no fun is such lengthy text multi-detail problems.
•  » » 6 weeks ago, # ^ |   0 You could use inbuilt lower_bound and upper_bound functions in C++
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 In my code it looks fairly simple.https://codeforces.com/contest/1271/submission/66964757Edit: Do the long longs overflow somewhere?
•  » » 6 weeks ago, # ^ |   0 Turned out in C I had the quadrants wrong. Not wrong implemented, but the wrong idea about how they are constructed.In E it is no endless loop, my implementation is simply that slow :/And i missed the case to check both colors in B. Rip rating, I am doing something wrong.
 » 6 weeks ago, # |   +5 Please unlock the solutions.
 » 6 weeks ago, # | ← Rev. 2 →   +135
 » 6 weeks ago, # | ← Rev. 2 →   +11 Pretest for B is too weak...
•  » » 6 weeks ago, # ^ |   +11 Why are you signed in as another user?
•  » » » 6 weeks ago, # ^ |   +6 I received this picture from my teammate.
 » 6 weeks ago, # |   -24 E has weak sys tests. I forgot to add case when k == n. It goes to an infinite loop for that case. Still it passed sys tests.
•  » » 6 weeks ago, # ^ |   +27 I thought k == n is in the sample itself!
•  » » » 6 weeks ago, # ^ |   -16 For some reason it gives output for k == n case when k is small.
•  » » » » 6 weeks ago, # ^ |   +9 You can hack yourself to append you stronger test case to the system test, a good chance to try it.
 » 6 weeks ago, # |   +22 After reading some of the comments about problem D and DP solutions, I was wondering if anyone else thought of a Greedy Solution? It was AC with potentially O(NlogN) time complexity.First, we greedily leave behind as many soldiers in each castle as we can. This means that we bring along only as many soldiers as we need to clear the rest of the castles. This is because if we want more in later castles, we can just push them over (in actual fact, this means that we choose to bring more soldiers that needed).Similarly, for any castle V, only the furthest portal that can go to V matters. If we wanted to send a soldier to V from an earlier castle, we could just push it forwards and send it back later.Now, we process from castle 1 to castle N. Let U be the current castle and S be the number of soldiers we have at the current castle. We consider all the castles whose furthest portal is from U, and sort them in decreasing importance. While S > 0, we can greedily choose the best castle to take among these castles and subtract 1 from S. If S = 0, we can replace one the castles we have taken previously with another castle, if the importance of the castle we are considering is greater than the importance of another castle we have taken previously. (Replacing here means that instead of sending the soldier at an earlier castle, we bring him forwards to U and send him to another castle) After greedily replacing, if S is still not 0, we push any remaining soldiers to the next castle.Can anyone find a flaw in my algorithm?My submission: https://codeforces.com/contest/1271/submission/66962381
•  » » 6 weeks ago, # ^ |   0 Nice solution, i thought it firstly too(before i decided that it needs dp). However i missed the fact that only furthest portal is matter. Thank you for your detailed comment.
•  » » 6 weeks ago, # ^ |   0 Even I solved it using greedy method. Time complexity O(nlogn). Solution#include using namespace std; #define ll long long #define ld long double #define endl "\n" #define dbg(x) cout << #x << " = " << (x) << endl; const ll MOD = 1000000007; const ll INF = 0x7fffffffffffffff; void input() { #ifndef ONLINE_JUDGE freopen("F:\\Scripts\\input","r",stdin); freopen("F:\\Scripts\\output","w",stdout); #endif } template void print(T v, int l = 0, int r = 5){ for(int i = l;i < r;i++) cout << v[i] << " "; cout << endl; } const int M = 5005; int n, m, k; int a[M]; int b[M]; int c[M]; int road[M]; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); input(); cin >> n >> m >> k; for(int i = 0; i < n; ++i) cin >> a[i] >> b[i] >> c[i]; vector> g(M); int v[M] = {0}; for(int i = 0; i < m; ++i) { int u, v; cin >> u >> v; u--; v--; road[v] = max(road[v], u); } for(int i = 0; i < n; ++i) if (road[i]) g[road[i]].push_back(i); for(int i = 0; i < n; ++i) { sort(g[i].begin(), g[i].end(), [&](int a, int b) { return c[a] > c[b]; }); } priority_queue>, greater>> pq; int ans = 0; for(int i = 0; i < n; ++i) { while (k < a[i] and !pq.empty()) { k += 1; auto x = pq.top(); ans -= x.first; v[x.second] = 0; pq.pop(); } if (k < a[i]) return cout << -1 << endl, 0; k += b[i]; if (!road[i]) { k -= 1; v[i] = 1; ans += c[i]; pq.push({c[i], i}); } for(auto j: g[i]) { if (v[j]) continue; if (k) { v[j] = 1; ans += c[j]; pq.push({c[j], j}); k -= 1; } } } cout << ans << endl; } 
 » 6 weeks ago, # | ← Rev. 2 →   0 DELETED
 » 6 weeks ago, # |   0 Am I correct in saying that F was a flow problem? I got the idea in the last 10-15 minutes, which didn't leave enough time for implementation.
•  » » 6 weeks ago, # ^ |   0 I thought about that for a while at the end of the contest, but I don't know how to send flow through the students which attend three or two classes, I solved it using simplex method but didn't have enough time for implemented it in the contest
 » 6 weeks ago, # |   +13 My (tester's) solution of F: SpoilerLet's define $x = f_1 + f_2 + f_3 + f_4$, $y = f_1 + f_2 + f_5 + f_6$, $z = f_1 + f_3 + f_5 + f_7$ ($f_i$ is number of students of i-th type), where $x$ is number of students in the first subgroup attending maths classes, $y$ — attending programming classes, and $z$ — attending P.E. We know capacities $a_1$, $b_1$, $c_1$ of auditoriums of the first subgroup, so $x \leq a_1$, $y \leq b_1$, $z \leq c_1$. We can define $x_2$, $y_2$, $z_2$ in similar way for students in the second subgroup. There are $d_i$ number of students of i-th type, so $x_2 = (d_1 + d_2 + d_3 + d_4) - (f_1 + f_2 + f_3 + f_4)$, $y_2 = (d_1 + d_2 + d_5 + d_6) - (f_1 + f_2 + f_5 + f_6)$, $z_2 = (d_1 + d_3 + d_5 + d_7) - (f_1 + f_3 + f_5 + f_7)$. We know capacities $a_2$, $b_2$, $c_2$ of auditoriums of the second subgroup, so $x_2 \leq a_2$, $y_2 \leq b_2$, $z_2 \leq c_2$, therefore $x \geq d_1 + d_2 + d_3 + d_4 - a_2$, $y \geq d_1 + d_2 + d_5 + d_6 - b_2$, $z \geq d_1 + d_3 + d_5 + d_7 - c_2$. Thus we know lower and upper bounds of $f_i$ and $x$, $y$, $z$ (let's define lower bounds of $x$, $y$, $z$ as $x_L$, $y_L$, $z_L$ and upper bounds as $x_R$, $y_R$, $z_R$).Note that $f_1$ appears in $x$, $y$, $z$; and $f_4$ only in $x$, $f_6$ only in $y$, $f_7$ only in $z$, so it's possible to find them using $f_2$, $f_3$, $f_5$.So the solution is: Find $x_L$, $y_L$, $z_L$, $x_R$, $y_R$, $z_R$; Check that $x_L \leq x_R$, $y_L \leq y_R$, $z_L \leq z_R$; if not, than solution doesn't exist; Iterate over all possible $f_2$, $f_3$, $f_5$, such that $f_2 + f_3 \leq x_R$, $f_2 + f_5 \leq y_R$ and $f_3 + f_5 \leq z_R$. Now find $f_1$: it is minimum of $x_R - x$, $y_R - y$, $z_R - z$ and $d_1$, i.e. minimum value that we can add to $x$, $y$, $z$ simultaneously. Then find $f_4$: it is minimum of $x_R - x$ and $d_4$; also find $f_6$ and $f_7$ in the same way. Now calculate $x$, $y$, $z$. If $x \geq x_L$, $y \geq y_L$, $z \geq z_L$, then we found solution. If we didn't find solution after iterating over all $f_2$, $f_3$, $f_5$, then it doesn't exist. Code: 66966986. I don't know if it was supposed to pass, but it works in 2433 ms.
•  » » 6 weeks ago, # ^ |   +15 could've waited for 10 more submissions to get 66966996 :)Thank you for the solution though
•  » » 6 weeks ago, # ^ |   +5 It is almost the same as model solution, so it is allowed to pass (model solution is $O(M^3)$ with very low constant, that's why the TL is so high).In fact, I didn't know how to solve this problem faster before I saw some submissions with quadratic complexity.
•  » » » 6 weeks ago, # ^ |   0 On the contest I thought about some recursive bruteforce solution, but I wasn't able to implement it in time. After contest I finished my solution and it passed in 31ms, 66974278
 » 6 weeks ago, # |   +5 Solution 66967994 using simplex method should be correct for 1271F - Divide The Students ?
 » 6 weeks ago, # |   +10 Very weak tests! In task D there is no test with the answer 0
 » 6 weeks ago, # |   0 Why was my submission skipped for no reason?
 » 6 weeks ago, # |   +3 Can somone suggest some similar problems like D(Portals)
•  » » 6 weeks ago, # ^ |   0 Yes. Please
•  » » 6 weeks ago, # ^ |   +3 I think it is similar to 1251E2 - Voting (Hard Version). Link is hereActually, the most similar thing between these two problems is "I can't achieve it during the round".
 » 6 weeks ago, # |   +1 How do we solve DIV2 B, if we have to minimize the number of operations?
•  » » 6 weeks ago, # ^ | ← Rev. 3 →   +6 Do it the greedy way. Formally while (have black blocks) { ix = first black block; block[ix] = white; block[ix + 1] = !block[ix + 1]; } Check if the solution exists and try this for both black and white.
 » 6 weeks ago, # |   0 I couldn't solve E during contest although I was thinking somewhat similar binary search approach but wasn't able to connect the dots. Now, I managed to solved it, Can anyone tell other similar problems ?? Also, please suggest how to improve myself during contest.. Thanks.
•  » » 6 weeks ago, # ^ |   +18 That problem has 2 points: - figure out that the binary search will work - get the idea that you should check only even numbers and max even answer + 1As for the first, there are some problems which are solved by binary search, but once you know it the problem is no more challenging.The second part is unique, just a question of practice and attention to details.About improving yourself — first of all, what exactly is bad during the contest? Once you know the exact problem, you can start working on it.
 » 6 weeks ago, # |   +7 Well that was a good contest, had a couple of good problems D and E, which will help many experts upsolve and improve. :D
 » 6 weeks ago, # |   0 Can someone please explain how to solve DIV2 E. What should I apply binary search over?
 » 6 weeks ago, # |   0 Ratings are not updated yet. Was this contest rated?
 » 6 weeks ago, # |   -28 Greedyforce! Problem A,B,C and D are all greedy! Because I am a noble man, I don't like greed.This is the reason why I failed in this round.
 » 6 weeks ago, # |   0 Don't know why my solution is failing on test 4. Can someone please help.
•  » » 6 weeks ago, # ^ |   +11 Change your each "else if" to "if", a point can fit 1 or 2 "if" branch.
•  » » » 6 weeks ago, # ^ |   +8 Got it, thanks. Was a very silly mistake.
 » 6 weeks ago, # |   0 Can some one elaborate DP solution for D? What are the states and sub-problems?
•  » » 6 weeks ago, # ^ |   +3 The dp state is how many castles we passed and how many warriors remained, $dp[5000][5000]$, where $dp[i][j]$ is the maximum sum of importance values of castles that we are already defending. Interestingly enough, we do not need all those portals in the input. For a castle $v$, we need only the rightmost portal (since postponing the defense definitely won't cause us any harm). So, we are left with $5000$ portals, and no two of them lead to the same castle. BTW, it is convenient to interpret leaving a warrior in the current castle as a portal from $v$ to itself.Transitioning between states is not really difficult. First, we copy all values from $dp[i - 1][]$ to $dp[i][]$ with an offset $+b_i$ — that is how many warriors we gain when capturing castle $i$. Note that we should omit copying some states $dp[i - 1][j]$, where $j < a_i$, since by definition we can't continue with such an army.Then, $dp[i][j] = max(dp[i][j + k] +$ sum of $k$ portals w/ largest importance at castle $i$ over all possible $k$, $dp[i][j])$. Note that you should go bottom-up in respect to $j$ in order to avoid errors.Asymptotic complexity is $O(n \cdot m)$, where $m$ is $5000$ — the maximum possible number of warriors in our army: $n \cdot m + (m \cdot p_1 + m \cdot p_2 + ... + m \cdot p_n) = n \cdot m + m \cdot (p_1 + p_2 + ... + p_n) = n \cdot m + m \cdot n = O(n \cdot m)$, where $p_i$ denotes the number of portals in the $i$-th castle.
 » 6 weeks ago, # |   0 Editorial has not been published for the last 3 contests. Will it be published in the near future?
 » 6 weeks ago, # |   +6 I submit my code of problem D just now and get accepetd. However, my code don't consider the condition that I may fail to attack the first castle at all !
 » 6 weeks ago, # |   +17 I am extremely eager for the upcoming editorials! I hope they'll be out soon!
•  » » 6 weeks ago, # ^ |   0 Are the editorials still being prepared? It has been more than 2 days since the contest!
 » 6 weeks ago, # |   +3 Very good contest! I like E very much. D is a good greedy problem too albeit the very long problem statement.Also I finally became purple, thank you so much!
 » 6 weeks ago, # |   +15 The editorial is published. Sorry for the delay.
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 Can you also publish an update in the announcement blog? People are more used to looking it up there. Thanks.