BledDest's blog

Codeforces Round 608 — Editorial
By BledDest, history, 5 years ago, translation, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +36
  • Vote: I do not like it

Comments Comments (26)
| Write comment?
»
5 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Finally, the editorials are out.

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

Has any one solved the problem E like the tutorial? Please post your code.

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

Can someone explain the other solution to E ?

I saw many solutions which did not use the binary search idea. For example neal submission

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

Can Any one give a Dynamic Programming Solution with explanation for Problem B? Thanks in advance

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

    dp[i][j] = maximum answer if we start from city i and have j soldiers We first store what cities last city are the city i, and sort them by array c. so we can now choose how many of them we want to defend. my submission==> https://codeforces.net/contest/1271/submission/67000853

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

      Thanks for your efforts ... but i need Problem B ... not D ^_^

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

      It will be very helpful if you can briefly explain the dp transitions, I tried a lot but not getting it.

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

Can anyone explain the count(x)>count(x+2) concept of the problem E?

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

Well, I use a weird method for E: 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 probably 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). But, I don't know whether the statement is true, so do anyone know how to prove or disprove it?

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

In editorial of problem D it's written that: "The key observation is that it's always optimal to defend castle i (assuming we decided to defend it) in the latest possible castle. Since it gives you more warriors in between of i and X (more freedom), it's always optimal." How is this true? Suppose there are two X1 and X2 from where you can go to i and X1 is near to i than X2. But it doesn't guarantee that you will have more warriors during X1 than X2. It depends on how many warriors are you gaining after each win. Please correct me if I'm missing something here. Thanks in advance!

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

    If you decide to defend city $$$i$$$, then at the end you'll have one warrior less than you would have had if you had decided not to defend the city. Now the question is, at what point will you lose this one warrior? You would definitely want to lose it as late as possible, so that this warrior might prove to be of some use between the city $$$i$$$ and the city ($$$x$$$) from which you sent this warrior.

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

It is also possible to solve D in a greedy way without undoing your actions by using a $$$min$$$-Segment Tree and some precalculations. Keep an array that represents the last point from where you will be able do defend the $$$i-th$$$ castle ($$$l$$$) and another array that keeps the maximum amount of soldiers you can leave behind when you reach castle $$$i$$$ and still conquer all castles if you never defend a castle ($$$v$$$). To calculate it just iterate from castle $$$n$$$ to castle $$$1$$$ where $$$v[i] = min(v[i+1], S_{i} - a_{i})$$$ and $$$S_{i}=k + \sum_{j=1}^{i-1}b_{j}$$$. Append $$$S_{n+1}$$$ in $$$v$$$ and build the $$$min$$$-Seg from the nem $$$v$$$ (this is needed as we can defend using all soldiers in the last castle). Now just iterate over the castles from the most valuable one to the least valuable and if $$$query([l[i], n+1]) > 0$$$ we can take this castle and apply $$$update([l[i] + 1, n+1], -1)$$$, else we can just continue, as taking the current castle over a previous one would either make no difference in our answer or worsen it. $$$O(nlogn)$$$ complexity as well.

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

    bro i used similar technique but getting wrong answer. I used BIT , 1)->after storing the maximum difference between the total warriors available and warriors needed at index i in an array(called 'dp').

    2)->Then from right end I stored the minimum value at index i present to the right of that index and including that index in 'dp' array.

    So for this(Test case 5) example my dp array would look like this:

    5 5 0. 0 1 1738. 0 1 1503. 0 0 4340. 0 1 2017. 0 2 3894.

    'dp' array = 0 1 2 2 3 and ith element shows how many defended castles we can have before that.

    Now i used 'set<pair<int,int>,greater<pair<int,int>>> s' to store the gains at index i in decreasing order. So we traverse the set and check whether this castle index can be defended at later stage or not(we take the maximum index if possible).Now we check whether the prefix sum if smaller than dp[i+1].If possible then we update in BIT and add the gains to 'sum' variable. But I am getting wrong answer,pls help.

    Submission wrong at test case 6

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

Can someone tell me why the dp solution of problem D won't get TLE, i think in the in the for loop, the complexity is O(n*n*n). Thanks in advance. 67195351

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

    Yeah, I had the same confusion. So, if you look at the loop $$$fore(k, 1, N)$$$, you enter that loop only if $$$last[j] == i$$$ i.e. only if the last portal of the $$$j^{th}$$$ castle is in $$$i^{th}$$$ castle. In other words, in the worst case, the loop runs only once for each castle making it $$$O(n^2)$$$.

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

Idea for $$$O(M^2)$$$ for problem F:

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

You don't actually need two binary searches for the problem 1271E - Общее число. Let $$$S_x$$$ be the set of numbers that have $$$x$$$ in their paths and $$$ count(x)=|S_x|$$$. For example $$$S_4 =$$$ { $$$4, 8, 9, 16, 17, 18, 19...$$$ } . Clearly, for every odd number $$$x$$$ (except $$$1$$$)

$$$x$$$ has $$$x-1$$$ in its path.

$$$\implies$$$ all of the $$$count(x)$$$ numbers of $$$S_x$$$, has $$$x-1$$$ in its path.

$$$\implies$$$ $$$x-1$$$ appears in more numbers' path than $$$x$$$ does i.e. $$$count(x-1)>count(x)$$$

On the other hand, it can be seen that for $$$x$$$ is even and $$$x>2$$$, $$$count(x)\leq count(x-2)$$$. The $$$k^{th}$$$ element of $$$S_{x-2}$$$ is always less than the $$$k^{th}$$$ element of $$$S_x$$$. You can observe it from the pattern of the elements of $$$S_x$$$, as $$$S_x[k]=2*S_x[\frac{k}{2}]+$$$[$$$k$$$ is odd]. So, using this information, we can iterate over only even numbers as $$$x$$$ using binary search to find the largest $$$x$$$ such that $$$count(x)\geq k$$$, and check whether $$$count(x+1)\geq k$$$ as well. This essentially deals with the odd numbers' binary search as well.

To find the $$$count(x)$$$ for any given $$$x$$$, notice the pattern of $$$S_x$$$. It's almost like a binary tree. So you know the number of nodes in every level and the highest labeled node. Whenever that gets $$$>n$$$, just take the trimmed portion of the level.

My contest time submission: 66958024

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

In fact, F can be solve in $$$O(M)$$$. It's easy to know my AC code is run in $$$O(M)$$$.

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

Problem D is great:) But the description can be reduced???

→ Reply
»
5 years ago, # |
← Rev. 8   Vote: I like it 0 Vote: I do not like it

Problem D: My code got accepted but failing at following testcase:

https://codeforces.net/contest/1271/submission/67515586

3 2 1

0 0 20

0 0 10

0 0 5

2 1

3 1

Did I miss any constraint?

→ Reply