Hello again, and hope you have been Joon-Joon of the round :P

**I’m preparing harder version of some of problems (Div.2 A, B, and Div.1 A, D) and I’ll put them on some gym, so if you are interested in harder version of problems please wait for about one week.**

You can see and download the problem archives (pretests, **tests**, statements, validator, checker, **solutions**) here. You can see solutions in solutions folder, note that there are several codes there, there is a descriptor for each code (.desc) that shows the verdict of that code.

## Preparation details:

In 25 May Sa1378 came up with problem Div.1 D and other problems authored inchmeal. Several problems has changed during the process. And several new problems authored, in fact I have another problem set to prepare another div.1 + div.2 round, but I haven’t enough time now : (.

Paintings in problems was suggested by me, painted by Sa1378 and edited by me. Problem stories and this editorial were suggested and written by me. KAN helped us preparing the round very much, we are thankful to him. This table for each person and for each problem shows the number of the committed changes (in polygon) he has made in preparing the problem (it is good for showing how much someone was involved in preparing).

User\Problem | Div.2 A | Div.2 B | Div.1 A | Div.1 B | Div.1 C | Div.1 D | Div.1 E | Total |

Me | 8 | 9 | 16 | 16 | 10 | 19 | 37 | 114 |

Sa1378 | 3 | 2 | 1 | 0 | 7 | 0 | 1 | 14 |

KAN and testers | 3 | 3 | 5 | 9 | 7 | 7 | 13 | 61 |

Here is another table, showing the number of expected accepts (in my opinion, before the contest) and the number of accepts (after system testing).

Div.2 A | Div.2 B | Div.2 C | Div.2 D | Div.2 E | Div.1 A | Div.1 B | Div.1 C | Div.1 D | Div.1 E | |

Expected | 6000 | 4500 | 2000 | 500 | 150 | 600 | 400 | 300 | 50 | 10 |

Accepted | 3966 | 1723 | 1131 | 684 | 10 | 479 | 474 | 50 | 15 | 1 |

# Hints

**Div.2 A** : Write last digit of 1378^{n} for several small values.

**Div.2 B** : Note that if then .

**Div.1 A** : If the answer exists, it depends on the lengths of cycles in the functional graph.

**Div.1 B** : It’s similar to a simple knapsack problem, think on *O*(*n*·*W*) solution using dynamic programming.

**Div.1 C** : Build a graph and put edges between each 2 * *i*, 2 * *i* + 1 and each BF and GF.

**Div.1 D** : Keep a mask for each vertex, *i*-th bit of *mask*_{v} is *true* if the number of edges in the path from root to *v* such that letter *i* is written on them is odd. Now if number of bits in is 0 or 1, path between *v* and *u* is Dokhtar-kosh.

**Div.1 E** : Sort all of the options, then problem becomes easier, solve the new problem with sqrt decomposition.

# Details

**Div.2 A**

Idea, authoring, solution by Sa1378, preparation by Sa1378 and me.

My and Sa1378 ’s birth year in Solar Hijri calendar is 1378.

**Div.2 B**

Idea, authoring, solution by Sa1378, preparation by Sa1378 and me.

**Div.1 A**

Idea, authoring, solution, preparation by me.

Attractive boys/girls are called Joon-Joon in persian. Owf is a sound used when we (persian) are interested in something, especially when we see something attractive, such as our crush :P

**Div.1 B** :

Idea, authoring, solution, preparation by me.

The problem authored by me 2 days before the contest :D (#FastAsFerrari). Attractive girls are called (some word similar to) “Hos” in persian. It’s a good place to thank Amsen, whose name (Hir) gave me this idea (to use word “Hos” instead of “attractive girl”).

**Div.1 C** :

Idea, authoring, solution by Sa1378, preparation by Sa1378 and me.

“Kooft” is something make people die. “Zahre-mar” meaning is “Venom of snake”.

**Div.1 D** :

Idea by Sa1378, authoring, solution, preparation by me.

“Dokhtar-kosh” is an adjective, used when something is very very attractive.

**Div.1 E** :

Idea, authoring, solution, preparation by me.

# Solutions

I’d like to finish the editorial with below poem by Hafez:

Translation: I have never seen anything that sounds better than **love**, it’s the relic which will remains in the universe.

Good luck and see you soon in **“Round #383 hard version”** ; )

Nice Editorials

Arpa Best editorial I have ever seen till now in Codeforces :D

In Div2C why if there is a cycle of even length we add len / 2 to S?

Because if the cycle is even you can go until the middle and return (from x to y and from y to x). Also you can go from x to x, but this option don't minimize the value of T. And when the cycle is odd you must take all the cycle (sorry for my poor English)

That makes sense. Thank you very much!

Got your Point ... I don't understand Why the answer is the LCM of all the length ?

suppose that you have 2 cycles with lengths 20 and 15. Now you have T1 = 10 and T2=15. You need to find a T, such T is multiple of T1 and T2 (this guarantees that you can go from any x to y, and go from any y to x, possibly more than once). The problem says "find smallest T". that is the LCM. (sorry for my poor English)

Could someone please explain with an example as to why Len/2 operation is being done

Because if a cycle has even length, in order for the condition to be fulfilled, it is not necessary that the line of calls starts and ends in the same person. For example, if 1 calls 2 and 2 calls 1, t=1, because if the cycle starts in 1 it will end in 2, and if it starts in 2, it will end in 1.

Thanks a lot, finally understood

Good contest... but, can anyone explain better the solution for Div1C problem? I can't understand the editorial... Thanks

Put edges between pairs a_i,b_i and also between 1-2,3-4,5-6,...,(2n-1)-(2n).

In this graph we don't have any odd cycle(prove it yourself) and if we color the vertices with colors 1 and 2 it could be answer of the problem, cause a_i and b_i have different colors and also for each 3 consecutive people there is at least one edge between two of them and they have different colors...

Сan you explain, why problem has no solution, if there is no solution in this graph, please?

You can always color the vertices by two colors in that graph so the main problem has always a solution too...

Because it can be proved that this graph always has a solution, also a solution to the main problem, we don't have to care that the problem has no solution.

Proof is very simple. Bipartite graphs always have a 2-vertex-coloring solution!

We can have a different coloring if we put edges between 2-3,3-4,...,(2n-1)-(2n),(2n)-1

Shouldn't we check for both the graphs? Thanks

You could always check for any graph that is bupartise, as there is always a solution from these graphs you could consider any of them.

The style of your editorial is great.

I used a different solution to solve 741E.

For K<=50 I created range trees (memory is O(N*50), build is O(N*50), total query is O(Q*50*logN)).

For K>50, N/K <= 2000 so we can iterate through each block of K in time, querying a sparse table over the whole array (memory is O(NlogN), build is O(NlogN), total query is O(Q*2000)).

Thus we have O(Q*(2000 + 50*logN)) which is runs pretty fast.

Very nice idea to add hints to the editorial.

anyone else solved div2 A using bigmod? :v

Me... And when I was trying to hack I found more guys like us.

I used it too, Python _/_

I will get some money for using my name or its idea :| .

You are getting some minuses instead :P

Heh you're so funny :|

This is maybe the best editorial I've seen. Though, I don't see why you use religion quotes on this website.

Thanks. Why not? My purpose is to show other people our literature.

EDITI had misunderstand meaning of word "religion", I thought your mean is the poems in the post.You start some of your blogs with "in the name of God". It looks like it isn't about showing the literature.

Why not? Anyone has some beliefs, and I believe in "Anything which doesn't starts with "In the name of God" is incomplete"

Let's move to private messages, shall we?

I'm very sorry for doing this. I'll remove "In the name of God" from my blogs now.

But why? I thought it was good :)

would you mind telling us why?

maybe i remove it from my comment...

As Errichto said, "neutral websites like CF should avoid discussions about religion because it's unrelated to competitive programming and can only divide people".

If something as generic as "In the name of god" can offend people and cause hate, then maybe they should see a psychiatrist.

You did write some heavily religious stuff. I'm sure Errichto referred to those.

Btw, I'm not very religious myself(karma is my religion), but I like seeing others following their faiths. I believe every belief deserves to be respected.

پس شما باید قبول کنی که تو کدفرسس کار ناقص انجام میدی

در ضمن ما با به نام خدا گفتن میگیم خدایا حتی به موقع کد زدن هم به فکرت هستم

مورد سوم کدی که میزنیم از خداست و به همراه اعتقاد با خداست و برای خداست

پس ما اینجا فقط به نام خدا نمیگیم بلکه تمام اعتقادات و اهدافمون رو داریم میگیم

چطور میشه که داستان های کودکانه گفتن منافاتی با مسابقه ندارند ولی به نام خدا گفتن منافات داره

اگر امروز این رو از دستت بگیرن فردا تمام اعتقاداتت رو از دستت میگیرن

به خاطر لحنم ازت معذرت میخوام

امیدوارم بهترین تصمیم رو بگیری

As an atheist I don't mind people including their beliefs in their blogs or lectures, just don't make it too long.

Different from Errichto, though I find the poem parts more disturbing (just imagine if a Christian lecturer starts every lecture with the words from the Holy Bible ), I feel like it's a bit nazi to forcing someone else to remove one short sentence "in the name of god".

Ehh, I guess it's 2016 after all.

why are u afraid creations instead of Creator? people will discuss u anyway. do everything for God's satisfaction not for people.

I think the word "God" should be removed from all posts in CF if there any post contains "God".

in the name of god

congratulations for your blog.

Mashallah! very good editorials! go on despite on people who don't like ur actions.

Many thanks for the wonderful editorials! I can tell how much efforts you put into this. Kudos guys!

Woah! Nice job!

I did Div2A simply with pow(1378,n,10) in python

pow(8, n, 10) is more simply

Two Hoses x and y are in the same friendship group if and only if there is a sequence of Hoses a1, a2, ..., ak such that ai and ai + 1 are friends for each 1 ≤ i < k, and a1 = x and ak = y.

what does this mean?

got it.

how ? i missed the point why you should use disjoint set ... can u explain? its a very poor description..

You don't have to use disjoint set, you can use any method of finding connected components. I used dfs.

in Div1-A why i have to take the LCM & why i am taking the (len / 2) when it is even ??

Consider two cycles, for one value of t is 3 and for other value of t is 2 then, the minimum number that satisfies condition of the problem is lcm of both. And for question of taking len/2, if you read last sample testcase in problem you'll understand it

thank you :)

So to answer your second question see this comment. It helped me out. For your first question lets consider two pairs of people: a and b, c and d. Let's say that to go from a to b you need a cycle of length 3 (a -> u -> v -> a) and to go from b to c you need a cycle of length 4 (b -> k -> l -> m -> b). If t was 4 then you could go from b to c but you would have also followed path a -> u -> v -> a -> u (which is not a cycle). Now you need minimum t such as after t moves you can complete some number of cycles. This is the LCM over all cycle lengths. For this example answer would be 12, doing 4 full cycles from a to b and 3 full cycles from b to c.

Hope I helped!

it's the minimum time so that i can fully complete any cycle , am i right ?

Absolutely!

Thank you very much :)

if i count maximum T it also satisfy all the cycles why not ? here is 4,3 in my vector . If i take 4 as a answer , it satisfy cycle which need 3 (4>3) , also the cycle with 4 (4==4) . So why i need LCM ?

"it's the minimum time so that i can fully complete any cycle " == taking maximum T also satisfy this , why i need LCM ?

You have to take exactly t steps. If the cycle has length = 3 and you take 4 steps you don't end up at the starting position.

Now if you consider the lcm of all the cycles, you will have the number of steps necessary to satisfy all of them (start at x and end at x). In your example (4 and 3), you should take 12 steps in order to end at the starting positions of both cycles.

Also, note that for even cycles you can go to the middle of it and use the same amount of steps to get back at the origin (you want to know the t necessary to go from x to y and from y to x), in odd cases you have to go through the entire cycle to get to a y that returns to x in the same amount of steps).

Since you want the minimum t, that implies that you need to divide the even cycles length by 2. (If you had cycles 4 and 3, you should use the lcm of 2 and 3 which is 6)

Hope that has cleared it up!

seriously?

we have two types of food, kooft and zahre-mar!!!! i'm from iran too

i couldn't stop laughing when i read that.

thanks mate, nice editorial. it helps a lot

mate quick editorials , thanks for that :)

in 741C, I believe you make an edge between 2i and 2i+1 for the constraint => in every 3 consecutive

`Among any three guests sitting on consecutive chairs, there was two of them who had different type of food.`

. But the constraint has more cases than 2i and 2i+1 are opposite. Should not there be a provision to check those cases also?But look that graph, if you try to bi-color it, you always will be able to bi-color it and for every 3 consecutive nodes its impossible that all 3 have the same color. Think, you have a-b and c, as a-b must have different color (cause you have an edge betwen them) you are respecting the rule. That's why you don't need other provision.

Yeah, we can bicolor following 2i and 2i+1. But there are other ways we can bicolor it without following 2i and 2i+1. I am asking, to either prove that we cant, or that it is not required

There are many solutions. So, there exist solutions in which 2*i and 2*i+1 might have same color for some i. But, we need to find anyone solution. The above construction gives one such solution.

But, if there is no solution for 2i and 2i+1, there may be other solutions which we ignore

There always exist solution for 2*i and 2*i+1. You need to give anyone solution.

Let me explain in other scenario. Question — "print any prime below 10^18". Answer — do you find all primes below 10^18, consider them and print one prime? No, you give anyone prime which works.

Also, now suppose you have figured out a way(given a magic function) which gives twin primes. You call this function, and give one of its values as your solution. One can argue, if there exist no twin primes below 10^18, then you are doomed. But we know that this magic function will work correctly. In other words, it will give one possible solution.

The above construction always give one such solution out of all possible solutions S.

Okay, actually my problem was that if there exists no solution. Then there might be more conditions which we could have checked. That is, if there graph constructed contains an odd cycle. But yeah, after you pointed it out,I saw an odd cycle is not possible. It was a nice solution, I hope I can come up with a solution like this some day.

I have the same doubt. Arpa please elaborate why your method is correct.

WOW , The best editorial until now

Good job bro :)

God bless you my brother :)

In Div2-D how can we consider only a memeber of group in our DP?

During DFS when you try to label each "vertices" (hos) to a connected components, you should also list down which vertices for each connected component contains

Then during the DP, iterate through all the list of vertices and try to take one vertices (we know our weight and beauty value, just like knapsack problem)

Hope it helps

fonmagnus

Can you please tell this in a little detail. I tried understanding accepted solutions but wasn't able to understand.

For each vertex, we can find out in which group that vertex belongs to (we can simply using DFS for labelling connected components). We also precompute the total of all weight and beauty im this group and store it in an array

andweightSum[k]beautySum[k]Let's say after the DFS we have the group of friends in group A that contains (A1, A2, ..., Ak), these vertices are belong to group A, so we list down these vertices in a vector that represents the list of vertices for each group.

After doing so, we can run a DP with two states : let's say

means we are currently evaluate theDP(pos,w)with a remaining weight of at mostgroup[pos]wIn our DP, the best solution can exists in any of these 3 alternatives :

Not take that group means we evaluate the next group

DP(pos+1,w)Take all of those group together

means we evaluate the next group with a new remaining weight and added with current group beauty (make sure our current weight is not less than this group weight).DP(pos+1,w-weightSum[pos])+beautySum[pos]Take only one of the hos in this group that produces the best solution. We dont know which hos is the best solution, so we iterate through each

hos in this group (by listing down the vertices list in a vector I've mentioned earlier, we simply can iterate through all of the list) this alternatives isi-thwhereDP(pos+1,w-weight[i])+beauty[i]andweight[i]each represents the weight and beauty for thebeauty[i]hos in our current group.i-thThen we just compare which one of those alternatives produces the best solution :)

I have a question,possibly a "dummy" one.

Is it possible that when we check for a whole group(the total amount of weight and beauty and if we manage to fit it inside our certain weight that somewhere (one) inside that group is better solution then the whole group? Im asking this because i failed test because of this and i couldnt understand why...After i found that a group can fit inside my DP[X][J] i never checked for 1 member inside that group and i just skipped it..It failed a test and after removing the else contidtion it passed...

Yes. Suppose that you have 7 hoses, such that 1,2,3,4 are friends and 5,6,7 are friends. Hoses in the first group have beauty 1, except for the hose 1, who has beauty 5. Each members} of the second group have beauty 2. All of the hoses weight 1, and the scenario can stand weight 4. Your algorithm will give as an answer 8 (take the whole first group), while the optimal answer is to take hose 1 and the second group.

Nice editorial. Enjoyed contest. Congrats to winners :) I could do Div2A in 30 seconds, but couldn't do other ones. Hope to see you on next contests.

I don't understand 741B (the dp parts). Can someone please explain the steps in a better order or maybe link a good solution?

edit: got it :)

I really respect your effort , BUT there is so much stuff in this tutorial that no body cares about :)

I am not trying to be offensive , Big thanks for your round and good tutorial :)

Anyway has anybody noticed that RIP (English and Well formed statements) in Div1 A , B

I find those unusual parts quite interesting actually.

The hints part is really cool and should exist in every editorial.

Well the intro , and preparation details , and that details section :D I don't know what's the point !

This guy is really proud of making this round (and he must be). But I think there must be something wrong , this is the round 383 and nobody ever wrote any of that stuff. you may find one part of them in few rounds. But this is kind of too much :D

for DIV2 — C is there a better solution using DP ?

http://codeforces.com/contest/742/submission/22769871

brother it got failed at test 61 , before posting here please check at least once .

brother .. i know that my answer fails at test 61

i'm asking for a hint to make my solution accepted using DP approach

thanks

One of the best written editorial on Codeforces

can someone tell me where is my code is wrong thanx in advance http://codeforces.com/contest/742/submission/22771264

please someone reply me

in your code :

ll lets_do(int ind, int wt) {

.....

I think it should be :

right ??

but here i m working on indexing and if i access an group or a single element from a group than next time i never select any element from that group

thanx i do it i slightly change my code ind to grp according to ur hint and its accepted thanx a lot

Very cool editorial and problem ideas! Thanks Arpa for the great Round

One of the best editorials I've ever seen! And this hint section is the best part!

Best editorial I've ever seen. Great job!

Arpa and _-_Sa1378_-_,

I found your mistake in task div2.B.

In statements was wrote 1 ≤ n ≤ 10^5. N could be 1. We need find pair, but if n == 1 answer will be 0.

But, you haven't any tests n == 1.

For example I thought that

My mistake, but got acceptedif ( n == 1 && x == d[1] ){ cout << 1; return 0; }

else if ( n == 1 ){ cout << 0; return 0; }

My solution is wrong but it passed.

`You was should add test when n = 1.`

This my my wrong , but accepted solution :P :

22750839

We didn't have test with n=73901 too...Sorry for this... :/

Okay, maybe it isn't mistake, but I just wanted to say that you should note this for future...

but still thanks for round.Min- and max-tests should always be included in the final tests. It often allows to fail some more solutions, while there are no drawbacks.

In Div 1 C, "This graph doesn’t have cycles with odd length". Doesn't this test case contradict?

2

1 3

2 4

The graph will have edges: 1-3 2-4 1-2 3-4

Does it have cycles with odd length?

Oh! I misunderstood the editorial. Thanks!

Actually it does not. Maybe you forget to connect vertice 2*n and vertice 1.

I made the same mistake, I think he connects every consecutive vertices.

I keep getting wrong answer in testcase 4 for 741b , why is the answer not 1710057 but 1495706?? can somebody explain? thx

try this test case: 10 5 100

64 90 3 94 96 97 52 54 82 31

796554 444893 214351 43810 684158 555762 686198 339093 383018 699152

6 8

8 3

3 9

2 3

10 3

This is the fastest tutorial in CF I'v seen.Thank you Arpa.

amd also publishes lightning fast editorials, and Arpa's his student :)

Best Editorial till date seen by me on codeforces. Thanks! Arpa

IN div2- C why i need to LCM of all length which are stored in the vector S , according to tutorial . I understand the fact n/2 for even but why need LCM , Can anyone explain ? . Please dont ignore .

If for one cycle, length is 3 but for another length is 2, Then you have to choose a value which satisfies both cycles. You cant choose t=3 because it wouldnt work for 2 cycle and vice-versa.

Therefore the smallest number to satisfy both of these cycles is the LCM.

Thanks understand it

Consider for example that we have two cycles :

of length 8 and 12.

So the considered value is : 4 and 6 ( because we have even number of nodes in the cycle, we consider n/2 in that case).

Now the LCM(4,6) = 12.

You can see that 12 satisfies for both the cycles.

If the cycle satisfies for t, it should also be satisfied for all multiples of t.

I explain it before here

Can you please explain the solution of Div1 D using centroid decomposition?

Link.

It says : We're sorry. You can't access this item because it is in violation of our Terms of Service.

It seems you are right and I'm so sorry : (

Please download the archive here, I'll fix the problem soon.

Can anyone further elaborate on Div2 Problem B? I didn't quite understand the solution.

I will explain you my approach:

you need to understand that: a xor b => x ; it means that: a => b xor x;

sort the array

imagine you fix a value a_i (1<=i<=n). you can use binary search in order to find the values such b xor a_i = x. ( Here you need b value. But b = a_i xor x. ).

Now you must realized that you are counting any pair twice. (Because you count a_i with a_j and a_j with a_i) that is why you need to divide the answer by 2.

Don't forget the constraint i<j. You must consider different positions.

I hope this helps you. (Sorry for my poor English)

Best editorial ever. Wish every future codeforces rounds have such editorials. Its always better read hints than to directly read the complete solution. Thanks arpa

I didn't get the solution of Div.2 B for this case.

6 2

1 1 1 3 3 3

so for this answer should be 9 as each of 1 can go with each of three but as per my understanding of the solution of the problem , We will first count the frequency of each input digit so in this case , frequency array will be ....freq[1]=3 , freq[3]=3

Then we will go through the frequency array and we will add corresponding element present at X Xor i place for each i of freq array... So in this case , 2 Xor 1 is 3 so ans=ans+freq[3]=3; then 2 Xor 3 is 1 so ans=ans+freq[1]=6; then we will divide it by 2 as suggested in solution so answer will be 3 but rather it should be 9.

I think I misunderstood the solution, If anyone finds the problem in my understanding then kindly help me out.

the answer is 0 because there is not any pair Ai and Aj (1<=i<j<=n) for which Ai XOR Aj = 1

Ohh ! Sorry I have made a mistake in writing that example consider X as 2 then It will be the question I am looking for! I updated it. Thanks.

Can anyone explain in div1 B, what is newDP and oldDP?

Copy the

dparray tooldDpbefore each group, then copynewDptodpwhen processing is done.A small trick in implementing this: instead of dumping away each oldDp array away each time, use it as the NewDp array right after the processing is done.

for example:

for i in range(X): j = i%2 dp[j] is currentDp dp[j^1] is newDp

For sure I know, but I had wrote that this way for simplify.

I only meant to hijack to post, in case if anzhu didn't know how to implement it w/o getting MLE. =P

And what is the biggest possible answer for div 2 C and what is the proof for this?

I think the biggest value is when we only have components of prime size.

Since the maximum number of vertices is 100, we can make a graph with components of size: (3,5,7,11,13,17,19,23)

and the LCM of everything is 3*5*...*23 == 111546435

EDIT: I was wrong.

Thank you very much for the contest, and of course for the editorial was very good explained.

Thank you for introducing hints in editorials. It's educational and does not need too much additional effort. I hope all authors follow this trend in the following contests.

In div1E, i wonder how to solve RMQ part in O(n) for each K?To each K less than n^0.5, i think we should build RMQ arrays.i can query in O(1),but how could i initialize RMQ arrays in O(n) for each K?

Read about it here (fifth method for solving LCA).

but sorry,this method works when the array is a binary one .but in div1E ,the array which need to be used ,i think, is not a bianry one.

Convert RMQ to LCA at first, then solve it with this technique. 22759852 can help as well.

Every RMQ problem is equivalent to a "reduced" RMQ problem that satisfies the required property. The idea is that RMQ is O(n)-equivalent to LCA, which is O(n)-equivalent to a reduced RMQ.

See https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/ for a complete explanation.

Can someone please explain Div2.B I am not able to understand it.

Brother , logic behind to solve the problem is that — A^B=C <=>A^C=B <=> B^C=A (you can verify it by taking some examples do this operation on their binary representation) — next task is you need to find the all the tuples such that i<j , Ai^Aj=x or(find all i such that Ai=Aj^x) you just need to find the count of Ai that present in the array before j index . (you can use count sort for this .)

let me know if you are not able to get it .

For reference you can check my solution : Solution Link

Bro, I am not able to understand the working of your loop. can you please give a better description of the loop.

I love this kind of Solution because of the hints.

Normally, Author only writes solutions down, it's not good to build a system of thinking.

I have to give you an up vote. :)

Hi Arpa, I could not find your blog for Arpa's Technique. My solution splits queries on K=20 and uses only sparse tables and is faster than your submitted solution on E. I wanted to know how your technique works (your blog is missing?).

Hi. I'll post that blog again now.

Link.

Still can't understand the Div2 D solution :C Can please someone explain it in detail? I mean I understand the solution of simple knapsack problem. I just don't realize how to use it properly in this problem.

check out my solution. its understandable.

In 0/1 knapsack, the choice of one item is "pick" or "not pick".

While in this question, there is some constrains that items in same group can only be picked mutual exclusively, or pick them all.

So it is much alike to 0/1 knapsack, except that now you have to handle it group by group, for each group, you can

For case 3, you can pre-compute and make an extra virtual item of sum(weight) and sum(beauty) for each group, so that it can be viewed as part of case 2 as well.

I was looking at few solutions for problem 741D like this one http://codeforces.com/contest/741/submission/22787904 but what i am not getting is how we are ensuring that the number of set bits is either 1 or 0 which is the required condition for ensuring whether palindrome word can be formed or not.

ans[i] = max(ans[i], x.second + maxHeight[x.first ^ (1 << b)] — 2 * h[i]);

like here we are seeking solution for subtree rooted at i then the quantity x.first^(1<<b) can have more than one bits set.

Can someone explain me this ?

This is my submission for Div.2 problem B.

I got WA on test 11 but it's too big to trace on paper, can anyone provide a smaller test that can hack my solution?

I've explained the reason, read Corner case #2.

You can download that test here or the full package here. Take a look to my code if needed.