Do DFS.. For each child get 2 values their pleasentness sum and the max pleasentness and 2nd max pleasentness value till that child.

Keep one max_ans and update it with max(max_ans,max1+max2)

Update and return your sum and max(your sum, max)

Do the above for each node and finally print max_ans

This works because of the 'max1' and 'max2' coming from the different subtrees of the children thus satisfying our condition that the subtrees shouldn't intersect

If it holds for n, then it also holds for n+1. Proven. Ps: Isn't is the most 0 on the right? (In base 2)

https://oeis.org/A001511

Not sure this is an answer. Just another relevant observation while talking about all things binary :P But the answer can be obtained by binary-searching the index k in the range [1,2^n — 1] and decrementing the answer variable by 1 at each "step".(answer is initially n). We see an obvious analogue coz for any n, the value n is at the "mid" of the sequence. Formally, the answer somehow depends on the number of comparisons a binary search would do, in order to hit index k in the range [1,2^n — 1] See submission for clarity 22961954

One line solution to B — 22997490

isn't it just binary search on possible values of len?

Good idea. I'd just like to add some improvement.

Define dp[ind][mask] as the size of largest sequence that can be built starting from index ind and only using elements unset in mask, with each element being repeated x or x + 1 times.

For each state, either you'll add the element at index ind for x times, or x + 1 times, or 0 times and move to ind + 1.

We can do some pre-computation to be able to get the position of x - th following occurrence of some element in O(1).

Clearly, this function for a fixed x is O(N * 2^K).

As you've said, we can do binary search on x, and the validation function will be whether this dp returns 0 or not.

This way achieves better complexity and simpler code.

Total complexity: O(log(N) * N * 2^k).

2/n = 1/n + 1/n

so, x = n; observe that, 1/y + 1/xy = 1/x if y = x+1;

2/n = 1/n + 1/n

So we have just made the problem much easier because how we just need to represent 1/n as a sum of 1/x and 1/y (then we would have 2/n = 1/n + 1/x + 1/y)

Then let's take a look at the second testcase and find out that x = n + 1 and y = n * (n + 1) are right for all the cases (just because 1/(n + 1) + 1/n(n+1) = n + 1 / n(n + 1) = 1/n)

Let's check that 1/x != 1/y != 1/z

n != n + 1 for every n

let n = n^2 + n then n^2 = 0, n = 0. But all n are positive so this also work for every n and the last case n + 1 = n^2 + n <=> n^2 = 1 <=>(n is positive) n = 1. So in this case we can't represent 2/n as 1/x + 1/y + 1/z

Finally x, y, z would be less than 1e9 because n less than 1e4, so n^2 + n is less than 1e8 + 1e4 , so this restriction is useless.

As for me, I can't guess why this problem costs only 1250, I think it is much harder than B and than common Div2C

Here You can read here for more information :D. This is the website that I googled during the contest time.

k<=2^n следовательно log(k)=n

You know sample test 2? Take it for instance... Suppose you can write x=n, y=b, z=(n*b), ok? Then,

2/n = (1/n) + (1/b) + (1/(n*b))

1/n = (1/b) + (1/(n*b))

1/n = (n+1)/(n*b)

1 = (n+1)/b

b = n+1

Then, x=n, y=b=n+1, z= n*(n+1) solve the equation, since they are all different;

For n=1, you can see that there's no solution: if x=1, then we have to find y and z that satisfies 1=(1/y)+(1/z) Since they must be different from x, we can maximize the value of the equation by y=z=2, then we would have a solution; in that case, y=z, and it can't be a solution by the hypothesis that they are all different ;)

As you can see by sample test 1, it is not a "formula", there are other solutions. You have to find a "pattern" that works for any given n ;)

what i did was to break 2/n = 1/n + 1/n now we break the whole equation into 1/n + 1/n = 1/x + 1/y + 1/z now break it further that is

1/n = 1/x + 1/y -> 1

1/n = 1/z -> 2

from 2nd z = n

1/n = 1/x + 1/y ( Diophantine Equation )

whose solutions are x = n + a and y = n + b and a*b = n*n

take a = 1 and b = n

therefore x = n + 1 and y = n + n*n

В данном случае это невозможно тк или первый подарок подвешен ко второму или второй к первому. И взятие верхнего из них автоматически возьмёт и подвешенный к нему подарок.

они решили выбрать себе два таких различных подарка, что множества подарков, подвешенное к ним цепочкой из веревок и других подарков, не имеют пересечения. Иначе говоря, не должно быть подарка, который был бы подвешен к подарку Хлои и подарку Владика одновременно

How could we get the formula ?

это если считать чтение данных в сложность решения

You seem to be iteratively checking the remainder after dividing by powers of two.

Instead of that , you can simply check the binary representation of k , and find the first position from the right which is 1.

Like this: 22997490

First, observe that we only need edges between adjacent airports (cost 1) and between airports of the same color (cost 0). Although we have the option to jump from any airport to any other with cost |i-j|, we can reach it with the same cost by jumping there 1 by 1 (ex. instead of jumping straight from 3 to 6 with cost |3-6|=3, we can jump 3-4, 4-5, 5-6 with cost 1+1+1=3). So now we would have n edges except that we still have edges with weight zero between every pair of airports with the same color, giving potentially n^2 edges. To fix this, change your nodes from airports to airport colors (since any two airports of the same color can be reached with cost 0, we can consider them the same node). Now you only need the linear edges between adjacent airport (color)s, and you can do a BFS (all edges left are weight 1) with O(n) nodes and edges, so O(V+E) -> O(n)

Note that in the case where there are only two colors, the graph you create will end up being either two connected nodes (if you have both 1's and 0's) or a single node (if the whole string is 0's or all 1's). This means the shortest path will always be 0 if you are the same color as the target, or 1 if you differ.

Ok, я понял, как выглядит динамика и как она пересчитывается. Правда, видимо, это нужно трактовать как максимальное кол-во цветов, которых мы берем len + 1, и заканчивая ровно на позиции pos.

In the problem statement : "...the sum of pleasantness of all the gifts that they will take after cutting the ropes is as large as possible."

Because they both have to cut the rope, they can't take the subtree with root = 1.

Remember "they will choose prizes at the same time", so you can't cut the rope between 8 and 10. In another word for "at the same time", you have to choose two disjoint subtrees. So the best solution is choosing only vertex 6 and vertex 7 which has answer = 3.

You have to pick 2 different subtrees A and B such that there is no common vertex between A and B.

you just finding min distance with signs similar to s[a] and s[b], but it is not true. example: 5 2 5 11100 here your answer is 2, but you can go to 3rd airport for free (it's similar to s[a]) and you go to s[4] it will cost 1 and you will go to s[b] for free(s[4] equal to s[b])

shortly, answer will be one if s[b] and s[a] different airports, and 0 if they are same

nice :D

I didn't came up with a way to maintain the length of dp array so I also ended up trying all possibilities, thank god k! (k=8) isn't that big.

Haven't seen a Div2E problem been this open-ended for a while.

My solution

Time complexity, where k is the variety of cards: O(log^2(N) * k! * C(k, k/2))

Reading the input is O(n)

WOW! This is the coolest thing I came across on the internet today! Didn't even know about builtin functions, but now I do! Thanks :)

Please read the other comments first.This one , in particular.

Answer is 1. Go from 5 to 6. : Costs 0

then 6 to 7 : Costs 1

then 7 to 8 : Costs 0

Total Cost : 1

No need to go directly from 6 to 8, use the fact properly that going from one index a to other index b such that I is 0. Infact, the answer can never be greater than 1 since the indices of transition from a '0' to '1' in the string are always consecutive.

Code

1^1=0 0^0=0 0^1=1

Conditions doesnt have to be satisfied in the original sequence, your task is to find the maximal subsequence, where they are satisfied.

https://en.wikipedia.org/wiki/Subsequence

typedef vector < int > vi;
...
struct node{
	ll data;
	ll m;
	ll sum;
};
...
vi s;
s.pb(val[graph[x][i]].m);	

I was wrong at the test 15 too. Have you known the reason for that? If you know , please tell me ,thanks?

http://codeforces.com/blog/entry/49049?#comment-330919

amax is a funcion, that is trying to maximize some value. Extremely sorry for using this code-style in a solution written for public.

Our subsequence looks like this:

c_1, c_1, c_1, c_1, ..., c_2, c_2, c_2, c_2, ... c_8, c_8, c_8, c_8,

where c is some permutation, the order in which we are taking the colors. On each position in the array we have to know how many and what exact colors we had already taken. mask would be a bitmask of 8 bits, where i-th bit is 1, if we had already passed the segment with number i in c, otherwise 0. So the whole state is pos, mask — the maximal length of the subsequence, if we stand at the position pos in the array and already passed all the 1 bits in mask.

look at my code i m not getting the error http://codeforces.com/contest/743/submission/23025516

Wow! how did you observe it and guess it?