retr0coderxyz's blog

By retr0coderxyz, history, 4 years ago, In English

Hello guys, Can anyone explain me how to do Problem E . (I came up with a greedy solution where in we sort based on the last candidates and remove first k polls until the sum of last candidate is less than at least one candidate. nut realized it would be wrong.) So can anyone explain a way to do this. Thank you!

I read the editorial and couple of other people's solution, but I couldn't understand what's going on.

Full text and comments »

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

By retr0coderxyz, history, 4 years ago, In English

Hello guys,

I was trying to solve Distinct Colors: link.

I did a naive solution which obviously led to TLE.

TLE

I saw various solutions that use BIT. But I cant assimilate why BIT works here, what BIT represents here (for e.g. in case range sum query BIT keeps track of cummulative frequency.)

It would be great if someone tells some trick how to use BIT for various other purposes too.

Thanks!

Full text and comments »

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

By retr0coderxyz, history, 4 years ago, In English

Hello guys,

I have been trying to solve Dp problems. When I read a problem I try to translate it into DFS(recursion) which ends up having TLE, then I simply store the state variables so it passes the time limit. But What I want to learn is that, any trick is there to convert this into iterative DP( As I guess DFS+memo has large constant factor).

For example take this problem: link

TLE Code non memoized
DFS+Memo Passed

So I want to learn a generic technique ( not limited to this problem) to write iterative solutions as No matter how hard I try I am unable to grasp iterative writing method. It would be great if you guys could help me in this. Thank you!

P.S. Please Dont downvote this blog guys as some people have extension to hide bad blogs. Once I get an answer you can downvote it to your hearts content. Thanks :)

Full text and comments »

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

By retr0coderxyz, history, 4 years ago, In English

Hello guys,

When I was practicing problems found that there was no way to hide the problem tags. It really hinders my ability to identify the class of problem. So I wrote an extension for chrome to hide the tags and reveal when required. It is quite useful for me and I guess you guys would also feel its useful.

Link for extension: link

Instructions: link

Use the extension and let me if you guys face any bugs or any sorts of thing.

UPD: well this extension allows to reveal tags in a button press. So after long time if we are unable to identify the class of problem we can simple reveal it. I find it much easier than turning entirely off in settings. Hope i gave back something meaningful for this beautiful community.

UPD2 Screenshots:

1.png

2.png

Thank you and happy coding.

Full text and comments »

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

By retr0coderxyz, history, 4 years ago, In English

Hey guys!

I am trying to solve Qtree2 from SPOJ after learning about LCA using binary lifting.Problem

There are 2 parts to this question one is to find distance between any two given nodes and the other part is to find kth node in the path between 2 nodes.

While I was able to solve the first part, but I am stuck in solving second part, I tried a lot (only clue i was able to find out is that the path goes through LCA of two nodes) and couldn't proceed from there.

It would be really helpful if someone could give a detailed explanation using binary lifting it would be great. Thank you so much!

Full text and comments »

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

By retr0coderxyz, history, 4 years ago, In English

Can anyone tell me how to solve this problem: 208E.

I saw few solutions and I understood till the LCA part I dont understand why should we renumber the tree and why is binary search used here. It would be great if anybody could help me out with this. Please and thank you so much :)

Full text and comments »

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

By retr0coderxyz, history, 4 years ago, In English

Hello Community,

I am trying to learn to find LCA using binary lifting method. But, I am unable to find where does my code fail. It would be great if someone could point this out.

Problem: LCA

Solution: Solution

Please Help me with this guys ! Please. Thank you!

Full text and comments »

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

By retr0coderxyz, history, 4 years ago, In English

Hello guys,

https://codeforces.com/contest/1324/submission/73157058 fails at test 99 because of this

error

But this works fine in local compiler for the same test case. can anybody point out my mistake?

Thanks!

Full text and comments »

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

By retr0coderxyz, history, 4 years ago, In English

Hello community,

Recently I cam across 4 questions(A hiring challenge from Hacker Earth which is over now!) to which I could not find solutions. I tried my best during contest to come with solutions but I was unable to do so. It would be great if you guys could help me provide a solution for these problems(also a generic solution for similar kind of problems) Would really help me a lot. I dont remember the exact problem but I would try to provide the best description to my knowledge.

Problem 1:

We have to distribute N coins to S students such that each gets distinct number of coins while maximizing S. We have to find S. For eg. if N is 5 then S is 2 because (2,3). Its not mandatory to distribute all N coins.

My Idea

Problem 2:

Swapping the segments: given array of size n and q queries with each query containing l1,r1,l2,r2 A[l1:r1] should be swapped with A[l2,r2] After Q queries we should print the final array.

My Idea

Problem 3:

Given a string s we need to find two subsequence s1=s2 and maximize |s1+s2|. For eg: aabababb the answer is 6 s1=aab and s2=aab

My Idea

Problem 4:

Given a character for each node. and given a graph(its guarenteed to be a tree). Q queries with each query giving x y. We have to find for each query a consider a simple path from x->y find the most frequent character along the path. For eg.

6
a b a s q n
(n-1 edges)
1 2
1 3
2 6
3 4
3 5
2
2 3  => a
2 6  => b(print lexicographically smaller in case of tie)
My Idea

Thank you for reading patiently guys, I tried so much to come up with a solution but couldnt so any help would be greatly appreciated guys.

Full text and comments »

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