SPOJ QTREE2

I'm back after a long break; longer than I anticipated. I was reading a Topcoder tutorial on Range Minimum Query (RMQ) and Lowest Common Ancestor (LCA) problems. Here's a comparison table of the algorithms presented in the tutorial -

Break

I'm taking another break for 3 days; currently overloaded with project works; need to reduce the workload to a maintainable amount.

SPOJ MMOD29

Problem Link : http://www.spoj.pl/problems/MMOD29/en/

I was searching some problems that would require modular inverse / Chinese remainder theorem / Extended Euclidean algorithm. This problem requires the simplest case of modular inverse when the numbers in question are co-prime.

The problem in short

Find the sum of divisors of the number 2004^X mod 29 [1<=X<=10000000].

So, first we need to find the sum of divisors of an arbitrary number N. Let prime factorization of N is -

TopCoder SRM 489 Div 1 Medium (Dice Rotation)

Another bad SRM for me :( I couldn't even submit any problem although I was just 1 click away from solving the medium problem with 30 seconds to go when the network router decided to go offline. My only achievement in this SRM was one successful challenge.

I'm going to explain how I approached the dice rotation problem. In this problem you have to move a standard dice placed at (0,0) cell of an infinite Cartesian plane to (goalx, goaly) by rotating it to right or up. The top of the dice have to show '1' when it starts its journey at (0,0) and also when it ends its journey at (goalx,goaly) and it cannot be on top in any intermediate cell. goalx and goaly can be as high as 10^9.

SWERC 2010: Assembly Line [Solved]

This is the problem I was getting Time Limit Exceeded as mentioned in the post. Thanks to emotionalBlind and moshiur for sharing their approaches. Previously I was trying to do a top down DP of finding optimal result within a start and end index which produces a certain character output. Now, I've switched my approach to bottom up. I am still storing results for the state [start index, end index, character i want to make]. But I'm also saving the characters I can make in a range of start and end index into a vector. So, when we split at different positions, instead of trying all characters, we only have to try the characters that we can make on the sub-range.

SWERC 2010: Jumping Monkey [Solved]

As you can find on my previous post, I was getting wrong answer on this problem. Thanks to BearedCrazyCoder aka Sidky for pointing out the mistake in my approach. I was using dynamic programming and moving from one state to the other recursively. You can read this comment for understanding the flaw  -

Unsolved: Jumping Monkey & Assembly Line from SWERC

Today there will be no solution for solved problem, rather I would post my approach, code and test data for 2 unsolved problems in recent SWERC contest and you are invited find flaws in my solution.

Jumping Monkey

This is an interesting problem. I've used bitmask DP to solve it. Each state represents the possible locations of the monkey. Now if we shoot a particular tree, if there was a monkey in the tree, it will die and cannot move to neighboring tress. If the monkey was in any other tree, it will move to any of its adjacent trees (including the one we've just shot).

TopCoder SRM 473 Div 1 Medium (RightTriangle)

Problem Link : http://www.topcoder.com/stat?c=problem_statement&pm=10976

In this problem,

given some points on the perimeter of a circle that were selected from a poll of equidistant points, we have to calculate how many different right triangles we can make from those points. points are placed using a generator program. If a position is filled up by a previous point, it will be placed on the next available position.

Now this problem has 2 parts -

TopCoder SRM 447 Div 1 Medium (PeopleYouMayKnow)

Problem link : http://www.topcoder.com/stat?c=problem_statement&pm=10580

This is a nice problem because it can be solved in different ways - dynamic programming, maximum flow or bipartite matching.

The solution of the problem in one line would be

calculate maximum number of node disjoint paths from node p1 to p2 whose length is less than or equal to 3.

TopCoder SRM 477 Div 1 Medium (PythTriplets)

Problem Link : http://www.topcoder.com/stat?c=problem_statement&pm=10766&rd=14157

In this problem, given some integers (at most 200) in the range [1, 999999] you have to find maximum number of disjoint pairs (a,b) such that a^2 + b^2 = c^2 for some integer c and a & b are co-prime.

Now this is a classic example of a bipartite matching problem although it may not be evident how to split the numbers in two bipartite sets. Lets consider the different cases possible according to the parity of the numbers in a pair -

TopCoder SRM 480 Div 1 Medium (NetworkSecurity)

Problem Link : http://www.topcoder.com/stat?c=problem_statement&pm=10736

This is a nice graph theory problem. The key observation here is that there is no point placing a data gate on an edge that is not directly connected to a server. Because in this way it can serve maximum number of clients. You might think if a client is connected to all the servers through some path and all the paths share an edge (a bridge) that is not directly connected to a server, why not just place a data gate on that edge as it will be useful for all of the paths? The answer is though it comes handy for the client in question, it does not do any help for the clients that are directly connected to the server. They still need a data gate between them and server. So, we have to place data gates further down the path anyway and that gate on the bridge edge will just be redundant.

TopCoder SRM 379 Div 1 Medium (TheAirTripDivOne)

The problems of latest TopCoder SRM 488 were set by Vasyl. The set was nice and a bit on the harder side. So, I was looking for the problems Vasyl set previously. I've found this one.

This problem is actually pretty straightforward. You just need to binary search on the safety parameter and for a particular value of safety, you have to determine if it is possible to make a series of trips within specified time to reach city n by waiting at least safety minutes between flights. This is essentially an shortest path problem on weighted graph which can be solved by Dijkstra's algorithm. We won't even need an efficient implementation as number of nodes and edges are within 500.

TopCoder SRM 395 Div 1 Medium (Skyscrapers)

Problem link: http://www.topcoder.com/stat?c=problem_statement&pm=8582&rd=11129

Problem description -

The skyline of the city of Terrapin City has N buildings all in a straight line; each building has a distinct height between 1 and N, inclusive. The building at index i is considered visible from the left is there is no building with a smaller index that is taller (formally, height[j] < height[i] for all j < i). Similarly, a building is visible from the right if there is no taller building with a higher index (height[j] < height[i] for all j > i). For example, if the buildings in order are {1, 3, 5, 2, 4}, then three buildings are visible from the left (1, 3 and 5), but only two are visible from the right (4 and 5).

TopCoder SRM 450 Div 1 Medium (Earn)

I was searching for what problem to solve today. I tried some - few were too difficult and few were too easy or uninteresting. So, I decided to randomly solve a TopCoder Division 1 medium problem. This one came up.

Problem statement -

As a serious strategy-games player, you know how important it is for your country to have a strong economy. In order to make this happen, you've just built n factories and hired k specialists. Unfortunately, you now have no gold left, and you must figure out the fastest way to raise target units of gold.

Strange Town

This is problem D from Codeforces Round 41. You can find the analysis of the whole problemset here.

The problem in short -

Given a graph with N nodes and bidirectional edges between all pair of nodes, you have to assign distinct prices to the edges of the graph in a way such that all the Hamiltonian cycles cost the same. Price of an edge cannot exceed 1000.

Now there are some key observations here -

Taking a break

I'm taking a break of 2/3 days from this blog as it is Eid day here. Alhough few years back, when I was a university student, I used to spend these days solving problems and participating in contests, things are a bit different right now - have to take some family responsibilities :)

Eid Mubarak to all!

Product of Prices

I've solved another Binary Indexed Tree problem today. It is the Div 1 Hard problem from TopCoder SRM 424. This problem is a bit harder to formulate than the previous one. You can check the complete analysis of the problem in the official match editorial. And don't forget to check the tutorial if you have any difficulty understanding BIT.

Floating Median

Today I've started to brush up my data structure knowledge. I've started with Binary Indexed Tree (BIT). TopCoder has an excellent tutorial on this. Initial segment of the tutorial is a bit hard to understand as it starts with notations and mathematical formulations but if you read that segment 2/3 times, things should be clear.

The problem I've solved requires you to -

Given a sequence of N integers in the range [0,M), find the sum of medians of N-K+1 contiguous subsequences of length K. (1<=N<=250,000; 1<=K<=1000, M=65536).

Hyper-Box

Today its going to be an easy problem as I couldn't manage time to solve anything harder. Its problem C of Dhaka Regional; 3rd most easiest problem of the set.

The problem requires you to

build an N dimensional hyper box using N dimensional hyper bricks whose length in any dimension can only be a Fibonacci number. You have to calculate minimum of bricks you'll need. N can be at most 15 and the length of any dimension of the hyper box can be 2*10^9.

First few numbers of Fibonacci sequence are -

1, 2, 3, 5, 8, 13, 21, 34, 55.....

So, if N = 3, you can use bricks of size (8,2,55) or (1,2,3), but you cannot use (1,5,10) as 10 is not a Fibonacci number.

Digital Matrix

For the 3rd day in a row, I'm solving a problem from recent Dhaka regionals. This time it is problem F - Digital Matrix. It is a very tricky ad hoc problem. No team could solve it during the real time contest. Fudan University came closest to solving it with their solution giving wrong output on only one type of cases. It took them 13 submissions though to come that close.

The problem states that

You are given two N x N square matrices, A and B. Each of the elements of these matrices is an integer between 1 and K (inclusive). You have to convert matrix A into matrix B in minimum number of operations. In each operation you can choose one element of matrix A and change it to any integer between 1 and K (inclusive). You have to ensure that after any operation the matrix is not converted to a symmetric matrix.

Knockout Tournaments

This problem is also from recent Dhaka Regional contest. Problem link -
http://acm.uva.es/archive/nuevoportal/region.php?r=as9&year=2010

The problem in short would be

For a number of tennis tournaments, each consisting of 8 rounds, you are given total number of wins (W) and losses (L). You have to find your average performance (round you reached) considering all possible scenarios. Two scenarios are different if the number of tournament played is different. W and L both are between 0 and 2*10^8.

Halloween Costumes

This is a problem from recently held ACM ICPC Dhaka Regionals. You can find the problem here -
http://acm.uva.es/archive/nuevoportal/region.php?r=as9&year=2010

The problem can be reduced to this -

Find minimum number of push operations needed to build a number sequence by printing the top element of the stack.

For example, if the sequence to be built is -

1 2 1 1 3 2 1 

We can do it through the following steps -

Introduction

My name is Sabbir Yousuf Sanny. I've completed my undergraduate degree from Bangladesh University of Engineering & Technology (BUET) in 2008 and I'm now working at Mukto Software Ltd.

This blog is going to be all about problem solving. I have participated in 2 ACM ICPC World Finals - 2007 & 2008. April 2008 was the last time before when I did problem solving seriously. After that its just occasional competitions - Topcoder Opens and Google Code Jams.

But recently I'm finding that passion of problem solving again; passion that keeps you sleepless for nights with a problem in head, paper and pencil in hand and an IDE open. I've decided that I'll try to manage 2 hours each day so that I can solve at least one interesting problem. Then it came to my mind - why not open a blog about it? It will certainly help keep my resolution of one problem a day and inspire me to in-depth understanding of every problem I solve or every algorithm that I learn.

So, here it is - a blog that I will try to keep updated every day with a new problem. Problem source can be UVa, Archive, Topcoder, Codeforces - anything that I feel like solving that day.