Samir Ahmed

Postgraduate Student at Monash University

[blaklites]

Migrating from Blogger

I have moved from blogger.com to tumblr. The posts here are copied from my previous blogger account.

[blaklites]

Light Online Judge: 1187 - Lining up Students

http://www.lightoj.com/volume_showproblem.php?problem=1187

The problem has a o(nlogn) segment tree solution. But it can be solved with o(n) complexity. The solution can be related to insertion sort and goes as follows:

At any point, assume the current list of 'N' numbers(students) is sorted. Keep record of the current position of the INITIALLY LEFTMOST student, say 'X'. When a new student comes in, you know the number of student 'S' who are taller than him and are to the left, meaning number of students in the current list who are taller than the new student. Now, if N-S is less than or equal to X, meaning, the first student(initially leftmost) is taller than the current student, increment the value of X.

The solution is simple and nothing special once you know it. But I would say such solutions require good understanding of sorting algorithms.

[blaklites]

Uva Online Judge: 12338 - Anti-Rhyme Pairs

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=278&page=show_problem&problem=3760 It was problem D of Daffodil Pre ACM 2011 (Bangladesh). The problem can be solved using Hashing or LCA. My team solved the problem using Segment Tree during the contest. Therefore, I will discuss the segment tree approach. First thing one have to understand is that, if one sorts the strings in lexicographical order, each string will always have its maximum match with either the string immediately to its left or to its right in the sorted list. Therefore if we have N strings say Str0, Str1......StrN-1, for each String Stri (0<=i<N), if maximum match of Stri and Sri+1 is X, then maximum match of string Strj (i+1<j<N) will always be less than or equal to X. Therefore, for a given pair of Strings, first find their indexes in the final sorted list, then find the minimum match between any two pairs of strings between the two indexes. Each query can be answered using segment tree. I guess that'e enough :).

[blaklites]

Light Online Judge: 1103 - Castle Walls

http://www.lightoj.com/volume_showproblem.php?problem=1103

The problem has a segment tree solution. But the problem can also be solved by PURE sorting and needs good understanding of a o(nlogn) sorting algorithm.

Thinking from sorting's point of view, lets assume that each peasant is a number with his value as the POSITION OF HIS GRAPPLING HOOK on the wall. So, the problem comes down to this:

Given the value of each peasant, sort the peasants VALUEs in increasing order such that peasant A is greater than peasant B if B's value (positon of hook) is more than that of A. While sorting, keep track of all the red peasants to the left of each blue peasant such that the red peasants' VALUEs are greater than that of the blue peasant: meaning their grappling hooks collide.

I guess the above explanation is enough. Solving the problem using Sorting will taste your understanding of the Sorting Algorithms. Therefore its worth a try.

Related Problem: SGU Online Judge: 180- Inversions

[blaklites]

ACM ICPC 2011 Dhaka Site: Problem E - Guards

http://www.lightoj.com/volume_showproblem.php?problem=1365

This is one of the most beautiful problem I have solved till date.

The soltuion is DP+counting.

Hints

1. Eliminate one parameter with a good observation

2. Apply basic combincatorics

Complexity N*K

I am not writing anymore about the solution. But, If anyone solves the problem by fully understanding and coming to the solution on his own, it will be a pleasant experience.

Still if someone wants to know the solution, here is  link to a solution. The solution has a different approach then that of mine.

[blaklites]

Light Online Judge: Samir’s Contest 2

This was the second contest that I have authored in Light Online Judge. You can read about my first contest here. Thanks to Iqram Mahmud for his alternate solutions for problem A, B and C. He was a bit ill so was unable to provide any alternate for problem D.  The contest went pretty fast for few of the contestant (solutions came really early), but I hope everyone enjoyed the contest.

I will explain the solutions in brief as usual:

Problem A: What you need to find is the largest integer that has at least K multiples less than or equal to N. The answer therefore is N/K. The first correct solution came in the second minute by Wang Shengyu

Problem B: The first player will win the game only if he can make the XOR sum of the all piles zero after his first move. In order to do that, you can find after some analysis that he can take away only a unique number of stones from each pile. So, for each pile, check if you can reduce its number of stones down to a new number and make the overall XOR sum of all the piles zero. The first correct solution came in the fifth minute my Wang Shengyu

Problem C: The problem can be solved using Dynamic Programming. You can use the concept of insertion or merge sort to solve the problem. In order to sort an array with the minimum number of swaps, for each number X, all the number to its left should be sorted. Then you keep on swapping X with the numbers to its left until you get a number which is smaller than X. I will not discuss the full solution now, I leave the rest to the solvers J. The first solution came in the twenty second minute again my Wang Shengyu

Problem D:  My solution to this problem uses inclusion-exclusion principle. If you observe properly, you will notice that a number will not have more than 8 unique prime factors. Therefore, you can use inclusion-exclusion principle to find the total sum of all the multiples (less than N) of the prime factors of N. Then deduct that value from the sum of all the numbers from 1 to N-1. There is another solution which is  n * phi(n) / 2, I got to know that during the contest. The first correct solution came in the ninth minute by Mohammad Hafiz Uddin.

Contest’s Final Rank list

You can still solve the problems and submit your solutions here.

[blaklites]

Light Online Judge:  A Contest Dedicated to Numbers

http://www.lightoj.com/practice_contest_index.php?contest_id=2

The contest was the then called virtual contest of light online judge. The author of the contest was me and all the problems were authored by me. Though there might be similar problems in some other online judge, I don't know. I will discuss the problems' solution in brief as usual.

Problem A:  ctrl A + ctrl B + ctrl C

The problem actually asks to find the maximum LCM among the LCM of all pairs of integers from 1 to N. The first ACCEPTED solution came in the 51st minute. Lets not talk about the solution, try it yourself.

Problem B: Filipino Translation

Here is the way to find the solution: Copy the output of sample case 2. Go to http://rot13.com/index.php, cypher, google translate. :). It was just for fun.

Problem C: God captures Devil

The name is shortened as GCD. Solution: Divide N with by smallest prime factor. Multiply the result with smallest prime factor-1.

Problem D: You are not single with respect to me

My solution used binary search. For each prime P (not a factor of N), search from the list of sorted prime numbers (not factors of N) the index of the largest prime L such that P*L<N. Repeats should be handled .

Problem E: One Theorem, One Year

This was my favorite problem and the problem was later added to lightoj. http://www.lightoj.com/volume_showproblem.php?problem=1298. I will not talk about the solution and I suggest readers solve it without knowing the category of the problem.

[blaklites]

My Problems at Sphere Online Judge

I have added three of my problem to Sphere Online Judge.

Reverse Engineering

One Theorem, One Year

Enough of analyzing, let’s play

These are my problems from two different contests I authored in Light Online Judge.