CP_Sucks's blog

By CP_Sucks, history, 3 years ago, In English

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 ?

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By CP_Sucks, history, 3 years ago, In English

Problem : https://cses.fi/problemset/task/1635/

My solution : https://hastebin.com/udicetufuy.java

Is there any more optimisation i can make to AC it ?

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By CP_Sucks, history, 3 years ago, In English

Hi i can someone tell how can i overcome TLE in this problem using java

Problem : https://cses.fi/problemset/task/1164/

My Solution : https://hastebin.com/ilexoqukuw.csharp

Full text and comments »

  • Vote: I like it
  • -17
  • Vote: I do not like it

By CP_Sucks, history, 3 years ago, In English

-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.

Full text and comments »

  • Vote: I like it
  • -50
  • Vote: I do not like it

By CP_Sucks, history, 3 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • -23
  • Vote: I do not like it

By CP_Sucks, history, 4 years ago, In English

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. :)

Full text and comments »

  • Vote: I like it
  • -35
  • Vote: I do not like it

By CP_Sucks, history, 4 years ago, In English

Hi i am starting to use intellij from toady , can someone tell me how to use the chelper. i am getting this error. Error: Could not find or load main class net.egork.chelper.tester.NewTester

Full text and comments »

  • Vote: I like it
  • -3
  • Vote: I do not like it

By CP_Sucks, history, 4 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +18
  • Vote: I do not like it

By CP_Sucks, history, 4 years ago, In English

Can someone tell why i get MLE in Problem D of last round ?

https://codeforces.com/contest/1363/submission/82256919

Thanks in advance.

Full text and comments »

  • Vote: I like it
  • +3
  • Vote: I do not like it

By CP_Sucks, history, 4 years ago, In English
  • Vote: I like it
  • +6
  • Vote: I do not like it

By CP_Sucks, history, 4 years ago, In English

Mike i might sound a bit toxic but i feel pikemike should not be allowed to set problems.

Thanks

Full text and comments »

  • Vote: I like it
  • -47
  • Vote: I do not like it

By CP_Sucks, history, 4 years ago, In English

Is there any limit to the length of the string after which hashing should be avoided. Also can the hashing solutions be easily hacked in contests ?

Full text and comments »

  • Vote: I like it
  • -14
  • Vote: I do not like it

By CP_Sucks, history, 4 years ago, In English

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

Question Link: https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd74/00000000002b1353 Solution: https://hastebin.com/wejoyikoke.m

Full text and comments »

  • Vote: I like it
  • -5
  • Vote: I do not like it

By CP_Sucks, history, 4 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +6
  • Vote: I do not like it

By CP_Sucks, history, 4 years ago, In English

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

Full text and comments »

  • Vote: I like it
  • -1
  • Vote: I do not like it

By CP_Sucks, history, 4 years ago, In English

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

C++14 https://codeforces.com/contest/1282/submission/67691308

C++17 https://codeforces.com/contest/1282/submission/67690121

Full text and comments »

  • Vote: I like it
  • +6
  • Vote: I do not like it

By CP_Sucks, history, 4 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +5
  • Vote: I do not like it

By CP_Sucks, history, 5 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +10
  • Vote: I do not like it

By CP_Sucks, history, 5 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +17
  • Vote: I do not like it

By CP_Sucks, history, 5 years ago, In English

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[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

Full text and comments »

  • Vote: I like it
  • +46
  • Vote: I do not like it

By CP_Sucks, 5 years ago, In English

 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 :)

Full text and comments »

  • Vote: I like it
  • +14
  • Vote: I do not like it

By CP_Sucks, history, 5 years ago, In English

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

1 . https://atcoder.jp/contests/abc123/tasks/abc123_d

Full text and comments »

  • Vote: I like it
  • +4
  • Vote: I do not like it

By CP_Sucks, history, 5 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • -28
  • Vote: I do not like it