A Tilling Puzzle

The Puzzle:
You are given an (8 x 8) grid (i.e. 8 rows, 8 columns) and an infinite supply of (1 x 3) tiles. You have to find a tilling of this grid with these (1 x 3) tiles such that, exactly 1 cell is left uncovered. Note that, you can rotate some of the tiles if you wish.



The Solution: It's an easy puzzle actually!




A Question: ( this is the actual puzzle! )
Is it always possible to solve the puzzle, if the position of the uncovered cell is specified ?


Answer: I don't know.

Z-Training :: Slicice

Problem Link: http://www.z-training.net/tasks.php?show_task=5000000529

Shortly the problem is,
There are N players (child). (1<=N<=100). They had some races. In each race, exactly 2 people participated. The winner received 2 points (cards, in the problem), looser receives 0 point. In case of a draw, both receives 1 point. After many races has taken place, you are given the points (cards) of each of the players, and a partial list of races where the id of the players are known, but the results are unknown. Note that, the list is partial (i.e. more races might have took place but they forgot who raced against whom). You have to construct a complete list of races with results.

The Solution:
This can be solved with max flow (experience will tell you that). Observe that, the total number of purchases (races) that took place is, total _number_of_cards / 2. Because, every purchase produces exactly 2 points, and distributes them according to the result.

So, we can build a flow network that has a vertex for each child and each purchase (known + unknown). The child-vertices are connected to the source with an edge with capacity equal to the number of cards of that child. For each known race (a,b), child a and child b are connected to that race-vertex with edge capacity 2. Every child is connected to every vertex that represents an unknown race with edge capacity 2. Vertices representing races will be connected to the sink with edge capacity 2.

Now, we shall be able to build a possible solution (any valid solution is allowed) from the maximum flow in this network.

Let, (a,b) is a known race and x is the vertex representing this race. Now, the pair (flow[a][x], flow[b][x]) will correspond to the result of this race. A (2,0) would mean, 'a' had own, (0,2) means, 'b' had own, and (1,1) would correspond to a draw.

Now let, x represent an unknown race. The edge (x,sink) has capacity 2. It is ensured in the problem that, the solution will always exist. So, the total incoming flow for x will be exactly 2. In fact it will be true for every race-vertex. So, there will be either a single incoming edge with flow 2, or two incoming edges with flow 1 for each. In the second case, the corresponding child-vertices will correspond to the participants of a race that has been drawn. In the first case, the child that produces that flow amount 2, will be the winner of that race. The looser is unknown. But, because any solution is allowed, we can assign any other child as the looser.

I have used Edmonds-Karp Algorithm to solve this problem (because, that's the only max-flow implementation that I know)

Complexity:
Maximum Total Nodes, V = 100 + 1000 + 2 = 1102 ( total child + total races + source and sink )
Maximum Total Edges, E = 100 + 100*1000 + 1000 = 101100 ( source to child + child to race + race to sink )
Edmonds-Karp has a complexity of O(VE²)
That gives us 1102*101100*101100 = 11263773420000, which is too large to run in 5 seconds!
But wait! The max-flow for this network will never exceed 1000 and at each step of Edmonds-Karp, the total flow increases by at least 1. So, the total number of augmentation won't exceed 1000. To find an augmenting path, Edmonds-Karp uses BFS that has complexity O(V+E) . So, in the worst case, Edmonds Karp will need at most 1000*(1102+101100) = 102202000 operations which clearly, would run in way under 5 seconds!

Here's the code:

#include<stdio.h>
#include<string.h>

#include<vector>
#include<queue>
#include<algorithm>

using namespace std;

typedef long long LL;
typedef pair<int,int> pii;

#define FOR(A,B) for(int A = 0; A < (B); ++A)
#define REP(A,B,C) for(int A = (B); A <= (C); ++A)
#define CLR(X,Y) memset(X,(Y),sizeof(X))

#define MAX_NODE 1+100+1000+1+5
#define INF (1<<29)

int src, sink;
int child, recall, card[105], total_card;

struct edge
{
    int u, v, cap, flow;
    
    edge(){}
    edge(int _u, int _v, int _cap, int _flow) 
    { 
        u = _u; v = _v; cap = _cap; flow = _flow; 
    }  
};

vector<edge> E;
vector<int> adj[MAX_NODE];

int rec_u[1005], rec_v[1005];

void add_edge(int u, int v, int cap)
{
    adj[u].push_back(E.size());
    E.push_back(edge(u,v,cap,0));
    
    adj[v].push_back(E.size());
    E.push_back(edge(v,u,0,0));
}

void build_network()
{
    int total_purchase = total_card / 2;
    
    src = 0;
    sink = child + total_purchase + 1;
    
    // initialize
    E.clear();
    
    // src to child
    REP(u,1,child)
    add_edge(src,u,card[u]);
    
    // child to recalled-purchase, and recalled-purchases to sink
    // recalled-purchases are represented by nodes (child+1+i)
    FOR(i,recall)
    {
        add_edge(rec_u[i],child+1+i,2);
        add_edge(rec_v[i],child+1+i,2);
    
        add_edge(child+1+i,sink,2);
    }
    
    // child to unknown-purchases
    // unknown-purchases are represented by nodes (child+1+i)
    REP(u,1,child)
    for(int i = recall; i < total_purchase; ++i)
    {
        add_edge(u,(child+1+i),2);
    }
    
    // unknown-purchases to sink
    for(int i = recall; i < total_purchase; ++i)
    {
        add_edge((child+1+i),sink,2);   
    }
}

int botnek[MAX_NODE], parent[MAX_NODE];

void max_flow()
{
    while(true)
    {
        REP(i,0,sink) 
        parent[i] = -1;
        
        queue<int> Q;
        Q.push(src);
        
        botnek[src] = INF;
        parent[src] = -2;
        
        bool found = false;
        
        while(!Q.empty() && !found)
        {
            int u = Q.front();
            
            Q.pop();
            
            FOR(i,adj[u].size())
            {
                int k = adj[u][i]; // edge-k goes out from node u
                int v = E[k].v; // v is the next node
                
                if(parent[v] != -1) continue; // already seen
                                              
                int res_cap = E[k].cap-E[k].flow;
                
                if(res_cap > 0)
                {
                    parent[v] = k;
                    botnek[v] = min(res_cap,botnek[u]);
                    
                    if(v == sink)
                    {
                        found = true;
                        break;
                    }   
                    else
                    {
                        Q.push(v);
                    }                
                }
            }
        } 
        
        if(!found) break;
        
        int v = sink;
        
        while(v != src)
        {
            int k = parent[v];
            
            E[k].flow += botnek[sink];
            E[k^1].flow -= botnek[sink];
            
            v = E[k].u;
        }
    }
}

int F[1105][1105];

void output()
{
    int total_purchase = total_card / 2;
    printf("%d\n",total_purchase);
    
    REP(i,0,sink)
    {
        FOR(j,adj[i].size())
        {
            int to = E[adj[i][j]].v;
            F[i][to] = E[adj[i][j]].flow;   
        }
    }
        
    FOR(i,recall)
    {
        printf("%d %d %d\n",rec_u[i],rec_v[i],F[rec_u[i]][child+1+i]);   
    }
    
    for(int i = recall; i < total_purchase; ++i)
    {
        vector<int> temp;
        
        REP(c,1,child) if(F[c][child+1+i])
        temp.push_back(c);
        
        if(temp.size() == 2)
        printf("%d %d 1\n",temp[0],temp[1]);
        else
        printf("%d %d 2\n",temp[0],(temp[0]==1?2:1));   
    }
}

int main()
{    
    
    scanf("%d%d",&child,&recall);
    
    total_card = 0;
    
    REP(i,1,child)
    {
        scanf("%d",card+i);
        total_card += card[i];
    }
    
    FOR(i,recall)
    {
        scanf("%d%d",rec_u+i,rec_v+i);
    }
    
    build_network();
    max_flow();
    output();
        
    return 0;
}

this blog is inspired by: http://one-problem-a-day.blogspot.com

One Solution of the Palindromic-Prefix Problem

This is a follow-up of my last post titled "A Sub-Problem, A funny bug". On that post I wrote about a problem and stated the fact that, I had an idea of a solution using some alien algorithm called Z-algorithm and also about my failed attempt to solve it using the more familiar KMP algorithm.

But (happily :D) I did solve it using KMP. The solution is simple and beautiful (ah well... everyone thinks like this after solving an interesting problem :P)!

For convenience, I will state the problem again:
Given a string S of length n. Calculate a boolean array P in O(n) time, where P[k] = true, if the k-length prefix of S is a palindrome, and false otherwise.

Lets recall what the KMP algorithm does. Basically it's a fast algorithm for searching for a given pattern in some text in O(text.length) time with O(pattern.length) preprocessing time.

The preprocessing part is the one, that will provide us the trick to solve this problem. Lets denote the given string as S and it's k-length prefix as S_k. With KMP, we can compute a table pi for S, where pi[k] is the length of the longest suffix of S_k, that is also a prefix of S_k. Note that, here a string is not considered a suffix of itself.

To solve this problem, at first I solved a related question which is, How to find in linear time, what is the length of the longest palindromic prefix of S.

For this, the following observation helped me: If S is a palindrome and also is S_k for some k < S.length, then it's k-length suffix will also be a palindrome and vice verse. But, S will not necessarily be a palindrome.

Here comes the trick! We can, create a new string T = S+reverse_of(S). We shall compute the pi[] (also, know as the prefix function) for T.

Now that, T is a palindrome, min(S.length,pi[2*length]) will the length of the longest palindromic-prefix of S. Lets call this value L. As, S_L is a palindrome, P[L] will be the length of the next longest palindromic prefix and so on..

For example, consider the string:
S = "abacabax".
So, T = "abacabaxxabacaba".

For T, we get these pi[ ] values,
pi[1] = 0
pi[2] = 0
pi[3] = 1
pi[4] = 0
pi[5] = 1
pi[6] = 2
pi[7] = 3
pi[8] = 0
pi[9] = 0
pi[10] = 1
pi[11] = 2
pi[12] = 3
pi[13] = 4
pi[14] = 5
pi[15] = 6
pi[16] = 7 [ this is the value of L ]

Now, we can set,
P[7] = true,
next value for L = 3,[ because, pi[7] = 3 ]
so, we set,
P[3] = true,
next value for L = 1, [ pi[3] = 1 ]
so, we set,
P[1] = true,
next value for L = 0, [ pi[1] = 0 ]
P[0] = true, [ empty string is also a palindrome ]

rest of the indices of P will be set to false.

and we are done!

both the computation of pi and P takes time linear in terms of the length of S. So, we have solved our problem in linear time.

Here is the code that calculates the P[ ] array.

void calc_P(char S[])
{
 int len = strlen(S);

 // append reverse_of(S) with S itself
 for(int i = len-1, j = len; i >= 0; --i, ++j)
 {
     S[j] = S[i];
 } 

 // KMP pre-processing Begins
 pi[0] = -1; // pi[0] is undefined

 for(int i = 0; i < len*2; ++i)
 {
     int k = pi[i];
  
     while(k >= 0 && S[k]!=S[i])
     k = pi[k];
  
     pi[i+1] = k+1;
 }
 // KMP pre-processing Ends
  
 int L = min(len,pi[len*2]); // length of the longest palindrome-prefix

 memset(P,false,sizeof(P)); // set all P[k] to false

 while(L >= 0)
 {
     P[L] = true;
     L = pi[L];
 }
}

I guess I would write on the second way to solve this problem (yeah, that Z-algorithm thing!) because, I need to understand the fairly easy Z-algorithm in depth! :P

Practice Problem (also the parent problem of this sub-problem):
http://www.codeforces.com/contest/7/problem/D


...and, this blog is always inspired by: http://one-problem-a-day.blogspot.com

A Sub-Problem, A funny Bug

Busy Days! Very little time for solving! :(

Problem (Actually a sub-problem of a problem, that I was working on):
Given a string S of length n. Calculate a boolean array P in O(n) time, where P[k] = true, if the k-length prefix of S is a palindrome, and false otherwise.
I have got an idea using some technique known (not much known) as the Z-algorithm. But I was trying to solve it with KMP (no success with that).

I'll try to write on that Z-algorithm-based solution some other day.

BTW, here is a very nice tutorial of the simple and interesting, Z-algorithm.

And here is a nice(!!) bug, that I made recently. The following function was causing TLE.

// the size of the input vector v is at most 50
int calc(vector<int>& v)
{
 int ret = 0;

 for(int i = 0; i < v.size()-1; ++i)
 {
   // do some constant time work...
 }

 return ret;
}

Why? Because, v.size() returns an unsigned value. So, when the input vector is empty, the expression (v.size()-1) evaluates to 4294967295. So, the loop was never breaking. As the loop counter i was a signed int type variable, it was never reaching this large value.

this blog is inspired by: http://one-problem-a-day.blogspot.com

SPOJ (Ambitious Manager)

This is an interesting math problem.

For the solution, you just have to observe and prove that, b_i > b_i-1 + b_i-2+ ... + b₁ for all i > 1. The question is, how one might observe this fact. That's when 'numerical experimentation' can help you. Just write down some (say, 10) random values of a_i on paper and calculate the corresponding values of b_i and you will see it.

This can be proved with induction.

For the base case, note that, b₂ > b₁ because, b₂ = a₂ + 2*a₁ = a₂ + 2*b₁. (a_i > 0 for all i)

In fact, from the definition of b_i it is clear that,
b_i = a_i + 2*b_i-1.

Now, lets assume that, b_n-1 > b_n-2+ ... + b₁ for some n > 2
b_n = a_i + 2*b_i-1
therefore, b_n > a_i + 2*(b_i-2+ ... + b₁) (by the induction hypothesis)

This poof leads to the following conclusion:
Let, b_i be the maximum number such that b_i ≤ N. We must take this value, otherwise it will be impossible to build N from the rest of the values.

So, you have to take the maximum b_i not exceeding N and replace N with N-b_i, as long as it is possible. If, you reach 0, you are done. Just print the positions of the taken numbers. Otherwise print a -1.

Note that, there will never be multiple solutions.
In fact, for any sequence S of integers such that, S_i > S_i-1 + S_i-2 + ... + S₁. Every subset of S yields a different sum.

To see this, consider two different subsets A and B. Without loss of generality, assume that, sum(A) ≥ sum(B), where, sum(X) is the sum of the elements of subset X. Let, k be the largest index such that, S_k is included in A but not in B. According to the proof described above, S_k will always be greater than the sum of all S_i, where k > i and S_i is included in B. So, sum(A) != sum(B) (i.e. A > B)

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>
#include<ctype.h>

#include<vector>
#include<set>
#include<map>
#include<string>
#include<stack>
#include<queue>
#include<iostream>
#include<algorithm>

using namespace std;

typedef long long LL;
typedef pair<int,int> pii;

#define FOR(A,B) for(int A = 0; A < (B); ++A)
#define REP(A,B,C) for(int A = (B); A <= (C); ++A)
#define CLR(X,Y) memset(X,(Y),sizeof(X))


int main()
{
   LL a[55], b[55];
   int T; scanf("%d",&T);
  
   while(T--)
   {
       LL n;
       int k; cin>>n>>k;
              
       FOR(i,k)
       {
           cin>>a[i];
          
           if(i==0) b[i] = a[i];
           else b[i] = (b[i-1]<<1)+a[i];
       }   
              
       vector<int> ans;
      
       for(int i = k-1; i >= 0; --i)
       {
           if(b[i]<=n)
           {
               ans.push_back(i+1);
               n -= b[i];  
           }  
       }
      
       if(n > 0)
       {
           puts("-1");  
       }
       else
       {           
           for(int i = ans.size()-1; i >= 0; --i)
           if(i<ans.size()-1) printf(" %d",ans[i]);
           else printf("%d",ans[i]);
          
           puts("");  
       }
   }
  
   return 0;
}

this blog is inspired by: http://one-problem-a-day.blogspot.com

Codeforces Round #41, Problem-C (Safe Cracking)

Problem Link: Safe Cracking

I could not solve this problem in the contest. My greedy solution was wrong. I submitted it without proof (didn't have time for that) and it failed the system test.

I have solved it later with the correct greedy idea described bellow:

Solution:
initially we have a cyclic 4-tuple {A,B,C,D}. (i.e. D and A are consecutive)

The solution works iteratively. At each step, we decide to perform one of the following operations based on the parities of {A,B,C,D}.

(1) if there are 2 consecutive even numbers, we divide both of them by 2, and repeat this step.
(2) if there are 2 consecutive odd numbers and at least one of them is greater than 1, we increase them by 1 and go back to step 1.
(3) we find two consecutive numbers such that, their parities are different. Increase them by 1 and go back to step 1.

Proof:
We have to prove 2 things: (i) the algorithm terminates with {1,1,1,1} (ii) it doesn't take more than 1000 steps.

The key observation is that, the algorithm never performs the increment operation for more than 1 consecutive steps. It is performed in case of one of the following combination of parities:

a. {odd,odd,odd,odd}
b. {odd,even,odd,even}
c. {even,odd,even,odd}

an increment operation on any of these combinations produces two consecutive even numbers which gets divided by 2 in the next step.

So, in every two consecutive steps, there is at least one division operation. This can not go forever.

So, we can conclude that, the algorithm terminates after a finite step with {1,1,1,1}.

The number of steps required is O(log₂M) where M is the maximum number among {A,B,C,D}. This ensures that, it never takes more than 1000 steps.

Here is the Accepted c++ code implementing this idea:

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>
#include<ctype.h>

#include<vector>
#include<set>
#include<map>
#include<string>
#include<stack>
#include<queue>
#include<iostream>
#include<algorithm>

using namespace std;

typedef long long LL;
typedef pair<int,int> pii;

#define FOR(A,B) for(int A = 0; A < (B); ++A)
#define REP(A,B,C) for(int A = (B); A <= (C); ++A)
#define CLR(X,Y) memset(X,(Y),sizeof(X))

int main()
{
int a[4];
FOR(i,4) scanf("%d",a+i);

while(1)
{
  if(a[0]==1&&a[1]==1&&a[2]==1&&a[3]==1) break;

  bool done = false;

  FOR(i,4)
  {
      if( a[i]%2==0 && a[(i+1)%4]%2==0 )
      {
          printf("/%d\n",i+1);
          a[i]>>=1;
          a[(i+1)%4]>>=1;
          done = true;
          break;
      }
  }

  if(done) continue;

  FOR(i,4)
  {
      if( a[i]%2==1 && a[(i+1)%4]%2==1 && max(a[i],a[(i+1)%4])>1)
      {
          printf("+%d\n",i+1);
          a[i]++;
          a[(i+1)%4]++;
          done = true;
          break;
      }
  }

  if(done) continue;

  int pos = 0;

  FOR(i,4)
  {
      if(a[i]%2 != a[(i+1)%4]%2) pos = i;
  }

  a[pos]++;
  a[(pos+1)%4]++;

  printf("+%d\n",pos+1);
}

return 0;
}

This blog is inspired by: http://one-problem-a-day.blogspot.com

Hello World !

This blog is inspired by:
http://one-problem-a-day.blogspot.com

I wish to write daily on the interesting problems I work on ( i.e. whether I can solve them or fail )
This will help me in developing a more organized thinking style.