N** coincidence, why not? You'll feel like making "Tommy" do all sorts of interesting/ridiculous things if you do more problemsetting.

Not for you bro

till now yes.

I want to ask it too.The past two contests are both unrated!

He unregistered!

He unregistered now, or he isn't registered basically his last visit was 6 hours ago before which is before the registration opened. Looks like you just want contributing points :D

Then why I can't see tourist in the registration list?

...

He ranked 5 in SnackDown 2017 Finals today the 3 top are 1-Um_nik's team 2-anta's team 3-jcvb's team

check Ranklist here

It's three

the answer is after the contest :D :D

The last round was just the author's luck though, nothing could have been done to help.

Soon it will be Round #422=Downvote x422

.

Attack on acloser season 1++

Ban everyone!

Is it possible to make User-Id using loop?

What's the gain on creating multiple dummy accounts ? Altering the quantity of people that have submitted something wrong, and in that way boosting your rating income?

76 likes, it seems all the acloser liked this.

No :)

Me too.

dp f(i)%=MOD before calculating f(i)*t^(i-l)

I used adjacency list + BS.

EDIT: failed systests. two pointers

You can sort by difference between l and r (sort by cost in case of equality) and then use two pointers to iterate your array .(runs in O(nlog(n)) )

Use a segment tree with min query and you can do it in O(n*log(n)). You don't need the binary search.

many people code like this

they don't limit i+n-1<=m

for (int i = 1;i <= m;i++)
   for (int j = 1;j <= n;j++)
  {

  }

so hack is

4 4
abcd
eeab

Apparently not. I used a prime sieve and submitted at 1:59 and got pretest passed. (if only I had gotten it earlier though...)

Mine passed in 1240 ms. Hope it passes system tests too.

Mine passed in ~700 ms.. So guess it will run..

F[n] = F[n / x] + (x — 1) * n / 2; Where x is smallest prime factor of n.

I got pretests passed for O(nlogn) in 545 ms, hope it passes system tests too...

EDIT: Passed system tests. Phew.

EDIT EDIT: Never mind, looks like my solution wasn't O(nlogn)

Answer should be -1 right?

Also, I hacked 1 brute force solution, and one solution with inf = 1e9(max answer can be 2e9).

Loop through all the sorted start and end points and if it's an end point, add the length and cost to your set, and if it's a start point then check all the end points before the current coordinate (in the set) to match the 2 lengths together.

For every length store costs and left border in vector. Then sort these vectors by left side and cost. And for every element do binary search. 28224027

EDIT: This failed systests. sort by duration of voucher and use two pointers method. works in O(nlogn) due to sorting. it passed pretests, hope it will pass systests as well. http://ideone.com/BU1KjQ

1. Create arrays for vacations of each length.
2. Write all vacations into corresponding arrays (l, r, cost)
3. Sort each array by vacation start date.
4. For each array create a corresponding array of the same size and write minimal vacation cost for all vacations which start from x or later.
5. Now iterate from 1 to x (length of your first vacation). Length of corresponding vacation would be x-i.
6. On each step you have to find minimal price of second vacation (of length x-i). Because you sorted your array you can find it using binary search (also note that we use calculated suffix minimums here).
7. On the end of each step update your answer.

O(n) solution for C: 28224212 It passed pretest. But it didn't passed System test :(

You should check for 32-bit integer overflow

Have you done the operations MOD 1e9 + 7 ?

I also fell down on the second test. Then I noticed that I forgot my answer by modulo after each addition.

If you are updating f[i] from f[i / p] (where p is the smallest prime divisior of i) and i >= l and i / p < l , f[i] would update incorrectly.

Hi, I had an idea with hashings, with some greedy steps for problem E. The general idea is to keep the matched segments in some stack and remove those segments when a better one appears. Below the steps:

*Let's say "size" is equal to the sum of length of your segments in every step. *For every character "i" in string "t", and with current position pos = 0 in "s" do this:

(1)Look for the ith character of "t" in s[pos... n], take the first ocurrence, let's call this position "k" in s.

(2)Check if the largest common suffix of s[1,2,...k] and t[1, 2, ...size + 1] can replaced some stored segments on your stack.

(3)Remove segments of the stack that can be replaced by the largest suffix.

(4)Updated pos, size, Repeat until pos = n

Finnaly if you got the whole string "t" in "s", you will need one aditional check if some substring at the right position of "pos" can be a better suffix for t.

suffix array is not necessary

It can be proved (I simply bruteforced), that at it stage it was optimal to take the smallest group possible.
Given this, you simply computed the answer with help of memoization and a prime sieve to prevent TLE.

I did like this. For any n, the optimal choice is always a prime factor. To prove this, it's enough to prove that its better to choose X for N and then Y for N/X rather than choosing X*Y for N.

F(N) = X*(X-1)/2 * N/X + Y*(Y-1)/2 * (N/X)/Y + F(N/XY) in the first way.

F'(N) = XY*(XY-1)/2 * N/XY + F(N/XY) in the second way.

Its simple to prove F'(N) > F(N) for any X,Y > 1 (Just rearrange the terms, do some math).

F[n] = F[n / x] + (x — 1) * n / 2 Where x is smallest prime factor of n. Lets say n is composite: n=p*q. When F[n] = min(F[n / pq] + (pq — 1) * n / 2,F[n / p] + (p — 1) * n / 2, F[n] = F[n / q] + (q — 1) * n / 2) When F[n/p] = F[n / pq] + (q — 1) * n / 2 When F[n/q] = F[n / pq] + (p — 1) * n / 2 From this you somehow prove that you need to choose first smaller of p, q.

Mine, if we replace sort with counting sort: 28224166

I belive mine is: 28236057 Edit: although technically it's O (200000+n) I guess

I'm not sure, but if your comment rating is in [-5; 0], cf will show this rating as 0, but will count real rating when calculates contribution

Your solution's complexity doesn't depend on l, r. If your solution runs like 1400-1500 ms it can get tle when rejudged I think.