Tag Archives: tester

bfd5f9d4-8-cover-AL--R3

Invitation to India Hacks 2015, Qualification Round 3

Hello!

I want to invite all of you to participate in the last Qualification Round of India Hacks 2016, which is organized by HackerEarth.

This is the third and the last one qualification round. If you missed or didn't qualify in the two previous rounds, this is the last change to advance to the semifinals.

Qualification Round 3 takes place on January 17, 04:30 PM CET (click to check your timezone). Top 1000 participants with non-zero score will advance to the main contest.

The prizes in India Hacks are quite nice, including a trip to San Francisco, many tech gadgets and a lot of goodies for top 50 participants. If you want to grab any of them, or you just like to compete agains a lot of other programmers and you haven't qualified to the main contest yet, reserve a time slot for this round!

Screen Shot 2016-01-16 at 9.22.22 PM

I'm a tester of the problem set and a conductor of the contest. There will be 5 problems in the contest and you'll have 3 hours to solve all of them. In addition, a partial scoring system will be used in all of them, which means that you'll get points for each correctly solved test file in any problem.

Big thanks to tanujkhattar, subway, aditya1495 and hellgeek for creating the problems, to belowthebelt for technical assistance and to I_love_Tanya_Romanova and Errichto for proofreading and solving the problems, and for all their suggestions.

Since this is the last qualification round, problems won't be very hard, so if you're going to participate, you may assume that submission time might be a big factor in the final standings.

As a small hint, I can tell you that you should be prepared with number theory, computing optimal subsequences of some types, and techniques used with computation on trees.

Have fun and good luck to all of you!

See you on the leaderboard, hopefully at the top of it :)

61e61b94-8-cover (30)

December Easy 2015 by HackerEarth

Hi all,

December Easy Contest by HackerEarth is taking place on December the 3rd at 5:00pm CET. Contest duration is 3 hours.

There will be 5 problems to solve, all algorithmic ones, especially targeted for beginners. However, I'm pretty sure that any participant will find them interesting to solve :) All the problems have partial scoring and ties are resolved by penalty time.

A little hint for you, 3 of the 5 problems will ask you to minimize some value, so be better prepared with methods of solving these kind of problems :)

As the tester and editorialist for the contest, I want to thank the problem setter aditya1495 and admin belowthebelt for preparing the contest. It was nice to work with you guys as always!

As a tradition in Easy Contests, the top 5 beginners (1st year or 2nd year) will receive HackerEarth T-shirts.

Good luck and see you on leaderboard!

11011222_511457242338872_6530479336684615373_n

HackerEarth August Easy / Subscriptions to blog enabled

First things first, I have just enabled subscriptions to blog. If you want to get informed about new posts or just appreciate my work, please leave me your email in the box located on the right. I will personally thank you and you will be receiving latest cool news from competitive programming world as soon as possible.

HackerEarth August Easy

August Easy is coming and I am the tester of all problems in it. They are so cool that you have to participate. If you decide to, you will face 6 problems: a geometry one, one involving bitwise XOR, a string challenge, one related to permutations and 2 ad-hoc problems. There are over 1200 people already registered, so we expect a great competition!

and more..

Moreover,  another big 24 hour contest with great prizes is coming and I am the author of a hard problem in it. More details coming soon :) Stay tuned!

JULY_EASY

Editorialist for HackerEarth // July Easy Contest

I am pleased to announce that I have just become editorialist on HackerEarth. It is a great platform with a lot a challenges - they are growing extremely fast.

I really encourage you to take part in upcoming July Easy Contest for which I am the editorialist. Problems are really nice and fun to solve thanks to Arjit Srivastava who is the setter.

See you on leaderboards!

 

game-theory1

Knight and Queen // HackerRank Lambda Calculi

It's been a while since my last post here. I've been busy working with my team on a brand new game for Android and iOS.

Anyway, I'm back with a very interesting problem. I was asked to test some problem for HackerRank Lambda Calculi Contest. The one which I want to write about is Knight and Queen. The original problem is available here:

https://www.hackerrank.com/contests/lambda-calculi-10/challenges/knight-and-queen

Problem statement

Two players are about to play a game on a chessboard of size n x n, where the bottom-left cell has coordinates (0, 0). There are only 2 figures on the board: the Knight and the Queen. Both figures moves like in a classic chess game, but with a restriction that they cannot move right or up, so every legal move is left, down or left and down. For example, the Knight standing on a field (5, 4) can move to (4, 2) or (3, 3) but cannot move to (6, 6). Also note that both figures can be a the same cell in the same time.

Players takes moves alternately. Player who is about to make a move can pick the Knight or the Queen and make any valid move with in. A player who is not able to make a move is declared a looser.

Your task is to decide who is a winner knowing the initial positions of both figures and the fact that both players plays optimally.

You will be given many testcases, so the best you can do is to be able to provide the answer for any given initial positions fast.

Solution

If n is quite small, you can consider a dynamic programming solution where we have n^4 positions: n^2 possible positions of the Knight multiplied by n^2 possible positions of the Queen. For each such position, you can compute the best possible move in O(n) time, so a total time will be O(n^5), but since we have n = 50, this is way to much.

We need a faster solution.

Game of Nim

Let's consider a simpler game called Nim first. In the Nim game, there are N distinct heaps. Each heap has a positive number of objects. Players takes moves alternately. Player who is about to make a move, can choose any non-empty heap and remove any positive number of objects from it. A player who is not able to make a move is declared a looser and a player is not able to make a move if and only if all heaps are empty.

This is a very classic game, a fundamental one in game theory. There is a famous theorem which can be used to determine who has a winning position in Nim at the beginning of the game if both players plays optimally. If you haven't heard about it yet, you should be amazed at least a little bit.

Theorem

Let a_1, a_2, ..., a_N be current sizes of heaps i.e. a_i is the number of objects in the i-th heap before the next move. Let X = a_1 xor a_2 xor ... xor a_N, where xor is a binary xor operation.

A player who is about to make a move has a winning position if and only if X != 0.

In other words, if X != 0 and you are about to make a move, you can win no matter what, and if X == 0 and you are about to make a move, no matter what will you do in that move, your opponent can always win.

Sounds great! Let's make a sketch of a proof.

Let X == 0 before the next move. There are two possibilities:

  1. All heaps are empty, so the current player is a looser
  2. There is at least one non-empty heap

Since the first situation is clear, let's consider the second one. The current player has to remove at least one object from a non-empty heap, so no matter what will he do, the xor of sizes of all heaps after his move will be non-zero.

On the other hand, if X != 0 before the next move, the player who is about to make a move can always choose a valid move leading to a situation that the xor of sizes of all heaps after this move will be 0.

If you want to more detailed explanation, check it here or do it on your own considering binary representation of heaps sizes.

Our problem

Let's think of our problem as of a special game of Nim where we have only two heaps, the first one for the Knight and the second one for the Queen and let's consider these two heaps separately. For each of these two heaps, we will assign a single number to any position of the figure corresponding on the board. This number will correspond to the number of objects in a game of Nim on a single heap.

Knight's heap

Let's consider any position of the Knight such that there is no valid move with this figure. Any such position is equivalent to an empty heap, so we will assign 0 to any such position. Next let's consider any other position P, and let M be a set of numbers assigned to all positions reachable from P. We will assign the smallest non-negative integer which is not in M to the position P.

Queen's heap

We will do the same as above with respect to Queen's valid moves.

After making these two above computations, we have assigned numbers to any valid position of each figure on a board. We can think of these numbers as of the number of objects in the corresponding heap in a Nim game - just note that in Nim if you have k objects on a heap before your move, you can reduce the number of objects in this heap to any non-negative number less than k. The same is true in our game. If you decided to move the Queen in your turn, and it is currently in a cell with number k assigned to it, you can move it to a different cell with any assigned non-negative number less than k.

So in order to solve our problem, just assign the numbers as described above to both Knight's and Queen's positions. Let X be the xor of assigned numbers corresponding to the initial position of both figures. The player who starts the game has a winning strategy if and only if X != 0.

Time complexity

For a board of size n x n, you have to compute two tables of size n x n and computing a single position in any of these tables takes at most O(n) time, so the total complexity is O(n^3) if you use memoization or dynamic programming and here we have n = 50, so it will be very fast.

Related problems

One interesting thing is that many simple games can be reduced to Nim. I encourage you to read about that here.