Topcoder SRM 714

Time: 2:00 pm MSK Sunday, May 7, 2017

At the same time there will be an onsite contest: https://tco17.topcoder.com/regional-events/st-petersburg-russia/. We will share problems for both SRM and this regional contest.

Calendar: https://www.topcoder.com/community/events/ (Note: Still not updated)

Auto comment: topic has been updated by cgy4ever (previous revision, new revision, compare).Update: added start time and link to regional contest.

Contest coming!

We will share problems for both SRM and this regional contest.Will the onsite regional event have div. 2 or div. 1 problemset?

We need a problemset that are good for both first time player and TCO winner, we will use Div2 Easy, Div1 Easy and Div1 Hard, so hopefully everyone can enjoy it.

Registration open. Update: start time is 2:00 pm instead of 1:30.

Is topcoder down at the moment, I can't enter Arena?

Same. It's down for me as well.

Hard is very nice!

What's the intended solution of Med? Straightforward solution works in

O(KlogMAX*memoization_{cost}), but I struggled a lot with TL.I'm extremely sorry if what i'm gonna explain now is wrong, as i am incredibly inexperienced ->

each time from f(n) we use f(n / 2) and f((n + k) / 2), Look at this tree of states, in each level the difference between the state with minimum number and maximum number is at most k, so that's why we can use an array of size k for each level, that would make the memoization cost O(1), of course please correct me if i'm wrong

Since all subtasks we get are in form of "calculate answer on segment [1, n / 2^x + y]", y <= K, n is L or R, memorization can be a simple array lookup. It works fast even in Java.

My submitted solution was buggy, but I still think it can be solved like this (not sure what are your solutions memoizing, so I don't know how different it is; skipping some +/-1 adjustements): we compute the values for even numbers

`[L, L+K)`

directly, as well as for odd numbers in`(R-K, R]`

. The rest of`[L, R]`

can be split into even numbers from`[L+K, R]`

, and odd numbers that directly correspond to them. So we can solve recursively for the`[(L+K)/2, R/2]`

.memoization_costis then replaced by the cost of directly compuingKlog MAXvalues, so I guess bylog MAXwith a low constant.No memoization:

Go from the end, fix finishing number

x≤K. Now if we look at the tree of numbers generated by going backwards fromx, they will be of the formx2^{p}-kq, where 0 ≤q< 2^{p - 1}.Number of applications of

ffor such number is simplyp+numberOfBits(q). Now it can be easily summed up over numbers from [L,R] ifxandpare fixed.It seems the only thing I needed to do was to replace a map with unordered_map.

Another one, without memoization :

Let

S_{i}= sum ofg(i) for [K+ 1,i+K]. Then,S_{i}=i+ (S_{i / 2}) + (S_{(i - K) / 2}+i/ 2). However, we can naively calculateg(i) inO(lgN) time. So, If we knowS_{(i - K) / 2}, we can knowS_{i / 2}inO(KlgN) time.T(N) =O(KlgN) +T(N/ 2) =O(K(lgN)^{2}).Can you please explain the proof?

Well, what requires proof?

I'm not quite sure how you derived

S_{i}=i+S_{i / 2}+S_{(i - K) / 2}+i/ 2? Just intuition behind it would be useful. Thanks in advance.That is a recursive definition, try to separate cases for odd / even number in interval, and write what happens next for both numbers.

I was the author of this round except for div1 medium. I hope you enjoyed the round!

After this round, I've got 99 problems on Topcoder.

Here is some of the code and hints for the problems.

div2RangeEncodinghint1All numbers are distinct, and they are given in increasing order.

hint2A range will take consecutive elements in this list.

hint3We can try greedy.

codeRemovingParenthesishint1How many distinct strings can we possibly generate?

answerAn easy upper bound is 2^20.

hint2We can try to simulate the process, but memoize answers.

codeSaleswomanThere are two approaches

approach 1hint1Try dp

hint2We can satisfy the demands from left to right. So, we just need to keep track of the rightmost person who's demands have satisfied. Similarly, we need to keep track of the rightmost person who's supply we have taken. Lastly, we need another parameter for where are currently at.

codeapproach 2hint1Try greedy

hint2We can satisfy demands from left to right. One example of Alice's optimal strategy is to only turn back if she can satisfy every person behind her.

codediv1ParenthesisRemovalhint1Let x[i] be the number of openining parenthesis before the i-th closing parenthesis. Then, we need this parenthesis to be removed at turn x[i] or before.

hint2This is also a sufficient condition. To show this, we will show that if the balance for a particular closing parenthesis goes below zero, then it will be removed after turn x[i].

In particular let's look at the leftmost parenthesis whose balance goes negative. At this point we matched i-1 closing parenthesis to its left correctly and this does not effect the balance. In addition for its balance to go negative, we need to match at least x[i]-i+1 other closing parenthesis on its right. So the first turn we can match this closing parenthesis is strictly after turn x[i] which completes the claim.

hint3Using those conditions, we can see the answer is x[0] * (x[1]-1) * (x[2]-2) * ...

codeSalesmanhint1Try to solve Saleswoman (div2 hard) in linear time.

hint2WLOG, suppose we go to leftmost point first. This allows us to fix the leftmost visited point. What is the rightmost point we need to visit in this case?

hint3We need to deal with the fact that we can end anywhere we want. We can do that while we are simulating our greedy solution.

codeCan we solve RemovingParenthesis in O(n)? Somebody in my room did it using stack.

Yes, see ParenthesisRemoval from div1.

I know that one of the submitted hard are wrong. For example, on test where we should shuffle for a lot of times: (pos=-1+1000*k,delta=-1),(pos=1000*k,delta=1) for k in [1..100]. Do you have such a test?

Is TOPCODER Arena Down???

Works now, but active contests are gone :D

edit: back now :)