Problem : https://cses.fi/problemset/task/1674/
Code 1 : https://hastebin.com/dahepocuke.java
Code 2 : https://hastebin.com/ayomexiwez.java
Both code give TLE on 1 large testcase , any optimisation to AC ?
-is-this-fft- wrote a beautiful comment -> https://codeforces.com/blog/entry/86315?#comment-742365. Got good sheer of votes. Bitcoin is now at 40722 as i write this answer. I feel more sad for those stupid people who upvote by seeing the color of handle without even knowing what they are even talking about. Good luck stupid people. Herd following is best seen on Stupid CP sites.
As there are so many indians with grey-green rating , there should be seperate rating without grey-green indians so that people know where they actually stand and not inflated ratings.
Mike please consider my request regarding this.
Hi everyone i am planning to do live stream on yt.
If anyone is interested please comment topic which you want the stream to be (dp,segtree,anything related to cp). I would select some good quality problems and will solve them live , answering any doubts. I will do stream for any number of audience as it's mostly to brush up my own skills. So i would be doing this coming weekend, till then lemme know if anyone is interested and which topic stream should be based on. Personally i would like to do some dp and segment tree problems, but if people in comments want something else it will be changed.
Hopefully we both can learn something from each other in the stream. :)
Hi i wrote a program that will automatically get test cases from the site and run your program against them and validate them against the output.
Just made it so can be buggy, all suggestions are welcomed.
Clone from here : https://github.com/medhruv7/Codeforces-test-cases.git
Also read the readme.txt before working with it.
Looking for feedback.
If someone wants a demo write in comments i'll add video or screenshots.
I gave GCJ and didn't make to next round bcoz i failed last test set of problem B.
Can someone tell me the reason i get MLE. I don't even use any memory or i am missing something
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.
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
Can someone tell why the first submission TLE on TC 10
I got RE with submitting in c++17 and same code AC in c++14. Why is it so can someone help.
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.
Thanks in advance.
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
Thanks in advance.
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.
Problem Link: https://codeforces.com/contest/1187/problem/E
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 = sz + dp + dp (sz = 9)
Now what all will change if we root the vertex 1 instead of 2 ?
Firstly lets deal with the changes of vertex 2 . Its size changes and it's dp changes so dp -= dp (we remove the left subtree's contribution here) dp -= sz (remember that size also contributed in the inital answer so we need to remove it now) sz -= sz (remove the size finally , dont update this before updating dp 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 += dp dp += sz (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
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). So if dp was 1 answer is last element (that is k)
If dp 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 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
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 = 2 as we could in case of max
so here dp = 3+2
and answer becomes 5-5+1 = 1.
Hope this helps .
Upvote if this helped :)
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.