SRM 440 div-1 Hard (SquareFreeSets)

Problem Link

The problem in short:

A square-free number is an integer that is not divisible by the square of any integer except 1. A set containing only square-free numbers is called a square-free set. The product of such a set is the product of all its elements. If the product of a square-free set is a square-free number itself, that set is called a perfect set.

You are given two ints N and K. Determine the number of perfect square-free sets that contain between 1 and K elements, inclusive, where each element is between 2 and N, inclusive. Return this number modulo 1,000,000,007.

Some observations:

1. In the prime factorization of a square-free number, each of it's prime factors occurs exactly once.
2. There are 95 prime numbers smaller than 500. So, the size of a perfect square-free set can't exceed 95.
3. There are only 8 primes {2,3,5,...,19} smaller than the square-root of 500.
4. In the prime factorization of any integer x, there can be at most 1 prime, which is greater than sqrt(x).
5. So, in the prime factorization of a square free number x <= 500, at most one prime p > 19, can exist.

The Dynamic Programming Solution:

Divide the numbers (1 to N) into buckets. Let, LP(x) be the largest prime factor of x. Two numbers x and y will be kept in the same bucket if and only if LP(x) = LP(y). Note that, in a perfect square-free set, no 2 elements will be from the same bucket.

Lets define dp[i][len][mask] to be the the number of perfect square-free sets of size 'len' and the elements are taken from the buckets 0,1,...i. 'mask' is a bit-mask that represents which of the 8 primes are already used. The rest is easy!

Here is the code that I submitted in the practice room:

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <iostream>

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

const LL mod = 1000000007;
             
vector<pii> buck[505];
vector<int> primes;

bool is[505];
int smallPrimes[] = {2,3,5,7,11,13,17,19};
int pos[25];

void precalc(int n)
{
for(int i = 0; i < 8; ++i)
pos[smallPrimes[i]] = i;

for(int i = 2; i <= n; ++i)
{
 bool isSqFree = true;
 int temp = i, mask = 0;

 for(int j = 2; j*j <= temp; ++j)
 {
  int cnt = 0;
 
  while(temp%j==0)
  {
   temp /= j;
   ++cnt;
  }
 
  if(cnt)
  {
   mask|=(1<<pos[j]);
  }
 
  if(cnt>1)
  {
   isSqFree = false;
  }
 }

 if(temp > 1 && temp*temp<=n)
 {
  mask |= (1<<pos[temp]);
 }

 if(isSqFree)
 {
  buck[temp].push_back(pii(i,mask));
 }

 if(temp==i)
 {
  primes.push_back(i);
 }
}
}

LL dp[100][100][1<<8];

LL F(int i, int len, int mask)
{
if(len == 0) return 1;

if(i < 0) return 0;

LL& ret = dp[i][len][mask];
int p = primes[i];
if(ret>-1) return ret;

ret = F(i-1,len,mask);

FOR(j,buck[p].size())
{
 if((buck[p][j].second&mask)==0)
 {
  ret = (ret + F(i-1,len-1,mask|buck[p][j].second))%mod;
 }
}

return ret;
}

int calc(int k)
{
if(k > primes.size())
k = primes.size();

CLR(dp,-1);
LL ret = 0;

for(int len = 1; len <= k; ++len)
{
 ret = (ret + F(primes.size()-1,len,0))%mod;
}

return (int)ret;
}

class SquareFreeSets {
public:
int countPerfect(int N, int K) {
 precalc(N);
 return calc(K);
}
};

On MMOD29 (SPOJ)

Yesterday I solved this problem.
You can find a nice analysis of the solution here.

A Modified Version:

Find the multiplication of all the divisors of (2004)^x modulo 29

is it possible ?

This question arose in my mind recently, while working on a similar problem:

Given an integer array A with n integers. R is an array of size n where R[i] denotes the number of distinct j, such that i < j and A[i] ≥ A[j]. Is it possible to calculate R in O(n) time?

The Answer:

This is not possible in the general case. Because, if it was possible, then we could have designed an O(n) sorting algorithm for arbitrary integer arrays in the following way:

Lets assume that it is possible to compute the array R in O(n) time. Note that, in that case, it would also be possible to compute another similar array L of size n, where L[i] denotes the number of distinct j, such that i > j and A[i] ≥ A[j].

Now, L[i]+R[i] is the number of distinct j such that, i ≠ j, and A[j] ≤ A[i]. This tells us, for each i, where to place the number A[i] in the sorted array and sort A in O(n).

Question:

Is it possible to solve the task in O(n) time, if the numbers in A are small positive integers (say ≤ 1000).

A Problem From The Sixth IMO (1964)

I am passing a very busy time because of my undergraduate thesis!

But still I managed to solve this really entertaining problem from the sixth IMO:

Problem Description:

Each of 17 students talked with every other student. They all talked about three different topics. Each pair of students talked about one topic. Prove that, there are three students that talked about the same topic among themselves.

An obvious way to restate the problem is:

Given a complete graph with 17 nodes. Each edge is colored with one of three colors. Prove that, there exists a triangle (i.e. cycle of length 3) such that, all three edges are colored with the same color.

Initially I had no idea how to attack the problem. I started drawing a complete graph with 17 nodes which turned out to be a jungle of edges! So, I had to simplify the problem somehow to make it more accessible. Now, what makes the problem hard ? Clearly, the size 17 is a bit too high to draw some graphs and try to understand what happens when we color the edges.

So, I came up with the following simpler problem, by solving which, I got the required insight to solve the original problem.

The Simpler Problem:

Given a complete graph with 6 nodes. Each edge is colored either red or blue. Prove that, there exists a triangle with all three edges colored with the same color.

Now, this problem is more accessible in a sense, because it is easier to draw a complete graph with 6 nodes and color the edges with 2 colors and try to understand what happens.

How did I come up with these numbers, 6 nodes, 2 colors ? Well, I drew a few complete graphs with 4 nodes, 5 nodes and then 6 nodes and found that, I could not color the 6-node-graph with 2 colors without creating a critical triangle (lets denote those single-colored-triangle by this name)

A Journey to the solution of "the simpler problem":

I kept experimenting with this smaller problem and the following observations emerged one by one:

1. If edge (a,b) and (a,c) are colored red then, edge (b,c) must be colored blue (if we want to avoid creating critical triangles)
2. if edge (a,b) and (a,c) are colored red and edge (c,d) and (b,d) are colored blue then, we are in a situation where critical triangle is unavoidable, whether we color the edge (b,c) red or blue.
3. if all of the edges (a,d), (b,d) and (c,d) are colored red, we cannot avoid a critical triangle, because, coloring any one of the edges (a,b), (b,c) or (c,a) with color red will create a red triangle and coloring all of them with color blue will create a blue triangle.

The last observation is the most important one! Because, it is easy to show that, this circumstance is unavoidable in case of 6 nodes and 2 colors. Why?

As the graph is a complete graph of 6 nodes, every node will have 5 edges adjacent to it. If we color those 5 edges with 2 colors, then by the pigeonhole principle, at least 3 edges will have the same color. And we are done, because this is the situation of the above image! The simpler problem is solved! And, this has provided us with an insight and a technique that will be directly useful in the solution of the actual problem.

So, here is the solution to the main problem:

Here, the complete graph has 17 nodes and we have 3 colors to color the edges. Any node u has 16 edges adjacent to it. By the pigeonhole principle, at least 6 of those edges will have the same color (say, red). denote the nodes on the other side of those edges to be v₁, v₂ ... v₆. Note that, we cannot color any of the edges-among-them red because, this will create a red triangle. So, the edges among v₁, v₂ ... v₆ must be colored with the other 2 colors! And Here We Are! This is exactly the smaller version of the problem (6 nodes, 2 colors) that we have solved earlier.
Note that, instead of describing the final solution formally in mathematical language, I have tried to describe the way I have attacked the problem. This is because, that is the real-fun-part of problem-solving!

An Easy Exercise:
Find the minimum number of nodes of a complete graph, for which there always exists a critical-triangle (defined earlier) if we color the edges with four colors.

Answer to the Tilling-Puzzle Question

Today I am going to post the stunningly simple answer to the unanswered question from my last post. I couldn't solve it myself. So, I just saw the solution.

The Question was,
If you are given an 8x8 chessboard and infinite supply of (1 x 3) and (3 x 1) tiles, is it always possible to tile the chessboard using some of these tiles, if the position of the single uncovered cell is specified?

The Beautiful Answer:


Let's number the (8 x 8) board like the figure above. Here, we have 21 cells numbered 2, 21 numbered 3 and 22 numbered 1. A single tile covers three different numbers. So, the board cannot be covered if the uncovered cell is specified to be a cell with a 2 or 3 on it.

This beautiful technique of proof is known as Coloring Proof (here, 1, 2 and 3 represents three different 'colors')

The answer doesn't imply that, we are always safe with an uncovered-cell with an 1 on it. So, here is another question:
Which of these cells-containing-an-1 are safe to be kept uncovered ? (here, 'safe' means, it is still tillable).

Let's try to answer to the opposite question, "Which of these cells-containing-an-1 are not safe to be kept uncovered?"

Note that, the top-left cell contains an 1 but it is still an unsafe cell because, it is equivalent to the top-right cell containing a 2 ( the mirror reflection of this board has a 2 on the top-left cell ).

So, we might claim that, those cells that contain 1, both before and after the reflection of the board along the x-axis or y-axis, are safe to be kept uncovered.

There are four such cells. If we number rows and columns with numbers 1 to 8 then those safe cells are (3,3), (3,6), (6,3) and (6,6). Because of the symmetry of the board, proving the safety for one of these cells would prove for all four. And, we have already proved it for cell (3,6) in the previous post ( the solution image ).

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.