### once_twice's blog

By once_twice, history, 6 weeks ago, ,

In a recent Div3 F : https://codeforces.com/contest/1311/problem/F

i made a submission with segtree of size 4*(number of distinct velocity) https://codeforces.com/contest/1311/submission/71877885

it got RE

Then i made segtree of size max it can go i.e 1e6 and it AC https://codeforces.com/contest/1311/submission/71878460

Can someone tell why 4*size is not enough in this case.

• +6

By once_twice, history, 3 months ago, ,

I tried to implement recent div2B with as optimised constant as i could. Can someone tell why my solutions TLE. It Tled 7 times in contest. I tried many approaches

eg submissions

https://codeforces.com/contest/1287/submission/68278756

https://codeforces.com/contest/1287/submission/68277154

Can someone tell why the first submission TLE on TC 10

• -1

By once_twice, history, 3 months ago, ,

I got RE with submitting in c++17 and same code AC in c++14. Why is it so can someone help.

• +6

By once_twice, history, 6 months ago, ,

I recently gave a test in which there was this classic Dp problem.

Given some stairs you need to reach Ath stair and you are currently standing on ground (0th stair)

You can do 3 things take 1step,2step,3step

But catch is you can take 1,2 step as many times as you want but the number of time you can make 3step move is only B.

Now we need to tell how many ways there are to reach the Ath stair.

Give Answer mod 1e9 + 7

Constraints A <= 1e5 , B <= 20

I was not able to do it, if someone could provide a working code for it that would be great.

• +5

By once_twice, history, 7 months ago, ,

I was doing a problem on Hackerearth contest, it was similiar to a problem i solved in one of the codeforces round but was more difficult than that.

Problem : We start from nothing. There are 4 type of queries -> 1. A x -> adds element x in array 2. I x -> increases value of all elements in array A by x 3. D x -> decreases value of all elements in array A by y 4. P k -> print the kth greatest element in the array so far

I don't remember the constraints but they were large enough that brute force won't work.

I know these types of problems can be solved by using suffix array for updating values and i tried that but couldnt figure out how to handle the query of type 4.

Any help would be appreciated

• +10

By once_twice, history, 7 months ago, ,

If any like me get this error while importing the Pbds in #includes..

I got error importing this -> #include<ext/pb_ds/assoc_container.hpp> Error was "cannot open source file hash_standard_resize_policy_imp.hpp ".

Fix go to the dir -> C:\MinGW\lib\gcc\mingw32\8.2.0\include\c++\ext\pb_ds\detail\resize_policy

There u will see a file similar to -> "hash_standard_resize_policy_imp.hpp0000644"

Rename it to hash_standard_resize_policy_imp.hpp

and now it worked for me .

I don't know the real reason why the file was weirdly name before if someone knows plz comment down below and tell.

Hope this helps.

• +9

By once_twice, history, 9 months ago, ,

I am writing this blog partly because i wanna rethink what the solution is and partly it may help someone. So we are given a graph and we need maximum points by choosing white vertices. Obvious greedy approach to this would be to take the root add points gained by it, then take the children (as this would give the maximum points greedily) and add their points to the contribution and so on. Now the problem is we can't tell which root will be giving us an optimal answer. Also according to the input size given we cant run dfs separately for each vertex. So thus we need an observation to reduce the time complexity so that we can get Accepted. Observation:

Re rooting the vertex of the graph to any of its children only changes few things and this is the main observation needed to solve this problem. Below i choose a graph :

here i will start by choosing 2 as my root. So consider how we can get the max points here. Points by root = N(all the nodes) + points by child 1 + points by child 6.

So we can use dp to get points of children and the answer becomes dp[2] = sz[2] + dp[1] + dp[6] (sz[2] = 9)

Now what all will change if we root the vertex 1 instead of 2 ?

Let's see

Firstly lets deal with the changes of vertex 2 . Its size changes and it's dp changes so dp[2] -= dp[1] (we remove the left subtree's contribution here) dp[2] -= sz[1] (remember that size also contributed in the inital answer so we need to remove it now) sz[2] -= sz[1] (remove the size finally , dont update this before updating dp[2] due to obv reasons)

Now we have successfully dealt with the changes in the vertex 2 so now we can get the answer with tree rooted at 1 by updating it's previous values as follows dp[1] += dp[2] dp[1] += sz[2] (Because now the size of 1 is no longer just 3 but 9 as its our new root so we update that too.)

This way we can check for each vertex the max points we can get and then finally choose maximum among all of them.

Hope it Helped.

If it did plz upvote :p

• +46

By once_twice, 12 months ago, ,

Wasnt able to get D in the contest . And Thought editorial was also confusing so trying to explain If i am wrong somewhere plz mention

I understood using the following code https://codeforces.com/contest/1153/submission/52692393

In the code we are setting first of all all the leaves to 1

Then for max we will take the min from all the dp of the childeren and for min we will add the dp of all the children

How i thought of this was dp[v] is basically how many numbers from the last can be allowed to pass to the top (root).

This is because we will be subtracting the result from k (k-dp[1]+1). So if dp[1] was 1 answer is last element (that is k)

If dp[2] Then basically second last element (that is k-1).

So if min was there will have to go to number from the last of k by adding all the children dp.

But if we have max we can just stop to the min of all children (so that k-dp[1]+1 will be maximum as dp[v] taken was minimum)

Take this tree for eg

Here mark all child as 1 so we are saying that we can take last 1 element from end of (1...k) . That is k itself.

Now as there is min in left we add 1+1+1 . What this means is that the best we can do is take last 3rd from (1...k) that is k-3+1. Similiarly for right part we add 1+1 that is best we can do is take k-2+1.

Now comes the root

Suppose if the root was max then we have 2 options

1. Take last 3rd from (1..k)
2. Take last 2nd from (1..k)

So best will be to take 2

That is the reason we are taking min(dp of all children so that in the end we will get a max) answer.

Now if the root was min there is no choice but to take 2+3 rd element from the end. we cant stop at taking just dp[1] = 2 as we could in case of max

so here dp[1] = 3+2

and answer becomes 5-5+1 = 1.

Hope this helps .

Upvote if this helped :)

• +14

By once_twice, history, 12 months ago, ,

Want to make a list of all the interesting questions that i find very interesting logic questions Plz add in comments more

• +4

By once_twice, history, 15 months ago, ,

Given Number = n To check kth bit set or not To Do 1. int temp = 1<<(k-1) (if u assume LSB to be 1 then use k-1 otherwise if assume 0 use k) 2. AND temp with n 3. If result is non-zero then set otherwise not set.