hitman623's blog

By hitman623, 5 years ago, In English

Hello Codeforces!

I would like to invite you to Manthan, Codefest'19, which will take place on Sunday, August 25, 2019 at 8:05 PM IST. This is a combined Div. 1 + Div. 2 round and is rated for participants from both divisions.

The Department of Computer Science and Engineering, IIT (BHU) is conducting Codefest from 23rd August — 25th August. Manthan, the algorithmic programming contest under the banner of Codefest, is being held as a special Codeforces round. The round follows regular Codeforces rules.

All problems in this round were created and prepared by drastogi21, _shanky, Enigma27, _hiccup, KAN and me (hitman623).

A lot of thanks to KAN, 300iq, vintage_Vlad_Makeev, _overrated_, Rox for the testing and valuable comments, and to MikeMirzayanov for the awesome Codeforces and Polygon platforms!

Prizes -

  • 1st place — INR 25,000

  • 2nd place — INR 18,000

  • 3rd place — INR 12,000

  • 1st place in India — INR 6,000

  • 1st place in IIT(BHU) — INR 3,000

  • 1st place among freshers (1st/2nd Year) of IIT(BHU) — INR 1,000

  • Codeforces T-shirts to the participants who will be the first to solve each problem.

Participants will be offered 8 problems and 2 hours to solve them. As usual, the scoring distribution will be announced later.

Hope you guys enjoy the contest! See you on the leaderboard!

UPD: The scoring is 500 — 1000 — 1500 — 2000 — 2250 — 2500 — 3000 — 3750

UPD: The contest has ended. Congratulations to the winners.

1. tourist

2. Um_nik

3. jqdai0815

First place in India: cerberus97

Following are the participants who were the first to solve each problem and have won a Codeforces T-shirt. Congrats!

A. IgorI

B. Geothermal

C. icecuber

D. ILoLy

E. nocriz

F. GoGooLi

G. jqdai0815

H. tourist

UPD: We decided to give the 8th T-shirt to IgorI for problem A. Congrats!

The editorial has been published.

Hope to see you next year!

Full text and comments »

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

By hitman623, 6 years 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.

Full text and comments »

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

By hitman623, 6 years 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.

SolveForTrisha

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.

Code

FunctionGame

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.

Code

PrimeMaker

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

Code

CountingTriangles

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.

ConfusingTriangle


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

MinimizeExpression

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.

Code

EquationSolver

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

Tribonacci

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.

Code

Full text and comments »

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

By hitman623, history, 6 years 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.

Registration:

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 [email protected]

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.

Full text and comments »

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