shubhamgoyal__'s blog

By shubhamgoyal__, history, 7 years ago, In English

Hello Codeforces Community!!!

I invite you all to take part in HackerEarth's January Easy contest.The contest will be held on 1st January,2018 at 22:00 IST.

Problems have been set by me(shubhamgoyal__) and tested by MiteshAgrawal.We are grateful to HackerEarth admin prat33k for his help.

You will be given 5 algorithmic problems to solve in 3 hours. Partial scoring will be used (you get points for passing each test case). Although the contest is targeted towards beginners, we hope even experienced problem-solvers find one or two problems to be interesting. The contest is rated and prizes will be awarded to the top 3 beginners(i.e. Programmers with a rating of 1600 or less before the challenge starts).

Good luck and have fun.

UPDATE1: Close to 3 hours left in the contest.

UPDATE2: Contest has started.

Full text and comments »

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

By shubhamgoyal__, history, 7 years ago, In English

I was trying to solve this problem which recently appeared in a hackerrank contest. The editorial mentions a solution based on geometric interpretation of the question.But since a lot of tree path questions can be done using centroid decomposition,does anyone know how to solve it using centroid decomposition?

Full text and comments »

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

By shubhamgoyal__, history, 8 years ago, In English

Can someone please help me out with this problem.
problem link
I saw a few accepted solutions and I'm guessing that the expected complexity is n*sqrt(n).

Full text and comments »

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

By shubhamgoyal__, history, 8 years ago, In English

Can someone please explain how to approach this problem using centroid tree decomposition. Problem Link-> https://www.codechef.com/problems/BTREE

Full text and comments »

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

By shubhamgoyal__, history, 8 years ago, In English

Can someone please explain how to solve this problem https://www.hackerearth.com/march-clash-15/algorithm/counting-on-tree-1/description/ using centroid tree decomposition.

Full text and comments »

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

By shubhamgoyal__, history, 8 years ago, In English

Can someone please explain the suffix array approach to this problem: http://www.spoj.com/problems/MINMOVE/

Full text and comments »

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

By shubhamgoyal__, history, 8 years ago, In English

Can someone please help me out with this problem. https://www.codechef.com/TCFST13/problems/TCFST05 My aprroach: I was thinking of a dp approach..dp[i][0] would denote expectation value obtained from first i shots given we miss the ith shot...dp[i][1] is defined similarly but this time we hit the ith shot. dp[i][0]=dp[i-1][0]+dp[i-1][1]. dp[i][1]=p[i]*(1-p[i-1])+dp[i-2][0]+dp[i-2][1]+p[i]*p[i-1]*(1-p[i-2])*2*2+dp[i-3][0]+dp[i-3][1]+p[i]*p[i-1]*p[i-2]*(1-p[i-3])*3*3+dp[i-4][0]+dp[i-4][1]...so on.. I am not able to figure out how to calculate dp[i][1] in O(n) time.. Please Help.

Full text and comments »

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

By shubhamgoyal__, history, 8 years ago, In English

Can somebody please help me out in this problem https://www.codechef.com/CDWR2014/problems/CW2/ My approach: Consider any number i.We can calculate its contribution in final sum.There are n-i numbers bigger than i.We choose any j of them and arrange them before i and rest (n-j-1) numbers are arranged after i. Thus the formula: This sum can then be divided by n!. I saw a few AC codes and somehow people have reduced it to sum of harmonic series,however Im not able to reduce my formula further. Can somebody please help!!.

Full text and comments »

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

By shubhamgoyal__, history, 8 years ago, In English

Can somebody please explain how to use the Möbius function to solve this problem. https://www.hackerrank.com/contests/w3/challenges/gcd-product

Full text and comments »

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