Due to technical reasons Codeforces may be unavailable on April 21st from 01:00-07:00 (MSK). ×

hitman623's blog

By hitman623, 6 weeks ago, In English,

Hello Everyone!

I would like to invite you to participate in HackerEarth's March Easy '19. The contest will be held on 9th March, 2019 at 21:30 IST

The problems have been prepared by me (hitman623) and Arpa. I would like to thank teja349 for testing the round, Arpa for his help in organizing the contest and Apptica for giving me the opportunity to hold the contest.

You will be given 6 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 for all and prizes will be awarded to the top 3 beginners (i.e. programmers with a rating of 1600 or less before the challenge starts):

  • First place: $75 Amazon gift card.

  • Second place: $50 Amazon gift card.

  • Third place: $25 Amazon gift card.

  • HackerEarth T-shirts to top 10 beginners.

Contest Link

Good luck and have fun!

UPD — The contest begins in 15 minutes.

UPD1 — The contest has ended. Congratulations to the winners. The Editorials have been published. Feel free to discuss anything in the comments.

Read more »

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

By hitman623, 8 months ago, In English,

Shooting Game

Let PA and PB be the probability of Alice and Bob hitting the target respectively. Then the chances of Alice winning the game are:

PA + (1 - PA)(1 - PB)PA + (1 - PA)2(1 - PB)2PA + ...

which equals using GP formula. Similarly, for Bob it would be .

Equating both we get, . Return -1 in case you get PB greater than 1.


Let x be an nth root of unity. Then, xn = 1. So, xn - 1 = 0 has roots 1, α1, α2....αn - 1. We can write this as follows :

Placing x = 1,  - 1 in the above equation and multiplying them, one can get the desired result.
If n is even the expression evaluates to 0 otherwise n.

Polynomial Guess

Consider the polynomial:

f(x) = x(x - 1)(x - 2)(x - 3)(x - 4)(x - 5)

Let g(r) be the value of at x = r and y(r) be the given values of the polynomial for r = 0 to 5.

The desired polynomial can be written as :

Placing x = 6 in above equation, the desired result can be obtained.



The main part of the solution here is using the equation : φ(xr) = xr - 1φ(x) , . Rest is just solving GP sums and calculating φ values from 1 to m.



Since, the operations allowed are only modifying / deleting a digit and value of n is at max 106, the maximum number that can be formed is of the rage 10n. The idea is to calculate all primes upto 107 and take the minimum number of operations required to convert n to a prime p over all primes p.

Another solution is to observe that we can always get a prime number in the range n - 99 to n + 99 . So, the maximum value of the answer can be 2 only. So, we just need to check whether the answer is 0 or 1. For answer to be 0, n should be prime. For answer to be 1 we have O(10 * d) candidates only where d is the number of digits in decimal representation of n. Each candidate can be checked in O(sqrt(n)).



Let us try to find a series for the number of triangles after n steps. First of all the side length of the triangle after n steps would be m = 2n. Lets iterate over the side length of the triangles that we are going to count currently. Let it be l. Every triangle is either pointing up or pointing down. Lets count them separately and add them in the end. For counting triangles of length l pointing up, we just need to count the number of valid points that can be the topmost point of our triangle. This is equal to . For counting triangles pointing down, we need to count the valid positions for placing the base of length l. This is equal to . The final answer would be :


Simplifying and using some series formulas, you can get a formula as : .
If you do not want to solve the series, observe that the final expression would be of order 3 in m. So, instead assume a general 3 degree polynomial, and get its coefficients using base cases already given.


The idea here is to use the mirror property. Imagine that the sides of the triangles have mirrors placed on them. Then the shortest distance between two centroids such that the line between them intersects all the sides exactly once is your answer. Applying pythagoras theorum, the answer comes to be


The key to the solution is to use Weighted AM — GM inequality here. Let us write the expression as

. . . . a times . . . . b times . . . c times )

Comparing the RHS of the expression with xAyBzC, solve for a, b and c. The final answer hence would be .
The conditions given guarantee that a, b and c after solving would be positive.



The answer to the problem is the coefficient of xc in the expansion of :

(1 + x + x4 + x9 + .....)n

where (1 + x + x4 + x9 + .....) represents the choices each variable has.
One solution is to perform binary exponentiation of the polynomial using NTT for polynomial multiplication. The time complexity of such a solution would be O(clog(c)log(n)).
Another solution is to calculate NTT of the polynomial once, exponentiate individual terms to n and then calculate the inverse NTT. Time complexity of the solution would be O(c(log(c) + log(n))).

Code: 1st solution
Code: 2nd solution


T(n) = Mn where M is the given matrix.

Let and .

Ti + β)

Let R(n) = T(α)n

The main part of the solution is to calculate and .
Consider the following matrix P(A)
\begin{bmatrix} A & I \\ O & I \end{bmatrix} The matrices P2, P3 . . . are as follows :
\begin{bmatrix} A^{2} & A+I \\ O & I \end{bmatrix}

\begin{bmatrix} A^{3} & A^{2}+A+I \\ O & I \end{bmatrix} Observe that the 2nd element of the first row is the GP sum of matrix A. Therefore,

Now, consider .

The first part of which we already know. For second part, Consider
The matrices S(2), S(3) . . . are as follows :
\begin{bmatrix} A^{2} & A+2I \\ O & I \end{bmatrix}

\begin{bmatrix} A^{3} & A^{2}+2A+3I \\ O & I \end{bmatrix} Observe that the second element of the first row is nothing but the desired part. S(n) can also be calculated in the same way the GP sum was calculated as it is nothing but another GP in P. The overall time complexity of the solution is O(k3(log(n) + log(m))).

Also observe that the modulus is 231, so no need to take modulus. We can let the operations overflow. In the end we just add 231 if result comes out to be negative.
Another method of taking modulus is to take bitwise AND of the intermediate calculations with 231 - 1. Both of them are much faster than the modulo operation.


Read more »

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

By hitman623, history, 8 months ago, In English,

Hi, Codeforces Community!

Codefest'18 — a diverse roster of high-quality programming competitions by Department of Computer Science and Engineering, IIT Varanasi is excited to present Mathmania.

Mathmania is a mathematical puzzle contest where a sound knowledge of mathematics together with computational thinking will be essential to solve problems. The motivation behind Mathmania is to provide a platform for the inquiring mind to dwelve into unfamiliar areas and learn new concepts in an exciting way.

The contest will take place at Topcoder. This contest will be an individual event with a duration of 3 hours, from Sep/1/2018 12:30 UTC. The contest will be unrated for both Div1 and Div2 participants but will be a long match which will consist of interesting mathematical challenges covering almost all domains of Mathematics, ranging from Number Theory, Algebra, Geometry, etc.

The contest has been prepared by iit_sujal, GT_18, Enigma27, vinayjaisinghani and hitman623.

Prizes -

1st Place : $200

2nd Place : $150

3rd Place : $75

Best ranking member in India: $75

Topcoder- Mathmania T-Shirts for top 30 participants.

Best two freshers/sophomores from IIT (BHU) will also receive T-Shirts.


Go to Topcoder Arena – arena.topcoder.com(Beta) or setup Topcoder Java Applet*, you will be able to register for the contest.

*In Topcoder Java Applet – you can find the contest listing in Active Contest Tab

Have questions? Email support@topcoder.com

Never Competed in a Topcoder Contest: See this to understand Topcoder Contests better!

UPD : The contest starts in an hour.

UPD : Hope you enjoyed the contest. We apologise for the technical issues you faced during the contest. For all those whose efforts went in vain in the 600 points problem, don't worry we have a consolation prize for you.

UPD : The editorial is published here. Solutions for last 3 problems will be added soon.

UPD : The editorial is complete. Feel free to discuss anything in the comments.

Read more »

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