### Arpa's blog

By Arpa, history, 8 years ago,

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

I’m preparing harder version of some of the 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:

On 25 May Batman came up with problem Div.1 D and other problems authored inchmeal.

9/25/16: Proposal sent to Gleb.

11/12/16: Answer from Gleb: Your proposal has been redirected to Nikolay KAN.

11/15/16: Nikolay has replied, and commented about problems, saying some problems are easy, some are hard, some are ok.

I changed some of the problems, change the constraints for some others and we talked about solutions through email.

11/17/16: We switched to Telegram.

Creating tests, writing generators, writing statements, etc started in the Polygon.

12/06/16: Round #383 hold.

gKseni told me how you want to get your money and I had no idea.

gKseni told me that it is possible to transfer my money and finally May 4, 2017, I received my money through Okpay.

I have another problem set to prepare another div.1 + div.2 round, but I haven’t enough time now :(.

Paintings in problems were suggested by me, painted by Batman 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).

I used Google Docs for writing everything.

 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 Batman 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 the last digit of 1378n 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 maskv 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 the problem becomes easier, solve the new problem with sqrt decomposition.

# Details

Div.2 A

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

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

Div.2 B

Idea, authoring, solution by Batman, preparation by Batman 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 Batman, preparation by Batman and me.

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

Div.1 D:

Idea by Batman, 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 the below poem by Hafez:

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

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

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

• +438

| Write comment?
 » 8 years ago, # |   +28 Nice Editorials
 » 8 years ago, # |   +54 Arpa Best editorial I have ever seen till now in Codeforces :D
 » 8 years ago, # | ← Rev. 3 →   0 In Div2C why if there is a cycle of even length we add len / 2 to S?
•  » » 8 years ago, # ^ |   +4 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)
•  » » » 8 years ago, # ^ |   0 That makes sense. Thank you very much!
•  » » » 8 years ago, # ^ |   0 Got your Point ... I don't understand Why the answer is the LCM of all the length ?
•  » » » » 8 years ago, # ^ |   +3 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)
•  » » » 8 years ago, # ^ |   0 Could someone please explain with an example as to why Len/2 operation is being done
•  » » » » 8 years ago, # ^ |   0 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.
 » 8 years ago, # |   +18 Good contest... but, can anyone explain better the solution for Div1C problem? I can't understand the editorial... Thanks
•  » » 8 years ago, # ^ | ← Rev. 2 →   +25 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...
•  » » » 8 years ago, # ^ |   +13 Сan you explain, why problem has no solution, if there is no solution in this graph, please?
•  » » » » 8 years ago, # ^ |   +10 You can always color the vertices by two colors in that graph so the main problem has always a solution too...
•  » » » » 8 years ago, # ^ |   +5 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!
•  » » » 8 years ago, # ^ |   0 We can have a different coloring if we put edges between 2-3,3-4,...,(2n-1)-(2n),(2n)-1Shouldn't we check for both the graphs? Thanks
•  » » » » 8 years ago, # ^ |   0 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.
 » 8 years ago, # |   +40 The style of your editorial is great.
 » 8 years ago, # | ← Rev. 2 →   0 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.
 » 8 years ago, # |   +54 Very nice idea to add hints to the editorial.
 » 8 years ago, # |   +4 anyone else solved div2 A using bigmod? :v
•  » » 8 years ago, # ^ |   +1 Me... And when I was trying to hack I found more guys like us.
•  » » 8 years ago, # ^ |   +16 print pow(1348, n, 10) # python 
•  » » » 8 years ago, # ^ |   0 I used it too, Python _/_
 » 8 years ago, # |   -17 I will get some money for using my name or its idea :| .
•  » » 8 years ago, # ^ |   0 You are getting some minuses instead :P
•  » » » 8 years ago, # ^ |   -9 Heh you're so funny :|
 » 8 years ago, # |   +257 This is maybe the best editorial I've seen. Though, I don't see why you use religion quotes on this website.
•  » » 8 years ago, # ^ | ← Rev. 2 →   -71 Thanks. Why not? My purpose is to show other people our literature.EDIT I had misunderstand meaning of word "religion", I thought your mean is the poems in the post.
•  » » » 8 years ago, # ^ |   +136 You start some of your blogs with "in the name of God". It looks like it isn't about showing the literature.
•  » » » » 8 years ago, # ^ |   -54 Why not? Anyone has some beliefs, and I believe in "Anything which doesn't starts with "In the name of God" is incomplete"
•  » » » » » 8 years ago, # ^ |   +84 Let's move to private messages, shall we?
•  » » » » » » 8 years ago, # ^ |   +45 I'm very sorry for doing this. I'll remove "In the name of God" from my blogs now.
•  » » » » » » » 8 years ago, # ^ |   -25 But why? I thought it was good :)
•  » » » » » » » 8 years ago, # ^ |   0 would you mind telling us why?maybe i remove it from my comment...
•  » » » » » » » » 8 years ago, # ^ |   +63 As Errichto said, "neutral websites like CF should avoid discussions about religion because it's unrelated to competitive programming and can only divide people".
•  » » » » » » » » » 8 years ago, # ^ |   -39 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.
•  » » » » » » » » » 8 years ago, # ^ | ← Rev. 2 →   -60 پس شما باید قبول کنی که تو کدفرسس کار ناقص انجام میدیدر ضمن ما با به نام خدا گفتن میگیم خدایا حتی به موقع کد زدن هم به فکرت هستممورد سوم کدی که میزنیم از خداست و به همراه اعتقاد با خداست و برای خداستپس ما اینجا فقط به نام خدا نمیگیم بلکه تمام اعتقادات و اهدافمون رو داریم میگیمچطور میشه که داستان های کودکانه گفتن منافاتی با مسابقه ندارند ولی به نام خدا گفتن منافات دارهاگر امروز این رو از دستت بگیرن فردا تمام اعتقاداتت رو از دستت میگیرن
•  » » » » » » » » » 8 years ago, # ^ |   -25 به خاطر لحنم ازت معذرت میخوامامیدوارم بهترین تصمیم رو بگیری
•  » » » » » » » » » 8 years ago, # ^ | ← Rev. 2 →   +26 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.
•  » » » » » » 8 years ago, # ^ |   +3 I think the word "God" should be removed from all posts in CF if there any post contains "God".
•  » » » » » 8 years ago, # ^ |   -42 in the name of godcongratulations for your blog.
 » 8 years ago, # |   0 Many thanks for the wonderful editorials! I can tell how much efforts you put into this. Kudos guys!
 » 8 years ago, # |   0 Woah! Nice job!
 » 8 years ago, # | ← Rev. 2 →   0 I did Div2A simply with pow(1378,n,10) in python
•  » » 8 years ago, # ^ |   0 pow(8, n, 10) is more simply
 » 8 years ago, # |   0 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?
•  » » 8 years ago, # ^ |   +3 got it.
•  » » » 8 years ago, # ^ |   0 how ? i missed the point why you should use disjoint set ... can u explain? its a very poor description..
•  » » » » 8 years ago, # ^ |   0 You don't have to use disjoint set, you can use any method of finding connected components. I used dfs.
 » 8 years ago, # |   0 in Div1-A why i have to take the LCM & why i am taking the (len / 2) when it is even ??
•  » » 8 years ago, # ^ |   +3 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
•  » » 8 years ago, # ^ | ← Rev. 4 →   +8 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!
•  » » » 8 years ago, # ^ |   0 it's the minimum time so that i can fully complete any cycle , am i right ?
•  » » » » 8 years ago, # ^ |   +8 Absolutely!
 » 8 years ago, # |   0 mate quick editorials , thanks for that :)
 » 8 years ago, # |   +4 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?
•  » » 8 years ago, # ^ | ← Rev. 2 →   +3 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.
•  » » » 8 years ago, # ^ |   0 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
•  » » » » 8 years ago, # ^ | ← Rev. 2 →   +3 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.
•  » » » » » 8 years ago, # ^ |   0 But, if there is no solution for 2i and 2i+1, there may be other solutions which we ignore
•  » » » » » » 8 years ago, # ^ | ← Rev. 4 →   0 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.
•  » » » » » » » 8 years ago, # ^ |   +1 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.
•  » » 8 years ago, # ^ |   0 I have the same doubt. Arpa please elaborate why your method is correct.
 » 8 years ago, # |   0 WOW , The best editorial until now Good job bro :)
 » 8 years ago, # |   +1 God bless you my brother :)
 » 8 years ago, # |   +1 In Div2-D how can we consider only a memeber of group in our DP?
•  » » 8 years ago, # ^ |   0 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 containsThen 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
•  » » » 8 years ago, # ^ |   0 fonmagnusCan you please tell this in a little detail. I tried understanding accepted solutions but wasn't able to understand.
•  » » » » 8 years ago, # ^ | ← Rev. 3 →   +4 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 weightSum[k] and 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 DP(pos,w) means we are currently evaluate the group[pos] with a remaining weight of at most 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 DP(pos+1,w-weightSum[pos])+beautySum[pos] 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). 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 i-th 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 is DP(pos+1,w-weight[i])+beauty[i] where weight[i] and beauty[i] each represents the weight and beauty for the i-th hos in our current group. Then we just compare which one of those alternatives produces the best solution :)
•  » » » » » 8 years ago, # ^ |   0 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...
•  » » » » » » 8 years ago, # ^ |   0 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.
 » 8 years ago, # |   +1 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.
 » 8 years ago, # | ← Rev. 3 →   0 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 :)
 » 8 years ago, # |   +31 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
•  » » 8 years ago, # ^ |   +75 I find those unusual parts quite interesting actually.
•  » » » 8 years ago, # ^ |   +18 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
 » 8 years ago, # |   0 for DIV2 — C is there a better solution using DP ? http://codeforces.com/contest/742/submission/22769871
•  » » 8 years ago, # ^ |   0 brother it got failed at test 61 , before posting here please check at least once .
•  » » » 8 years ago, # ^ |   +5 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
 » 8 years ago, # |   +11 One of the best written editorial on Codeforces
 » 8 years ago, # |   -10 can someone tell me where is my code is wrong thanx in advance http://codeforces.com/contest/742/submission/22771264
•  » » 8 years ago, # ^ |   -13 please someone reply me
•  » » » 8 years ago, # ^ |   0 in your code :ll lets_do(int ind, int wt) { if (ind > n) return 0; if (dp[ind][wt]) return dp[ind][wt]; .....I think it should be : if (ind > gp ) return 0; right ??
 » 8 years ago, # |   0 Very cool editorial and problem ideas! Thanks Arpa for the great Round
 » 8 years ago, # |   0 One of the best editorials I've ever seen! And this hint section is the best part!
 » 8 years ago, # |   0 Best editorial I've ever seen. Great job!
 » 8 years ago, # | ← Rev. 2 →   +11 Arpa and Batman, 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
•  » » 8 years ago, # ^ |   -40 We didn't have test with n=73901 too...Sorry for this... :/
•  » » » 8 years ago, # ^ | ← Rev. 2 →   +15 Okay, maybe it isn't mistake, but I just wanted to say that you should note this for future... but still thanks for round.
•  » » » 8 years ago, # ^ |   +55 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.
•  » » 7 years ago, # ^ |   -26 Excuse me, I accept my mistake.
 » 8 years ago, # |   0 In Div 1 C, "This graph doesn’t have cycles with odd length". Doesn't this test case contradict?21 32 4
•  » » 8 years ago, # ^ |   +3 The graph will have edges: 1-3 2-4 1-2 3-4Does it have cycles with odd length?
•  » » » 8 years ago, # ^ |   0 Oh! I misunderstood the editorial. Thanks!
•  » » 8 years ago, # ^ |   +3 Actually it does not. Maybe you forget to connect vertice 2*n and vertice 1.
 » 8 years ago, # | ← Rev. 3 →   0 I keep getting wrong answer in testcase 4 for 741b , why is the answer not 1710057 but 1495706?? can somebody explain? thx
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 try this test case: 10 5 10064 90 3 94 96 97 52 54 82 31796554 444893 214351 43810 684158 555762 686198 339093 383018 6991526 88 33 92 310 3
 » 8 years ago, # |   0 This is the fastest tutorial in CF I'v seen.Thank you Arpa.
•  » » 8 years ago, # ^ |   0 PrinceOfPersia also publishes lightning fast editorials, and Arpa's his student :)
 » 8 years ago, # | ← Rev. 2 →   0 Best Editorial till date seen by me on codeforces. Thanks! Arpa
 » 8 years ago, # |   0 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 .
•  » » 8 years ago, # ^ |   0 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.
•  » » 8 years ago, # ^ |   0 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.
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 I explain it before here
 » 8 years ago, # |   +23 Can you please explain the solution of Div1 D using centroid decomposition?
•  » » 8 years ago, # ^ |   +5 Link.
•  » » » 8 years ago, # ^ |   +1 It says : We're sorry. You can't access this item because it is in violation of our Terms of Service.
•  » » » » 8 years ago, # ^ |   0 It seems you are right and I'm so sorry : (Please download the archive here, I'll fix the problem soon.
•  » » » » 7 years ago, # ^ |   -26 Finally, I moved files from Google drive to Mega.nz, now you can see the solution you wanted here -> dokhtar-kosh-tree_HellKitsune.cpp.
 » 8 years ago, # |   0 Can anyone further elaborate on Div2 Problem B? I didn't quite understand the solution.
•  » » 8 years ago, # ^ |   0 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
 » 8 years ago, # |   +6 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
 » 8 years ago, # | ← Rev. 3 →   0 I didn't get the solution of Div.2 B for this case.6 21 1 1 3 3 3so 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]=3Then 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.
•  » » 8 years ago, # ^ |   0 the answer is 0 because there is not any pair Ai and Aj (1<=i
•  » » » 8 years ago, # ^ |   0 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.
 » 8 years ago, # |   0 Can anyone explain in div1 B, what is newDP and oldDP?
•  » » 8 years ago, # ^ |   0 Copy the dp array to oldDp before each group, then copy newDp to dp when processing is done.
•  » » » 8 years ago, # ^ |   0 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
•  » » » » 8 years ago, # ^ |   0 For sure I know, but I had wrote that this way for simplify.
•  » » » » » 8 years ago, # ^ |   0 I only meant to hijack to post, in case if zhussupov didn't know how to implement it w/o getting MLE. =P
 » 8 years ago, # |   +15 And what is the biggest possible answer for div 2 C and what is the proof for this?
•  » » 8 years ago, # ^ |   +8 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
•  » » » 8 years ago, # ^ | ← Rev. 2 →   0 EDIT: I was wrong.
 » 8 years ago, # |   +30 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.
 » 8 years ago, # |   0 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?
•  » » 8 years ago, # ^ |   +5 Read about it here (fifth method for solving LCA).
•  » » » 8 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » 8 years ago, # ^ |   0 Convert RMQ to LCA at first, then solve it with this technique. 22759852 can help as well.
•  » » » » 8 years ago, # ^ |   0 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.
 » 8 years ago, # |   0 Can someone please explain Div2.B I am not able to understand it.
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 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
 » 8 years ago, # |   +15 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. :)
 » 8 years ago, # |   0 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?).
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 Hi. I'll post that blog again now.Link.
 » 8 years ago, # | ← Rev. 2 →   0 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.
•  » » 8 years ago, # ^ |   0 check out my solution. its understandable.
•  » » 8 years ago, # ^ | ← Rev. 4 →   0 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 Not pick any items in this group at all: dp[group_i][W] = dp[group_i-1][W] Pick either one item in this group Pick ALL items in this group 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.
 » 8 years ago, # |   0 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<
 » 8 years ago, # |   0 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?
•  » » 8 years ago, # ^ |   0 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.
 » 4 years ago, # |   0 i am getting wrong on test case 56 for my solution of DIV2 D .http://p.ip.fi/b8Ob
 » 3 years ago, # |   +2 best editorial
 » 3 years ago, # |   -8 Div. 1 D and E are shit problems I must say. Div. 1 C is kinda neat though