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 cdkrot 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, nuipojaluista, Ivan19981305, lankin.i, Pavlova, Decibit, dmitrii.krasnihin, AlexSap, unreal.eugene.
Scoring distribution: 500 — 1000 — 1250 — 1750 — 2250 — 3000.
Good luck!
Is this the first time that two div 2 contests(607 and 608) will be held at the same day? :O
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.
I think they will not have time to recalculate the rating
recalculated
Will you be sharing the problems of the Olympiad (apart from the 6 that you added for this contest) after the contest is over ?
Hope to see less ad-hocs in this contest
But isn't it better to see more ad hocs, neither than more realizations and case-working etc?
Hope to see less greedy problems in the contest
D was greedy .....what happened???
You can tell me better
...
Delayed 10 minutes
Why?
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.
What was the delay for?
I don't understand why do u mention it here. People anyway get to know themselves.
discussion for fun, why do u complain to it? :3
delay 10m :))
why
greater than 9000 participants. I think so
I think they wanted the number of participants be a little more.something like 10000
The strategy didn't work. They still only have 9025 people registered. Only 27 people have registered in the last 5 minutes.
They got to 9000 though; that's a nice number too.
true true
Thought it was 10 hours.
10 minutes more of being an expert :p
10 minutes more of being a Pupil (* shifting towards newbie)
Same :)
You sure??
delayed :|
it happens when you are just few ratings away from expert
gl hf
delayforces
It feels pretty bad when contest time delayed.
come on it's only ten minutes
Delay strikes after a long time.
delayed 10 min ... another 10 min ...
I hope this is an entertaining contest and 2 hours with very good problems. I want to start !!
Muahhhh, you're going down my son
It took me 22 minutes to solve A,B,C combined and another 22 minutes just to understand problem D.
...
...
I want none of my submissions to be evaluated.
I thought I was doing a virtual contest.
atulyakv
lol
For many contestants:
You solved E though!
was it some sort of a pattern I was able to find some patterns but couldn't connect the dots :/
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.
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.
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?
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.
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 TLE
https://codeforces.net/contest/1271/submission/66964444
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).
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)
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
Why am I feeling that B has weak pretests ?
SAME BRO
How to solve D?
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.
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.
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.
WAS E Binary search as I failed to submit the solution in time
Yes, I did it using binary search
It was
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).
What is that formula? Can you please explain?
Assume that $$$x$$$ lies on the path of $$$A$$$. Then
$ (it can be easily seen by trying to invert the function $$$f$$$). By using induction, we get that
$ If $$$x$$$ is odd, then $$$a_1 > 0$$$, else $$$a_1 \geq 0.$$$ Let's say
$ 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:
$ and if $$$x$$$ is even, then $$$x$$$ is contained in the following number of paths:
$ 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).
what is a1,a2,...at?
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$$$.
Thanks,got it
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:"
Shouldn't it be
Thanks in advanced. <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.$$$
Got it. Thanks so much
That is impressed! But too difficult to understand. Math is hard.
Lol my B is gonna fail . Looks like in going for master to expert in one day
How to solve E? I tried using Binary Search.
I had a pattern-matching closed form
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 rn
Anyways, did anybody else come up with a DP solution to E? I used sort of "improved" memoization. The code became kinda long though.
I tried to use digit dp for E, what dp did you use?
There is no E submitted from your account :)
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 even
else 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)<len(n) we could use combinatorics
The new function I made was working properly, i.e. giving the same answer as my time and memory expensive f(x).
So, now I thought of binary search on x and I got stuck, because I noticed that f(x) values when x is even is about double when x is odd, hence a constantly increasing, monotonic search space wasn't what I was getting...
So, I got stuck, basically its not giving the correct answer at the 1000000 100 test case.
So, thats why I didn't submit. My wrong submission for clarity
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
How did you calculate f(x)?
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.
I think, I was solving at least 3 different versions of the fourth task until I understood right one.
How to solve E , can anyone help me .
Check it out here https://codeforces.net/blog/entry/72164?#comment-564659
How to solve B?
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
Why does it work, and how did you think of it?
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.
I was able to get the parity condition,but i could not implement the solution along with saving the indices.
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.
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.
E:
path(x)
containsy
IFF in binary form eithery
ory ^ 1
is the prefix ofx
.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)$$$.
Math is hard.
What I meant is either
y
ends with1
and is a prefix ofx
or ends with0
and eithery
ory + 1
is a prefix ofx
.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 castle
Then 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 best
Return the sum of all the taken importances.
I tried this, got WA. It could be an implementation error though.
It'r really a whole lot of coding, there are lots of places for errors.
I got AC with almost same approach : submission
Looks really impressive. Though it took you 80 mins in total.
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 castles
It takes somewhere around nlogn, since I were using sets for storing protected castles
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.
Yes, you got it right
Can you please explain me the question? DIscussing solution won't help me unless I am clear about question.
Thanks.
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.
It's DP. dp[index][numWarriors] = optimum value when you are starting from index = index with numWarriors.
Check solution to E here https://codeforces.net/blog/entry/72164?#comment-564659
How to solve C?
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)
how to solve D with DP?
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.
Thanks a lot, so how to transfer ? I can not find the way to use portals
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
Yes, you have explained it well! :)
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.
You could use inbuilt lower_bound and upper_bound functions in C++
In my code it looks fairly simple.
https://codeforces.net/contest/1271/submission/66964757
Edit: Do the long longs overflow somewhere?
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.
Please unlock the solutions.
Pretest for B is too weak...
Why are you signed in as another user?
I received this picture from my teammate.
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.
I thought k == n is in the sample itself!
For some reason it gives output for k == n case when k is small.
You can hack yourself to append you stronger test case to the system test, a good chance to try it.
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.net/contest/1271/submission/66962381
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.
Even I solved it using greedy method. Time complexity O(nlogn).
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.
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
My (tester's) solution of F:
Let'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:
Code: 66966986. I don't know if it was supposed to pass, but it works in 2433 ms.
could've waited for 10 more submissions to get 66966996 :)
Thank you for the solution though
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.
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
Solution 66967994 using simplex method should be correct for 1271F - Divide The Students ?
Very weak tests! In task D there is no test with the answer 0
Why was my submission skipped for no reason?
Can somone suggest some similar problems like D(Portals)
Yes. Please
I think it is similar to 1251E2 - Voting (Hard Version).
Link is here
Actually, the most similar thing between these two problems is "I can't achieve it during the round".
How do we solve
DIV2 B
, if we have tominimize
the number of operations?Do it the greedy way.
Formally
Check if the solution exists and try this for both black and white.
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.
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 + 1
As 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.
Well that was a good contest, had a couple of good problems D and E, which will help many experts upsolve and improve. :D
Can someone please explain how to solve
DIV2 E
. What should I apply binary search over?Ratings are not updated yet. Was this contest rated?
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.
Don't know why my solution is failing on test 4. Can someone please help.
Change your each "else if" to "if", a point can fit 1 or 2 "if" branch.
Got it, thanks. Was a very silly mistake.
Can some one elaborate DP solution for D? What are the states and sub-problems?
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.
Editorial has not been published for the last 3 contests. Will it be published in the near future?
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 !
I am extremely eager for the upcoming editorials! I hope they'll be out soon!
BledDest
Are the editorials still being prepared? It has been more than 2 days since the contest!
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!
The editorial is published. Sorry for the delay.
Can you also publish an update in the announcement blog? People are more used to looking it up there. Thanks.