is it rated?

How about being my brother in god and working for egypt?

Hope for ecchi (see artist's weebsite).

Not always, actually. There might be minor changes like it was in the previous one (i.e C and D were worth 1750 points instead of common 1500 and 2000)

What round is the Bakemonogatari round?

Well said .. :) Div 2 D

I don't think so. This is not a place where one who is into anime participate the contest just because it's anime-themed. Anyway I haven't ever expected to see a contest involving anime character, great surprise.

Same to me

I don't think so cause of pics and story !

take some downvotes too :P

Same happened to me but they fixed it

Please fix it soon. I am unable submit yet.

Same here,please reply!

1. Write brute force solution.
2. Run brute force on all vectors (0,0,0, ... , 1, ... 0) of length k, to get weight of each individual element.
3. Recognize the pattern. Even vs. odd n makes a difference, and even vs odd also does, you're looking for patterns depending on modulo 4.
4. Verify against bruteforce.
5. Step (optional): Prove the correctness.
6. Step: Pray that you didn't miss anything.

I think to use binomial coefficients. (Pascal's triangle)

What will be the transition function? The transition function will change depending on the level we're at. eg: from level 10 to 5 has a different transition function than 12 -> 6.

In short, according to my understanding, we can't. To use mat-exp we need a consistent transition function, that doesn't depend on level.

I passed pretests by finding pattern of the coefficients (Huh). There were 4 cases, (parity of n, parity of (n/2))

Typically, when n > m.

5 3
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1

Sometimes you need to start from columns not from rows... Consider a table:

010 010 010 010 010 010

My solution because of this was hacked... Bye bye rating :D

You had an opportunity to solve it in 5 minutes =)

Its easier than that . Here one matrix is always all zeroes . In the question you mentioned in your link, the other matrix is different and you need to make both matrices equal . Div 2C is an easier version of that .

I solved it with Segment Tree + BIT. For each given n range, update the range with segment tree. Then for each i from 1 to 200000, point query with segment tree checking whether it is >= k. If it is, then update point i in BIT with +1

Later, for each query, just do a range query with BIT.

P.S. I think it's pretty much overkill. Maybe others have much simpler idea.

Do you know partial sum?

for i [ 1, n ] arr[a]++; arr[b+1]--

then find the cum. sum in the arr[].

and then also do the cum sum in the array to find if the arr[i] is >= k.

then just ans is for query l to r cum[r]- cum[l-1]

I don't think so. This is one of the hacking test.

I think they are pretty different.

try this testcase: 1 1

Solved C 20 seconds after endings...

Do you know partial sum?

for i [ 1, n ] arr[a]++; arr[b+1]--

then find the cum. sum in the arr[].

and then also do the cum sum in the array to find if the arr[i] is >= k.

then just ans is for query l to r cum[r]- cum[l-1]

Solved it with segment tree.

Let's say we calculate 2 arrays:

int l_cnt[200200];
int r_cnt[200200];

l_cnt[t] — how many intervals start with temperature t?
r_cnt[t] — how many intervals end with temperature t?

Then we can figure out in O(1) the number of intervals covering some given temperature t in the following way:

int covering_intervals = n - l_cnt[t + 1] - r_cnt[t - 1];

think about sum A[1...r] then you need to add 1 to [l, r]. 1<=l<=r<=a. think about sum A[1...r-1] then you need to add 1 to [l, r]. 1<=l<=r<=a. think about sum A[1...r-2] then you need to add 1 to [l, r]. 1<=l<=r<=a. You store array D[1...n] Add 1 to D[l], subtract 1 from D[r+1]. And them D[i]=D[i-1]+D[i]. Here you have a prefix array Check if D[b]-D[a-1]>=k.

With Binary Search code

Use prefix array

No, because then you can just use all the coupons :P

If you can use a coupon but not buy the good, Then you can just use all the coupons but buy only the lowest (C-D) items as long as you can. In other words, equivalent to the problem, you have an array of values (equal to C-D), find the max no of items you can buy with sum <= B.

You can do it in if you just find minimum in row/column and substract it. Since max answer is roughly max(n, m) * 500, it is faster. However, your complexity should be totally fine.

Also you can use DP+priority Queue to do it in (n*m). Link to my code here

Thanks

I am guessing it is similar to the question "Barricades" from "Looking for a challenge" book.

So that's why it looked familiar!! The new 10^18 bounds though...

Yes, it can be done in that way too but it can be solved easily using prefix array. Look at this code — 27855143

You can just find all temperatures that suit and answer on queries using binary search

Make an array of pairs with size 200000.

let the first element of the pair as start of some of the given ranges and the second as the end.

now iterate over all values from 1 to 200000 cumulating sum like the following:

sum += a[i].first , sum -= a[i].second. but before subtracting the end check if the sum on index i is greater than or equal to K then on another array mark i as true or just 1.

now build a segment tree (regular segment tree of sum) on the array of marks. and answer regular sum query on it.

sorry for detailed explanation :D code

Shit > problem D

if your king paid that billions for improving mathematical books instead of trump you wouldn't have said that :)

It is actually O(n^2) because for each u, the total number of iterations is the number of pairs(x, y) such that lca(x, y) = u. That sums up to number of all pairs (x,y) in the tree.

The sad thing is that I thought O(n^2 * log(n)) was fine so I sorted each node's descendants to calculate f[u][i][0] instead of running another DP :(

You can learn about this trick using this problem Barricades whose solution is described here (just download the preview).