BledDest's blog

By BledDest, history, 5 years ago, translation, In English

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!

  • Vote: I like it
  • +155
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is this the first time that two div 2 contests(607 and 608) will be held at the same day? :O

»
5 years ago, # |
  Vote: I like it +24 Vote: I do not like it

First time to see 2 rounds in one day...I think it's important to make something clear:

  1. 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?

  2. 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?

  3. 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.

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

Will you be sharing the problems of the Olympiad (apart from the 6 that you added for this contest) after the contest is over ?

»
5 years ago, # |
  Vote: I like it -18 Vote: I do not like it

Hope to see less ad-hocs in this contest

»
5 years ago, # |
Rev. 3   Vote: I like it -59 Vote: I do not like it

...

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

Delayed 10 minutes

  • »
    »
    5 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    Why?

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

      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.

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

    What was the delay for?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't understand why do u mention it here. People anyway get to know themselves.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      discussion for fun, why do u complain to it? :3

»
5 years ago, # |
  Vote: I like it -19 Vote: I do not like it

delay 10m :))

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

delayed :|

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

gl hf

»
5 years ago, # |
  Vote: I like it -13 Vote: I do not like it

delayforces

»
5 years ago, # |
  Vote: I like it -39 Vote: I do not like it

It feels pretty bad when contest time delayed.

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

    come on it's only ten minutes

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

Delay strikes after a long time.

»
5 years ago, # |
  Vote: I like it -25 Vote: I do not like it

delayed 10 min ... another 10 min ...

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

I hope this is an entertaining contest and 2 hours with very good problems. I want to start !!

»
5 years ago, # |
  Vote: I like it +23 Vote: I do not like it

It took me 22 minutes to solve A,B,C combined and another 22 minutes just to understand problem D.

»
5 years ago, # |
Rev. 4   Vote: I like it -12 Vote: I do not like it

...

»
5 years ago, # |
Rev. 2   Vote: I like it +30 Vote: I do not like it

For many contestants:

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You solved E though!

    was it some sort of a pattern I was able to find some patterns but couldn't connect the dots :/

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it +21 Vote: I do not like it

      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.

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

        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

        1. Subtree size of v if v is odd, and

        2. Sum of subtree size of v and v + 1 if v is even.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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?

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

          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.

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

            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://mirror.codeforces.com/contest/1271/submission/66964444

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

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

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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)

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

      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

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Why am I feeling that B has weak pretests ?

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

How to solve D?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

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

    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.

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

    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.

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

WAS E Binary search as I failed to submit the solution in time

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, I did it using binary search

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It was

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What is that formula? Can you please explain?

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 3   Vote: I like it +9 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          what is a1,a2,...at?

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
            Rev. 2   Vote: I like it +1 Vote: I do not like it

            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$$$.

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like 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:"

          $$$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

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

            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.$$$

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          That is impressed! But too difficult to understand. Math is hard.

»
5 years ago, # |
  Vote: I like it +25 Vote: I do not like it

Lol my B is gonna fail . Looks like in going for master to expert in one day

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

How to solve E? I tried using Binary Search.

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it +4 Vote: I do not like it

    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)
    
    
  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I tried to use digit dp for E, what dp did you use?

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it +6 Vote: I do not like it

      There is no E submitted from your account :)

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 3   Vote: I like it +3 Vote: I do not like it

        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

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it +22 Vote: I do not like it

    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

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How did you calculate f(x)?

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

        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.

»
5 years ago, # |
  Vote: I like it +22 Vote: I do not like it

I think, I was solving at least 3 different versions of the fourth task until I understood right one.

»
5 years ago, # |
  Vote: I like it -8 Vote: I do not like it

How to solve E , can anyone help me .

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

How to solve B?

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

    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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like 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.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I was able to get the parity condition,but i could not implement the solution along with saving the indices.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

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

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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    E: path(x) contains y IFF in binary form either y or y ^ 1 is the prefix of x.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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)$$$.

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

        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.

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

    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.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I tried this, got WA. It could be an implementation error though.

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

      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

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please explain me the question? DIscussing solution won't help me unless I am clear about question.

      Thanks.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

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

    It's DP. dp[index][numWarriors] = optimum value when you are starting from index = index with numWarriors.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve C?

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

    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)

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

how to solve D with DP?

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

    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.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks a lot, so how to transfer ? I can not find the way to use portals

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

        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

»
5 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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.

»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Please unlock the solutions.

»
5 years ago, # |
Rev. 2   Vote: I like it +135 Vote: I do not like it

»
5 years ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

Pretest for B is too weak...

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

    Why are you signed in as another user?

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

      I received this picture from my teammate.

»
5 years ago, # |
  Vote: I like it -24 Vote: I do not like it

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.

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

    I thought k == n is in the sample itself!

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -16 Vote: I do not like it

      For some reason it gives output for k == n case when k is small.

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

        You can hack yourself to append you stronger test case to the system test, a good chance to try it.

»
5 years ago, # |
  Vote: I like it +22 Vote: I do not like 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://mirror.codeforces.com/contest/1271/submission/66962381

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Even I solved it using greedy method. Time complexity O(nlogn).

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

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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

My (tester's) solution of F:

Spoiler
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    could've waited for 10 more submissions to get 66966996 :)

    Thank you for the solution though

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

    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.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Solution 66967994 using simplex method should be correct for 1271F - Divide The Students ?

»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Very weak tests! In task D there is no test with the answer 0

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

Why was my submission skipped for no reason?

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can somone suggest some similar problems like D(Portals)

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How do we solve DIV2 B, if we have to minimize the number of operations?

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it +6 Vote: I do not like it

    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.

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

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.

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

    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.

»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like 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

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

Can someone please explain how to solve DIV2 E. What should I apply binary search over?

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

Ratings are not updated yet. Was this contest rated?

»
5 years ago, # |
  Vote: I like it -28 Vote: I do not like it

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.

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

Don't know why my solution is failing on test 4. Can someone please help.

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

Can some one elaborate DP solution for D? What are the states and sub-problems?

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

    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.

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

Editorial has not been published for the last 3 contests. Will it be published in the near future?

»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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 !

»
5 years ago, # |
  Vote: I like it +17 Vote: I do not like it

I am extremely eager for the upcoming editorials! I hope they'll be out soon!

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    BledDest

    Are the editorials still being prepared? It has been more than 2 days since the contest!

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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!

»
5 years ago, # |
  Vote: I like it +15 Vote: I do not like it

The editorial is published. Sorry for the delay.

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

    Can you also publish an update in the announcement blog? People are more used to looking it up there. Thanks.