Well we have the upper and lower bound. Just take the diff

exactly. one solution for A, B, and C

trial and error? need only around 30k levels to reach $$$10^9$$$

could be 8 8 8 8 thus on 1st second

No need to count connectivity of red edges. Merge all nodes with red edges to components and multiply each member count of adjacent components

Especially this part. Can elaborate more?

Because count(i, i, vec[i]) is always 1.

All 3 just fine

I found the problem G day 1 has a weak testcase. My submission got a bit typo and yet still AC

I dont know for BIT but for segtree you can store additional factor for all nodes (initialized by 1). For each scale query, just scale this factor properties as always.

In this case just 3 times (2,2,5). But anyway number of choosing doesn't really matter to optimal choosing. We can get optimal value by more than one way

choose any 2 -> delete 3

choose another 2

choose 5 -> delete 4

total 9

10

Cycle with 3 or more elements can still exist, yet can't return to original sequence (see (nxy) example above)

To maximize dimension of pieces, we must divide choco such that row and col of each piece nearly equal. So we divide n to x choco rows and m to y cols, and take floor because of minimum area

And at least a neighbor dot have visited to ensure it reachable from start point

Remove an intersection is remove a horizontal and vertical bar. Rest is yours ^^

10961000

It should be i,j,k in bound checking and counting chances

Usually the problem related to euler theorem is "given 3 integer A, B, C (can be vary large), find the value of A^B mod C" Such as, UVA 374 and UVA 10692

have an explanation?

Have you try Euler Theorem ?

Factor of luck

Sleep is for da weak.

Optimize it more by change the stack type become stack of current node only. If you pop the current stack top element must be parent

still here

Actually same as usual hashing. And since we look for palindrome, just find whether prefix and suffix match or not

Here's the official editorial : link

Easy to noticed there are only 2 case of arrangements, RRG and RGB. Use the second one when number of colors "balanced" enough, and the first one to the rest. Then consider if all arrangement is first scenario. So, you have (a[1] + a[2]) triples, and use 2 * (a[1] + a[2]) from the a[0]

could you explain what kind of knapsack?

Any other solution of E aside the segtree?

UPD : sorry i mean E but i wrote D

easy to note that we can build palindrome by add same character to begin and end of another palindrome. just consider the case of odd and even length, so we could just check every 2 and 3 consecutive letters

Why we cant change 1 to 1000000001 ? In description we can change to any integer we want, not neccessarily <= 10^9 (although the constraint of input is between 1 and 10^9). Am i wrong?

Yes. Proof can be found from matrix exponentiation, or by induction here

Then make 2 segtree, for maintain (supposed to be seg1) and (supposed to be seg2).

Sorry if this explanation seems unclear. More detail you can check my submission 7338693

The key is the merging step

While merging and , we need to shift the Fibonacci multiplier of the second one by (l2 - r1) to the right , so that we get

Shifting can be done by using identity F_n + m = F_nF_m - 1 + F_n + 1F_m

I just realized telescoping series in this sum. Anyway, thanks

could you explain this simplification?

\sum_{i=1}^m i * \frac{i^n — (i-1)^n}{m^n}

could you please explain more?

Has matrix-exponent optimizations been included here?

That's look like "lazy propagation of colorness", "sum of colorness", and "same color of range"

Could someone explain more bout solution using fenwick tree on Div1 C ? Or, specifically, how can we maintain range of color if we dont use segtree? Thanks

Remember a/a is 1. If we have a/b resistance, put one more resistor parallel will give

Hmmm chinese contest. Brave yourselves guys!!

Actually all we need is bravery :))

Actually we just need 2N - 1 nodes, where N >= n is a power of 2

Clean your code first. Put some spaces and indentations would be enough

I'm sure i don't change anything. Also i've changed class to public and still output 4

edit : this code works well in public class http://ideone.com/zZ0l5e

I don't have idea why the grader and custom output different. Could someone help me on this?

Submission : 6930710

I'll try with the bruteforce one. Since it's very simple

Suppose we take first k leftmost items with left hand and -obviously- the rest with right hand. Total cost we make for taking those : sum Of First K Leftmost * L + sum Of First (N-K) Rightmost * R. Bruteforce all possible K and find the minimum cost. Calculate those two sum can use precalc left[n] (sum of K leftmost items) and right[n] (sum of K rightmost items).

Then we need to minimize penalty Ql and Qr by taking items alternately (ex: LRLRLRL). As you see we got penalties only when different of taking left and right items |k - (n - k)| > 1. If left taken items more than right ones (ex: LRLRLRLRLLLL), add penalties Ql * (|k - (n - k)| - 1) else add Qr * (|k - (n - k)| - 1)

Sorry for bad english. Here the code : solution

You may consider using Prim instead, it's easier to write edges back

UPD: has been answered above. I didnt mean duplicate comment. sorry :(

I'm surprised that C can be solved by bruteforce :O

Ohh nice idea. Thanks a lot

Till max day + 1 of course :))

Notice that answer must be mod by 1e9+7. Some factor may lost within this operation

Can someone tell me why this code got TLE?

I'm not pretty sure if its called DP or else

Suppose we have range [0..X], we can make every number from 0 to X with lowbit of some elements from set S.

If we add one more element from S, supposed to be M. We can update range become [0 .. X + lowbit(M)], the proof is really easy. So, range [X + 1 .. X + lowbit(M)] can be arranged by M as last component.

After we precalc last component for each X <= sum, we can backtrack the query and find all of components of sum.

Sorry for my bad english ^^

Here is my solution if you want to know more

How is your dp then? Actually using dp and simple backtrack can run in linear time, should be fast enough

how can you find it? can you tell me please?

UPD : why you so rude to me? I just wanna ask for solution :(

I hope there are editorial after contest has ended

How do you know that? Are there any differences in these accounts? LOL

Someone told that B can be solved in O(N²). Can anyone please explain me about this solution?

Since you didnt use memo, your program can run up to o(k^n)

48 here same as '0'. Read this http://www.asciitable.com/

Nice explanation. You can consider the prefix sum instead of binsearch to make it O(N)

6637312

Not really Goldbach conjecture i think. It's just construct minimum prime partition of a swap-range

toki.or.id

but i didn't know they had a open contest for intl students too

Try understand this first. I think this should be clear enough

http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/

Any editorial?

Tutorual?

I think explanation above inspiring enough.

use the counting sort

and the other half are worse than usual :(

how can it be? can you explain a bit more?

Consider we have dp[msk][last] = amount of min money spent on solving problems chosen on msk with hire maximum first last friends. (msk is bitmask of chosen problems)

Then suppose we want to hire the (last + 1)'s friend which cost is dp[msk][last] + cost[last + 1]. If this amount less than dp[msk|solve[last + 1]][last + 1], update it.

The answer is minimum of dp[allproblems][k] for all (1<=k<=N) plus cost of monitors required.

Surely it's obvious. Maybe you can fix it for few so that it can be right

My greedy approach for D didn't work. Can you tell me why? 6357863

1 2 9

5

with N=1, A=2, B=9, and x1=5

see (2*5)%9 = 1

Try

1 2 9 5

the answer should be 0. But your formula ((x * A) % B) return 1

If you use iteration inside frame_correct in D div2, total complexity is O(m².n²). Use prefix sum to reduce searching to O(1) and total complexity is O(mn)

For Ediv2 / Cdiv1 i come up with the fact that number of inversion after reverse = N(N-1)/2 - number of inversion before reverse - number of pair of same element

But still dunno how to make efficient solution with this. Can someone help me?

can you tell me how the idea of this?

same as mine. try this 1 2 9 5

the answer should be 0

why the answer is 0? still dont get it

UPD : okay i understand now

as you see

well with memo solution above still running in O(N)

I'm still wondering in D. Should I submit for every combination of 16 bytes?

You dont have any 't' and 'w' and you can't make 'tttwtqq' with only 'y','q' and 'f' letters

Good solution. But i still dont get how to save queries in each element and find the current element?

I see. Since the problem only in range 10^5 using array is more efficient right?

I didnt notice this while implementing. Thank you

I also use map<vector> in 404C- Restore Graph problem to make much simpler implementation : 6083798

Is it just me here think that Div2 D is easier than C ? :))

exactly. its been clarified during the contest

Problem C. Restore Graph ***** The distance between two vertices is the minimal number of edges in the path between themc

your answer is valid if input 5 4 0 1 1 1 2

well, there is no vertex can be in distance 4 if there is no vertex in distance 2 and 3. so there are no answer

Thanks. I'm waiting for it

When the editorial posted then?

your 4th vertex has more than 3 edges. It should be 3 or less

UPD : okay maybe comment need some correction

So complicated way. Why dont you just find the first element of the corresponding element of array and count it? And the constraint is so small only about 1000 first element was able to counted.

If there are some element had been in the right order in sequence for a first element most, so its the most probable sequence. Then find differences with corresponding element in array. Just it

Here my solution : 6037944

I didnt really understand the problem and just generate the pattern for C div2...

and got AC :v

For problem D can you tell me what 'mask of reshuffle' means? sorry i don't get the solution clearly

Just try submit again. It's only temporary

luckily in last contest i became specialist. now it's turned back