### hloya_ygrt's blog

By hloya_ygrt, history, 6 years ago, translation,
Setter's code
Setter's code
Setter's code
Setter's code
Setter's code

• +123

 » 6 years ago, # |   0 Could anyone explain D to me again? I could not fully get the editorial.
•  » » 6 years ago, # ^ |   +4 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_ansThis 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
•  » » » 6 years ago, # ^ |   0 If we run DFS from every node, then it wouldn't be O(N) already right?
•  » » » » 6 years ago, # ^ |   0 No you don't have to run dfs from every node. It is mentioned in problem that 1 is the root ie the whole tree hangs on node 1 so just run dfs from node 1
 » 6 years ago, # |   +28 My solution to B is, the answer is the index of the right most bit 1 (1-based) in the k. 22954844I got this by solving some random values of n and k, but have no proof why this is correct :D, anyone knows why?!
•  » » 6 years ago, # ^ | ← Rev. 3 →   0 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)
•  » » 6 years ago, # ^ |   +3
•  » » 6 years ago, # ^ | ← Rev. 2 →   +4 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
•  » » » 6 years ago, # ^ | ← Rev. 3 →   +1 I did this with some beautiful observation, just three lines of code. check 22968081
•  » » » » 6 years ago, # ^ |   0 Check my solution to 22967686
•  » » » » » 4 years ago, # ^ |   -8 How did this solution strike you ?
•  » » » » 6 years ago, # ^ |   +1 beautiful indeed!
•  » » » » 6 years ago, # ^ |   0 Woah, that's pretty awesome! How did this solution strike you? What was your initial thought? I find that such solutions are really unintuitive :/
•  » » » » » 6 years ago, # ^ |   0 For me, I realized it in this way:Tried to obtain the first occurrence of k -> Realized it is related to 2^x -> noticed that they appears on a fixed interval -> try for some more corner cases -> code it
•  » » 6 years ago, # ^ |   0 if n=10 and k=12 then answer should be 0(right most bit of 12) how is this correct.
•  » » » 6 years ago, # ^ |   0 You need the rightmost set bit or 1 bit, not the rightmost bit
•  » » 6 years ago, # ^ |   0 if n=10 and k=12 then answer should be 0(right most bit of 12) how is this correct.
•  » » 6 years ago, # ^ |   0 I found out that number 1 2 3 4 5 start at 1 2 4 8 16... so I stored them in std::map. Then (k&-k) will be the answer. My AC submission
•  » » 6 years ago, # ^ | ← Rev. 3 →   +8 One line solution to B — 22997490
•  » » » 6 years ago, # ^ |   0 what this does ?
•  » » » » 6 years ago, # ^ |   +9 It uses a builtin function of the GCC compiler to calculate the position from the right of the first non-zero (1) bit in the binary representation of k. If you look at the way the sequence is generated , you'll find that this is equal to the number at k. This is much more efficient than implementing the algorithm on your own.Built-in Functions Provided by GCC
•  » » » » » 6 years ago, # ^ |   0 In particular, I think clz / clzll is the must learn one as it is very useful in handling bitmasks.As a guy who doesn't memorize a lot of commands, I used clz(x & -x) for this task instead.
•  » » » » 3 years ago, # ^ |   0 — Built-in Function: int __builtin_ffs (unsigned int x) Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero.
•  » » 5 years ago, # ^ |   0 I got it via a slight brute force over the solution space. Since the answer could be only from 1 to 50 given that n varies from 1 to 50.Each result can be formalized as a part of the Arithmetic Progression:k = 2 ^ (I — 1) + (m — 1) (2 ^ I)where I is the target number (1 <= I <= 50) and m is any arbitrary natural number satisfying the AP. Given an I, I check whether m is a valid natural number of not. See 27773567 for my solution.
 » 6 years ago, # |   +19 I have a bit different approach for problem E, which fits in the TL even when N is up to 10^6.The solution consists of tho phases. The problem is much easier if we can find such K that every element will be present either K or K+1 times. We can binary search to find it. Foreach step of step binary search, we will define dp[mask] as the smallest index of the sequence for which it is possible to have a sequence of number from mask ending on it. Updating this dp is quite easy, we just check all possible additions of the last element to our mask and binary searching on prefix sums the new interval.The second phase is as follows: we have the correct K found, so every number will be present either K or K + 1 times. Once again we will do bitmask dp, just considering all possible 28 cases this time and using the previous idea.Overall complexity: O(2K * K * logN * logN + 22K * K * logN)You can refer to my submission: 22976778
•  » » 6 years ago, # ^ |   0 isn't it just binary search on possible values of len?
•  » » 6 years ago, # ^ | ← Rev. 2 →   +10 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 * 2K).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 * 2k).
•  » » » 6 years ago, # ^ |   0 Sir I did not understand the binary search part how are u using binary search and for what purpose? I am a newbie it would be very helpful if you guide ?
•  » » » » 6 years ago, # ^ |   +4 Each number in the required sequence will be repeated x or x + 1 times.If there's a sequence with some x, then of course there's another sequence with x - 1. You can just delete one occurrence of each number from the first sequence to get the second one.Since you want to maximize the sequence length, you want to maximize x. And since the possibility of getting sequence with x is monotonic (i.e. it's true in some range [0, y) , and false in [y, OO) ), you can use binary search to get y.
•  » » » » » 6 years ago, # ^ |   0 Thanks a lot sir finally got accepted thanks a lot for help
•  » » » 17 months ago, # ^ |   0 Just a reminder that the binary search upper bound in the code should be n/8 instead of N/8...
 » 6 years ago, # |   +1 can someone explain to me how did we get those formulas for C?
•  » » 6 years ago, # ^ |   +1 2/n = 1/n + 1/nso, x = n; observe that, 1/y + 1/xy = 1/x if y = x+1;
•  » » 6 years ago, # ^ |   +8 2/n = 1/n + 1/nSo 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/zn != n + 1 for every nlet 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/zFinally 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
•  » » 6 years ago, # ^ |   -8 Here You can read here for more information :D. This is the website that I googled during the contest time.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 Why would someone use google during a competition?
•  » » » » 6 years ago, # ^ |   0 Well. I couldn't figure it out myself. I'm not blue like you :(. But are there any rules about google ? — If there are, I won't do it next time. !
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   +9 You CAN use the internet , as long as you don't copy-paste somebody else's code. It's perfectly within the rules of the contest. Also , you can consult any book , notes or code that you have personally written beforehand.See rules: Can-do's and Can't-do's : Point no. 3I don't know why these other people are downvoting you .. they seem to be under the impression that this is somehow unethical.
•  » » » » » 6 years ago, # ^ |   0 I think it's not a good way to improve your skills because you are not actually thinking about the problem. I think rounds should be the place where you try hard to solve the problems by your own. Anyway, that's just my opinion. Good luck!
•  » » » » » » 6 years ago, # ^ |   -7 I did try to solve the problem by myself. But in the end I couldn't come up with a solution. So I googled and found out about the formula. I submitted at 1:56. Sorry for using google.
 » 6 years ago, # |   0 How could i get the formula for C Mathematically ?
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 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)/bb = n+1Then, 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 ;)
•  » » » 6 years ago, # ^ |   0 ok i got it .so do u think in it like that or u brute forced and got the formula
•  » » » » 6 years ago, # ^ |   0 I thought like, "if we get x=n, then it's half the way done it. How can I get y and z that satisfies it?", then did some tests with n=2, 3, and then formalized it so that I would be convinced and could start coding it xD
•  » » 6 years ago, # ^ | ← Rev. 2 →   +6 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 is1/n = 1/x + 1/y -> 11/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*ntake a = 1 and b = n therefore x = n + 1 and y = n + n*n
•  » » » 6 years ago, # ^ |   0 Amazing but i can think in different way 2/n = 1/n + 1/n right if we make 1/x = 1/n it remains that we need to make 1/n = 1/y + 1/z so we need to make 1/n two parts so what is the first value less than 1/n it's 1/(n+1) so make one of them 1/(n+1) and the other is equal 1/n — 1/(n+1)
 » 6 years ago, # | ← Rev. 2 →   +5 For B just do F(k)=1 if k is odd, otherwise F(k)=F(k/2)+1, this will be O(logK).
•  » » 6 years ago, # ^ |   0 How could we get the formula ?
•  » » » 6 years ago, # ^ |   0 You can observe it after writing it down, for example with n=4, the positions of:1: 1, 3, 5, 7,...2: 2, 6, 10, 14,...3: 4, 12,...4: 8Now you should get the formula.
 » 6 years ago, # |   0 Question B has been tagged as bitmasks but what i did was something different. here is what i did . http://codeforces.com/submissions/logicbomb1#How to do it using bitmasks?
•  » » 6 years ago, # ^ |   0 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
•  » » » 6 years ago, # ^ |   0 thank you
 » 6 years ago, # |   +5 I thought that problem A was a SSSP problem. After reading the tutorial, I realised that it is indeed a trick. But what if we have 3, 4, 5... companies rather than 2? Are we able to use any simpler algorithm than dijkstra's?
•  » » 6 years ago, # ^ | ← Rev. 3 →   +3 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.
 » 6 years ago, # |   0 I found the problem statement of Div-2 D quite confusing. For the pretest-4Pretest-4-imageAns according to me should be 19 but ans is 6. Can someone please help me understand why we can't rope between ( 1 and 8 ) and then give 1 to second person ( 16 + 3 = 19 )
•  » » 6 years ago, # ^ |   0 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.
•  » » » 6 years ago, # ^ |   0 ok then also lets cut the rope between ( 8 and 10 ) and then between ( 1 and 8 ). Then A will get ( 4 + 3 + 2 + 2 -4 + 3 + 3 = 13 ) and ( 3 ) therefore sum = 16 and not 6. Please correct me if i am wrong
•  » » » » 6 years ago, # ^ |   +13 @saisumit : you cant cut the tree that way. Read the problem statement carefully:" they will choose prizes at the same time " [ You can't cut one part, and choose the next part later ]Also : " they decided to choose two different gifts so that the sets of the gifts that hang on them with a sequence of ropes and another gifts don't intersect "
•  » » 6 years ago, # ^ |   0 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.
 » 6 years ago, # | ← Rev. 2 →   0 Could someone plz clearly explain the problem statement of D, do we have to consider different subtrees i.e. can't we take a subtree and then take a subtree which consists of it's ancestor. For eg : — if input is like this32 2 21 21 3can we first take 3 and then the remaining subtree of size 2 so total answer is 6, or should we take only nodes 2 and 3. can't we choose two subtrees so that one of them contains the lowest ancestor of other.
•  » » 6 years ago, # ^ |   0 You have to pick 2 different subtrees A and B such that there is no common vertex between A and B.
 » 6 years ago, # | ← Rev. 2 →   0 For given constraints in E, I didn't use Binary Search and got AC.The complexity seems to be O(n2.2k), but I wonder whether all dp states would be useful here or not because the running time seems to be pretty fast even without binary search.
 » 6 years ago, # |   0 Can someone please explain me what is wrong with my solution for A. I have used the proper way to solve it which should be aaplicable even if two diffrent airports of type a and b were not adjacent to the destination airport.
•  » » 6 years ago, # ^ |   0 Is your soluntion working for this test case 10 1 10 0000011111???
•  » » » 6 years ago, # ^ |   0 Nopes. I have got my mistake.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +5 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
•  » » » 6 years ago, # ^ |   0 Thanks Bro, I got your point.
 » 6 years ago, # |   +1 Nice edition
 » 6 years ago, # |   +2 Can someone explain me the 743D — Chloe and pleasant prizes problem statement ???
 » 6 years ago, # |   +1 My solution for problem B 22969930 :D
•  » » 6 years ago, # ^ |   0 nice :D
 » 6 years ago, # | ← Rev. 2 →   +6 My solution for E is like O(8 * N + 8! * 2^8 * 8 * Log(N)). Did i win an asymptotic war?And it works for 8 seconds on my local machine with n = 10^7
•  » » 6 years ago, # ^ |   0 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 solutionTime complexity, where k is the variety of cards: O(log^2(N) * k! * C(k, k/2))
 » 6 years ago, # | ← Rev. 2 →   0 Deleted
 » 6 years ago, # | ← Rev. 2 →   0 Isn't the complexity for problem A, O(1) ? Why is it mentioned as O(n) ?
•  » » 6 years ago, # ^ |   0 Reading the input is O(n)
•  » » » 6 years ago, # ^ |   0 Forgive me if I'm being a little amateur here, but is reading a string of length n considered as O(n) or O(1)? We simply do a cin>>str , why would it be considered as O(n) ?
•  » » » » 6 years ago, # ^ |   +8 It can't magically read all the characters at once, it takes O(n) to read n characters.
•  » » » » » 6 years ago, # ^ |   0 Thank you for the clarification @tfg :)
 » 6 years ago, # |   +8 My one-line solution to B : 22997490It gives the position from the right of the first non-zero (1) bit. Using a builtin G++ function (that directly uses architecture-level instructions) to do this , is much more efficient.
•  » » 6 years ago, # ^ |   0 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 :)
 » 6 years ago, # |   0 How can the complexity of A be O(n) ?Shouldn't it be O(1)?
•  » » 6 years ago, # ^ |   0 Please read the other comments first.This one , in particular.
•  » » » 6 years ago, # ^ |   0 Sorry about thatThank you :)
 » 6 years ago, # |   0 I think test 27 is wrong here. The test case is the following- 10 5 8 1000001110 The jury's answer is 1. It should be two. According to me there are three possible cheapest ways to get to the destination. first is 5 to 6 then 6 to 8 price (8-6 =2) second is 5 to 7 then 7 to 8 price (7-5 =2) third is 5 to 10 then 10 to 8 price (10-8=2) my submission
•  » » 6 years ago, # ^ | ← Rev. 2 →   +10 Answer is 1. Go from 5 to 6. : Costs 0then 6 to 7 : Costs 1then 7 to 8 : Costs 0Total Cost : 1No 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.
•  » » » 6 years ago, # ^ |   0 Thanks I understood.
 » 6 years ago, # |   +18 sizeof(A's code) + sizeof(B's code) + sizeof(C's code) < sizeof(D's code)
 » 6 years ago, # |   0 Could you explain why the bitwise XOR works in problem A? I used a different logic though.
•  » » 6 years ago, # ^ |   0 1^1=0 0^0=0 0^1=1
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 Yes. But first we need to reach the nearest airport of the same company which is at a minimum distance to that of the other company; this minimum distance is the cost. But if only the company numbers 1s and 0s are XORed you'd always get either a one or a zero. But for that to be true, the cost must always be either 0 or 1.In that case I think it's possibly because 1. You never need more than two moves 2. The free ticket thing (which is I guess the bigger reason for this being true), am I right?But my naive solution from the contest used three times less memory than the XOR based approach, I don't know why.
•  » » » » 6 years ago, # ^ |   +1 There have to be two airports near each other from different companies. You can reach one of them with cost 0,next with cost 1 and the last that you need with cost 0. 0+1+0=1 that's all) And sorry for my bad English:)
•  » » » » » 6 years ago, # ^ |   0 Thank You, got it. Could you suggest a few tutorials for Graphs?
•  » » » » » » 6 years ago, # ^ |   +3 I would like to find it too
•  » » 6 years ago, # ^ |   0 there is more easy way , reading the two positions , if the have the same value (0,1) then it will be 0 cost, else is one ! for example if we say that number of airports are 6 , you are in the second palace , your distance is the last airport it it's represented like this : - 1 (1) 1 0 0 (0) you will fly to third one : cost = 0 1 1 (1) 0 0 (0) then you will fly to next : cost = 1 1 1 1 (0) 0 (0) then , they fly to last airport with no cost ! the total cost will be 1 .
 » 6 years ago, # |   0 Can someone please explain me the sample code 3 of problem E. (i didn't got the condition 2 satisfied for it.... as far as the condition is exampled in question 1122 and not 1221)... please.
•  » » 6 years ago, # ^ |   0 Conditions doesnt have to be satisfied in the original sequence, your task is to find the maximal subsequence, where they are satisfied.
•  » » » 6 years ago, # ^ |   0 but in that SAMPLE TEST CASE 3 of problem E there isn't any subsequence of length 17 which is like 555322288888811... the 8 is spread after every 2 integers
•  » » 6 years ago, # ^ |   0
 » 6 years ago, # |   0 Div 2D :- Can someone tell why this got AC D-AC but this didn't D-WA ? Although both of them do same thing ,ie find top two child values. Changes are only in dfs function.
•  » » 6 years ago, # ^ |   +6 typedef vector < int > vi; ... struct node{ ll data; ll m; ll sum; }; ... vi s; s.pb(val[graph[x][i]].m); 
•  » » » 6 years ago, # ^ |   0 Got it. Thanks :D
 » 6 years ago, # |   0 can anyone tell me why my code is not working on test case 15.: 23014828 code link:(http://codeforces.com/contest/743/submission/23014828)
•  » » 4 years ago, # ^ |   0 I was wrong at the test 15 too. Have you known the reason for that? If you know , please tell me ,thanks?
 » 6 years ago, # |   0 the problem is div 2d Chloe and pleasant prizes
 » 6 years ago, # |   0 D can be done in on single traversal code : http://codeforces.com/contest/743/submission/23016161
 » 6 years ago, # |   +8 Problem E is interesting, thanks!
•  » » 6 years ago, # ^ |   0
 » 6 years ago, # |   +1 In setter's code, I can't understand ~~~~~ amax(dp[in[k][it] + 1][j | (1 << k)], dp[i][j]); ~~~~~ mean ? Could anyone explain E to me again? I could not fully get the editorial
•  » » 6 years ago, # ^ |   0 amax is a funcion, that is trying to maximize some value. Extremely sorry for using this code-style in a solution written for public.
 » 6 years ago, # |   0 In E, I did not get the state represented by the dp. What exactly is the mask representing ? I found the editorial explanation insufficient.
•  » » 6 years ago, # ^ |   +3 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.
•  » » » 6 years ago, # ^ |   0 Thanks. That helped me get AC.
 » 6 years ago, # | ← Rev. 5 →   +1 D approach:For a node i let ai be its pleasantness. Let where {h1, h2, ..., hn} are the children of i and let ci = max(bi, bh[1], bh[2], ..., bh[n])We compute each node bi and ci with a o(n) recursive dfs.Now we'll find the solution of the sub-graph that contains a node (any) i as root. Denote this procedure dfs(i)Case 1: the node i is the only node of the graph. Then it is impossible to generate a pair (that is the solution)Case 2: the node i has only one child. Then the solution will be dfs(h1)Proof: we can't choose i, in the case we do: we select the root => we can't select another node => we can't make a pair. So we need to choose another node, the solution will be inside the sub graph of the only child. dfs(i) will contain the same pair solution (if it exist) that i should holdCase 3: the node i has two or more children. Now things get more interestingLet max1, max2 be the child with 1st and 2nd greater ci respectively. They will always exist as there are two or more children.now, we need a key observation There is an optimal solution that don't use both nodes outside max1 subgraph Proof: any solution that do so can replace one of its two elements with a node inside sub-graph max1 that will be always greater or equal that any node outside max1So there are two chances The optimal solution uses one node inside max1 and one outside (1) The optimal solution uses two nodes inside max1 (2) in the case (1) we will set the solution as cmax1 + cmax2 The sum of the two greater nodes of max1 and max2. in the case (2) we cant set the solution as cmax1 because the two nodes lie inside max1. So we compute dfs(max1).As we can do any of the two cases, then we compute both and we return the max value of them. (of course if dfs(max1) has no solution then we use only the case (1))Total complexity: O(n)
•  » » 6 years ago, # ^ |   0 look at my code i m not getting the error http://codeforces.com/contest/743/submission/23025516
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 The result is the selection of the ci of two nodes, But ci of each node references to bi of some node (the greater in the sub-graph)And bi is the sum of up to n ai values.n <  = 109ai <  = 109then bi <  = 109 * 109 = 1018change 'int' with 'long long' :) 23047937
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 thanks i took 24 hr to figure it out :(
 » 6 years ago, # |   0 does anyone has a mathematically clear prove for the C problem cause i can't find any online.
 » 6 years ago, # |   0 I am not able to understand the problem D Div2 !! Can someone help me and explain it in some better way?
 » 5 years ago, # |   0 My solution for B http://codeforces.com/contest/743/submission/22967882 :DD
 » 5 years ago, # |   0 I have managed to solve problem B unofficially by pen and paper, then got an algorithm ll getAns(ll n) { ll ans = log2(n); ll ta = pow(2, ans); if(n == ta) return ans; else return getAns(n - ta); } The answer is getAns(k)+1; Please someone tell me how can I determine its complexity.
 » 4 years ago, # |   0 What is the way to search for solutions to C, if you couldn't come up with the brilliant factorisation ?
 » 4 years ago, # |   0 Why is https://ideone.com/fWLX8s WA ? div2d
 » 3 years ago, # | ← Rev. 2 →   0 Problem D can be done without using extra space my solution
 » 2 years ago, # |   0 https://codeforces.com/contest/743/submission/86323255 A simple way of doing b is to simply count the power of 2 in k and print it by incrementing one ... eg — for 18 = 2^1 * 3^2 .. ans is 2 do have a look at the solution.
•  » » 23 months ago, # ^ |   0 Wow! how did you observe it and guess it?
•  » » » 23 months ago, # ^ |   0 Just tried relating the position with the sequence
 » 21 month(s) ago, # |   0 if anyone has solved 2nd que using recursion,give ans link in comment section.
 » 21 month(s) ago, # |   0 B) Can some explain why my solution gone wrong in test case 5 and why it is printing >. 94955731 Thanks in advance :)
 » 17 months ago, # | ← Rev. 2 →   0 1