f(f(x)) = -x, A neat Puzzle!

I found this problem in some blog that I don't remember:

The Problem:
Write a C function f(x) that takes an integer x and returns another integer such that f(f(x)) = -x
You are not allowed to use any global variables or static variables or file operations.

The Solution:
Let f(x) = y, then f(y) = -x
so f(-x) = -y                          [ -y = f(f(y)) = f(-x) ]
and f(-y) = x                          [ x = f(f(-x)) = f(-y) ]

f(x) creates a cycle of integers: (x) ==> (y) ==> (-x) ==> (-y) ==> (x)


So, we have to partition the set of natural numbers into cycles of length 4. But, 0 is a special case. f(0) = 0.
For example, one such partition can be:
(1) ==> (2) ==> (-1) ==> (-2) ==> (1)
(3) ==> (4) ==> (-3) ==> (-4) ==> (3)
(5) ==> (6) ==> (-5) ==> (-6) ==> (5)
... and so on

[Edit: the following portion has been added after misof correctly pointed out my mistake]

It is impossible to write a C function that solves the problem completely. We can represent 2^B numbers using B bits. The range is [ -(2^B) to (2^B)-1 ]. Note that, the 2^B doesn't exist in the domain, so, the problem is unsolvable for -(2^B). In fact, there will be another number for which we can't solve it. Let's see why.

Note that, 0 can't be part of a cycle of length 4.

Let, f(0) = 0. That leaves (2^B)-1 numbers to partition into cycles of length 4. But [(2^B)-1]%4 = 3. So, there will be 3 numbers left to be partitioned. We can create a partial cycle with these 3 numbers so that exactly one of them will be matched with it's negative. One of these three numbers will be -(2^B). So, there will be 2 unlucky numbers.

Let, f(0) = x, for some x != 0. If we want f to work for 0, f(x) must map x to 0. We get a cycle of length 2 where x is unlucky. It's better to chose x = -(2^B). That leaves (2^B)-2 numbers. After partitioning into cycles of length 4, 2 numbers will be left: y and -y. We can solve for exactly one of them by assigning f(y) = -y and f(-y) = -y. or vice versa. So, one of these 2 will be unlucky.

In both case, 2 numbers are unlucky!


But the following function partially works for all integers except -(2^31) and (2^31)-1:

int f(int x){
    if(x==0) return 0;

    if(x>0){
        if(x%2==1)
            return x+1;
        else
            return -(x-1);
    }else{
        if((-x)%2==1)
            return x-1;
        else
            return -(x+1);
    }
}

My Practice Log (Google Spreadsheet)

Here is the Google spreadsheet that I try to maintain.

This helps me to track my progress.
Ever since I have started this spreadsheet I didn't have any abrupt-long-break of problem solving.
Whenever I write "NOTHING" in the "What did I do?" column, I feel guilty! :-)

A probable mistake while overloading the '<' operator

I was not aware of the following basic thing. See the code segment bellow:

struct T
{
    int a, b;
    
    T(){}
    T(int _a, int _b){a=_a;b=_b;}
    
    bool operator < (T obj) const
    {
        return a < obj.a;
    }
};

int main()
{
 set<T> S;
 
 S.insert(T(0,0));
 S.insert(T(0,1));
 
 cout<<S.size()<<"\n";
 
    return 0;
}

The output of the given code is: 1 (I was surprised!)
The overloaded operator '<' can not distinguish between T(0,0) and T(0,1) (pretty basic.. huh!)

I learnt this when writing the State class for a Dijkstra's code. I was using STL set as the priority queue. Some nodes were "mysteriously" vanishing!

The overloaded operator should look like this:

    bool operator < (T obj) const
    {
        if(a!=obj.a)
            return a < obj.a;
        else
            return b < obj.b;
    }

Although this doesn't matter if you use a STL priority_queue. It can store more than one copy of the 'same' thing. But sometimes you need to use set, specially when deleting-nodes from the priority queue is important.

SPOJ ORDERSET (With Treap)

I LOVE TREAP !!


Honestly! Treap is the most beautiful Data Structure I know!
In my previous post I solved This Problem with Splay Tree which was more than 500 lines of code and took 5.98 seconds to run on SPOJ.

I solved the same problem with Treap this time and it's only a little over 200 lines that runs in 4.42 seconds on SPOJ.

The following implementation is based on the code given Here.

// SPOJ: ORDERSET
// using Treap
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<ctype.h>
#include<stdlib.h>
#include<time.h>
#include<assert.h>

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

using namespace std;

#define FOR(i,n) for(int i=0;i<(n);++i)
#define REP(i,a,b) for(int i=(a);i<=(b);++i)
#define CLR(a,x) memset(a,(x),sizeof(a))

#define INF (1<<30)

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

struct Node {
    int key;
    int cnt;
    int priority;

    Node *left, *right;

    Node(){cnt = 0; priority = 0; left = right = NULL;}
    Node(int _key){cnt = 1; key = _key; priority = rand(); left = right = NULL;}
    Node(int _key, int pr){cnt = 1; key = _key; priority = pr; left = right = NULL;}
};

struct Treap {
    Node* root;

    Treap(){root = NULL; srand(time(NULL));}

    int TreeSize(Node* T)
    {
        return T==NULL?0:T->cnt;
    }

    void UpdateCnt(Node* &T)
    {
        if(T)
        {
            T->cnt = 1 + TreeSize(T->left) + TreeSize(T->right);
        }
    }

    void LeftRotate(Node* &T)
    {
        Node* temp = T->left;
        T->left = temp->right;
        temp->right = T;
        T = temp;

        UpdateCnt(T->right);
        UpdateCnt(T);
    }

    void RightRotate(Node* &T)
    {
        Node* temp = T->right;
        T->right = temp->left;
        temp->left = T;
        T = temp;

        UpdateCnt(T->left);
        UpdateCnt(T);
    }

    void Insert(Node* &T, int _key)
    {
        if(T == NULL)
        {
            T = new Node(_key);
            return;
        }

        if(T->key > _key)
        {
            Insert(T->left, _key);

            if(T->priority < T->left->priority)
                LeftRotate(T);
        }
        else if(T->key < _key)
        {
            Insert(T->right, _key);

            if(T->priority < T->right->priority)
                RightRotate(T);
        }

        UpdateCnt(T);
    }

    void Insert(int _key)
    {
        Insert(root, _key);
    }

    void Delete(Node* &T, int _key)
    {
        if(T == NULL)
            return;

        if(T->key > _key)
            Delete(T->left, _key);
        else if(T->key < _key)
            Delete(T->right, _key);
        else
        {
            if(T->left && T->right)
            {
                if(T->left->priority > T->right->priority)
                    LeftRotate(T);
                else
                    RightRotate(T);

                Delete(T, _key);
            }
            else
            {
                Node* temp = T;

                if(T->left)
                    T = T->left;
                else
                    T = T->right;

                delete temp;
            }
        }


        UpdateCnt(T);
    }

    void Delete(int _key)
    {
        Delete(root, _key);
    }

    int Count(Node* T, int bound)
    {
        if(T == NULL)
            return 0;

        if(T->key < bound)
            return 1 + TreeSize(T->left) + Count(T->right, bound);

        return Count(T->left, bound);
    }

    int Count(int bound)
    {
        return Count(root,bound);
    }

    int FindKth(Node* T, int k)
    {
        if(TreeSize(T) < k)
            return -INF;

        int sz = 1 + TreeSize(T->left);

        if(sz == k)
            return T->key;

        if(sz < k)
            return FindKth(T->right, k-sz);

        return FindKth(T->left,k);
    }

    int FindKth(int k)
    {
        return FindKth(root, k);
    }
};

int main()
{
    // freopen("in.txt","r",stdin);

    int Q; scanf("%d",&Q);

    Treap oTreap;

    while(Q--)
    {
        char t[5];
        int p;
        scanf("%s%d",t,&p);

        if(t[0]=='I')
        {
            oTreap.Insert(p);
        }
        else if(t[0]=='D')
        {
            oTreap.Delete(p);
        }
        else if(t[0]=='K')
        {
            int v = oTreap.FindKth(p);

            if(v > -INF)
            {
                printf("%d\n",v);
            }
            else
                puts("invalid");
        }
        else
        {
            int v = oTreap.Count(p);

            printf("%d\n",v);
        }

    }

    return 0;
}

A needlessly long but Correct Splay Tree implementation

What follows is the Accepted solution of This Problem
I wish to write a shorter splay tree soon

// Splay Tree Implementation
// used for SPOJ Problem: ORDERSET

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

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

using namespace std;

#define FOR(i,n) for(int i=0;i<(n);++i)
#define REP(i,a,b) for(int i=(a);i<=(b);++i)
#define CLR(a,x) memset(a,(x),sizeof(a))

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

#define INF (1<<30)

#define KEY_TYPE int

class Node
{
private:
    KEY_TYPE    key;
    int         cnt; // size of the subtree rooted here

    Node* left;
    Node* right;
    Node* parent;

    int calcTreeSize();

public:
    bool isLeftChild();
    bool isRightChild();
    bool isRoot();

    KEY_TYPE getKeyVal();
    int      getCnt();

    void Rotate();
    void Zig();
    void ZigZig();
    void ZigZag();

    bool NormalBSTInsert(Node* newNode);
    void Splay();
    void SplayUntil(Node* until);

    Node();
    Node(const KEY_TYPE _key);

    ~Node();

    Node* FindNearest(const KEY_TYPE _key);
    bool Exists(const KEY_TYPE _key);
    void Insert(KEY_TYPE _key);
    void Insert(Node* newNode);
    void Delete();
    void Delete(KEY_TYPE _key);

    void PrintInOrder();
    void PrintPreOrder();

    KEY_TYPE findKth(int k);
    int Count(KEY_TYPE _key);
};


Node* ROOT;

bool Node::isLeftChild()
{
    return (this->parent!=NULL && this->parent->left == this);
}

bool Node::isRightChild()
{
    return (this->parent!=NULL && this->parent->right == this);
}

bool Node::isRoot()
{
    return this->parent == NULL;
}

KEY_TYPE Node::getKeyVal()
{
    return this->key;
}

int Node::getCnt()
{
    return this->cnt;
}

int Node::calcTreeSize()
{
    return 1 + (this->left?this->left->cnt:0) + (this->right?this->right->cnt:0);
}

void Node::Rotate()
{
    if(isLeftChild())
    {
        bool parWasLeftChild = this->parent?this->parent->isLeftChild():false;

        parent->left = this->right;

        if(this->right)
            this->right->parent = this->parent;

        Node* newParent = this->parent->parent;

        this->right = this->parent;

        if(this->right)
            this->right->parent = this;

        this->parent = newParent;

        if(this->parent != NULL)
        {
            if(parWasLeftChild)
                this->parent->left = this;
            else
                this->parent->right = this;
        }

        this->right->cnt = this->right->calcTreeSize();
        this->cnt = this->calcTreeSize();
    }
    else if(isRightChild())
    {
        bool parWasLeftChild = this->parent?this->parent->isLeftChild():false;

        parent->right = this->left;

        if(this->left)
            this->left->parent = parent;

        Node* newParent = this->parent->parent;

        this->left = this->parent;

        if(this->left)
            this->left->parent = this;

        this->parent = newParent;

        if(this->parent != NULL)
        {
            if(parWasLeftChild)
                this->parent->left = this;
            else
                this->parent->right = this;
        }

        this->left->cnt = this->left->calcTreeSize();
        this->cnt = this->calcTreeSize();
    }
}

void Node::Zig()
{
    Rotate();
}

void Node::ZigZig()
{
    this->parent->Rotate();
    this->Rotate();
}

void Node::ZigZag()
{
    this->Rotate();
    this->Rotate();
}

void Node::Splay()
{
    while( !this->isRoot() )
    {
        if(this->parent->isRoot()) // Zig
        {
            this->Zig();
        }
        else if(this->isLeftChild() == this->parent->isLeftChild()) // ZigZig
        {
            this->ZigZig();
        }
        else // ZigZag
        {
            this->ZigZag();
        }
    }

    ROOT = this;
}

Node::Node()
{
    key     = 0;
    cnt     = 0;
    left    = NULL;
    right   = NULL;
    parent  = NULL;
}

Node::Node(const KEY_TYPE _key)
{
    key     = _key;
    cnt     = 1;
    left    = NULL;
    right   = NULL;
    parent  = NULL;
}

Node::~Node()
{

}

Node* Node::FindNearest(const KEY_TYPE _key)
{
    Node *ret = this;

    while(true)
    {

        if(ret->key < _key)
        {
            if(ret->right)
            {
                ret = ret->right;
            }
            else
                break;
        }
        else if(ret->key > _key)
        {
            if(ret->left)
            {
                ret = ret->left;
            }
            else
                break;
        }
        else
        {
            break;
        }
    }

    return ret;
}

bool Node::Exists(const KEY_TYPE _key)
{
    Node* temp = this->FindNearest(_key);
    temp->Splay();

    return ROOT->key == _key;
}

// returns false if a node with key = newNode->key already exists in the tree
bool Node::NormalBSTInsert(Node* newNode)
{
    Node* curNode = this;
    bool alreadyThere = false;

    while(true)
    {
        if(newNode->key > curNode->key)
        {
            if(curNode->right)
            {
                curNode = curNode->right;
            }
            else
            {
                curNode->right = newNode;
                newNode->parent = curNode;
                break;
            }
        }
        else if(newNode->key < curNode->key)
        {
            if(curNode->left)
            {
                curNode = curNode->left;
            }
            else
            {
                curNode->left = newNode;
                newNode->parent = curNode;
                break;
            }
        }
        else
        {
            alreadyThere = true;
            break;
        }
    }

    if(!alreadyThere)
    {
        Node* temp = newNode->parent;

        while(temp)
        {
            temp->cnt = temp->calcTreeSize();
            temp = temp->parent;
        }

        return true;
    }
    else
        return false;
}

void Node::Insert(KEY_TYPE _key)
{
    this->Insert(new Node(_key));
}

void Node::Insert(Node* newNode)
{
    if(newNode == NULL)
        return;

    if(this->NormalBSTInsert(newNode))
        newNode->Splay();
}

void Node::SplayUntil(Node* until)
{
    Node* grandParent = until->parent;

    while(this->parent != grandParent)
    {
        if(this->parent == until) // zig
        {
            this->Zig();
        }
        else if(this->isLeftChild() == this->parent->isLeftChild()) // zigzig
        {
            this->ZigZig();
        }
        else
            this->ZigZag();
    }
}

void Node::Delete()
{
    this->Splay();

    if(this->left)
    {
        Node* maxNode = this->left->FindNearest(INF);
        maxNode->SplayUntil(this->left);

        this->left->right = this->right;

        if(this->right)
            this->right->parent = this->left;

        ROOT = this->left;
        ROOT->parent = NULL;
        ROOT->cnt = ROOT->calcTreeSize();
    }
    else if(this->right)
    {
        Node* minNode = this->right->FindNearest(-INF);
        minNode->SplayUntil(this->right);

        this->right->left = this->left;

        if(this->left)
            this->left->parent = this->right;

        ROOT = this->right;
        ROOT->parent = NULL;
        ROOT->cnt = ROOT->calcTreeSize();
    }
    else
    {
        ROOT = NULL;
    }
}

void Node::Delete(KEY_TYPE _key)
{
    if(this->Exists(_key))
    {
        Node* forDelete = ROOT; // the Exists method splays the node to the root
        ROOT->Delete();
        delete forDelete;
        forDelete = NULL;
    }
}

KEY_TYPE Node::findKth(int k)
{
    if(this->cnt < k)
        return -INF;

    Node* temp = this;

    while(true)
    {
        int c = (temp->left?temp->left->cnt:0) + 1;

        if(c == k)
            break;

        if(c < k)
        {
            k -= c;
            temp = temp->right;
        }
        else
        {
            temp = temp->left;
        }
    }

    temp->Splay();
    return ROOT->key;
}

int Node::Count(KEY_TYPE _key)
{
    Node* temp = this;

    int ret = 0;

    while(true)
    {
        if(temp->key < _key)
        {
            int c = (temp->left?temp->left->cnt:0)+1;

            ret += c;

            if(temp->right)
            {
                temp = temp->right;
            }
            else
            {
                break;
            }
        }
        else if(temp->key > _key)
        {
            if(temp->left)
            {
                temp = temp->left;
            }
            else
                break;
        }
        else
        {
            ret += (temp->left?temp->left->cnt:0);
            break;
        }
    }

    temp->Splay();

    return ret;
}

void Node::PrintInOrder() // not needed for the problem
{
    if(this->left)
        this->left->PrintInOrder();

    cout<<this->getKeyVal()<<" ";

    if(this->right)
        this->right->PrintInOrder();
}

void Node::PrintPreOrder() // not needed for the problem
{
    cout<<"["<<this->getKeyVal()<<":"<<this->cnt<<"]";

    printf("(");
    if(this->left)
        this->left->PrintPreOrder();
    printf(")");

    printf("(");
    if(this->right)
        this->right->PrintPreOrder();
    printf(")");
}

void SplayTreeInsert(KEY_TYPE key)
{
    if(ROOT)
        ROOT->Insert(key);
    else
        ROOT = new Node(key);
}

int main()
{
    int Q; scanf("%d",&Q);

    ROOT = NULL;

    while(Q--)
    {
        char t[5];
        int p;
        scanf("%s%d",t,&p);

        if(t[0]=='I')
        {
            SplayTreeInsert(p);
        }
        else if(t[0]=='D')
        {
            if(ROOT)
                ROOT->Delete(p);
        }
        else if(t[0]=='K')
        {
            int v = -INF;

            if(ROOT)
                v = ROOT->findKth(p);

            if(v > -INF)
            {
                printf("%d\n",v);
            }
            else
                puts("invalid");
        }
        else
        {
            int v = 0;
            if(ROOT)
                v = ROOT->Count(p);

            printf("%d\n",v);
        }

    }

    return 0;
}

SGU-103 Traffic Lights

Problem Link

The Problem in short:
Given an undirected weighted graph where each node contains a traffic light. The light shows two colors: Blue and Purple. Blue is visible for t_b seconds and Purple is visible for t_p seconds. This keeps repeating periodically. These two values may differ for different nodes. Cars can cross an edge (u,v) iff both u and v has same color at the moment when the car departs from u to v.

Now, given a source S and a destination T and the initial state of every node (there current color and how much time is remaining for that color), calculate the minimum time to reach from S to T.

Solution:
Run Dijkstra's from S. The tricky part is: given a time t and a node u such that, the current time is t and the car is at u, when will the light at u and the light at v show the same color ?

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

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

using namespace std;

#define FOR(i,n) for(int i=0;i<(n);++i)
#define REP(i,a,b) for(int i=(a);i<=(b);++i)
#define CLR(a,x) memset(a,(x),sizeof(a))

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

struct State {
    int at;
    int when;

    State(){}
    State(int _at, int _when){at = _at; when = _when;}

    bool operator < (const State other) const
    {
        return when > other.when;
    }
};

const int INF = (1<<29);

vector<int> adj[305];
int nodes, edges;
int cost[305][305];
int from,to;
int dist[305], parent[305];

int remaining[305], initColor[305], duration[305][2];

typedef pair<int,int> colorInfo;

colorInfo getColorInfo(int u, int t)
{
    if(t < remaining[u])
        return colorInfo(initColor[u],remaining[u]-t);

    int M = duration[u][0]+duration[u][1];
    int r = (t-remaining[u])%M;
    if(r < duration[u][1-initColor[u]])
        return colorInfo(1-initColor[u],duration[u][1-initColor[u]]-r);
    else
        return colorInfo(initColor[u],duration[u][initColor[u]]-(r-duration[u][1-initColor[u]]));
}

void getNext4InterestingTime(int u, int t, vector<int>& VT)
{
    VT.push_back(t);
    colorInfo info = getColorInfo(u,t);
    t += info.second;
    VT.push_back(t);

    FOR(i,4)
    {
        if(i%2==0)
            t += duration[u][1-info.first];
        else
            t += duration[u][info.first];

        VT.push_back(t);
    }
}

int calcTime(int u, int v, int t) // currently at u, current time t, want to go to v
{
    vector<int> interestingTime;

    getNext4InterestingTime(u,t,interestingTime);
    getNext4InterestingTime(v,t,interestingTime);

    sort(interestingTime.begin(),interestingTime.end());

    FOR(i,interestingTime.size())
    {
        if(getColorInfo(u,interestingTime[i]).first == getColorInfo(v,interestingTime[i]).first)
            return interestingTime[i];
    }

    return -1;
}

int solve()
{
    REP(i,1,nodes)
        dist[i] = INF;
    dist[from] = 0;
    parent[from] = from;

    State source(from,0);

    priority_queue<State> pq;
    pq.push(source);

    while(pq.empty()==false)
    {
        State u = pq.top();
        pq.pop();

        if(u.when > dist[u.at])
            continue;

        FOR(i,adj[u.at].size())
        {
            int x = adj[u.at][i];
            int y = calcTime(u.at,x,u.when);
            if(y == -1) continue;

            y += cost[u.at][x];
            if(dist[x] > y)
            {
                parent[x] = u.at;
                dist[x] = y;
                pq.push(State(x,y));
            }
        }
    }

    return dist[to];
}

int main()
{
    scanf("%d%d",&from,&to);
    scanf("%d%d",&nodes,&edges);

    FOR(i,nodes)
    {
        char s[5];
        scanf("%s%d%d%d",s,&remaining[i+1],&duration[i+1][0],&duration[i+1][1]);

        if(s[0]=='B')
            initColor[i+1] = 0;
        else
            initColor[i+1] = 1;
    }

    FOR(e,edges)
    {
        int u,v,w; scanf("%d%d%d",&u,&v,&w);
        adj[u].push_back(v);
        adj[v].push_back(u);
        cost[u][v] = cost[v][u] = w;
    }

    int ans = solve();

    if(ans >= INF)
    {
        puts("0");
    }
    else
    {
        vector<int> path;

        while(1)
        {
            path.push_back(to);
            if(to==from)
                break;
            to = parent[to];
        }

        cout<<ans<<"\n";

        for(int i=path.size()-1;i>=0;--i)
        {
            printf("%d",path[i]);
            if(i>0)
                printf(" ");
        }

        puts("");
    }

    return 0;
}

SPOJ :: KOICOST

Problem Link

The Problem in Short:

Given an undirected weighted graph.
There is a function Cost(u,v), which is defined as follows:
While there is a path between vertex u and v, delete the edge with the smallest weight. Cost(u,v) is the sum of the weights of the edges that were deleted in this process.
your task is to calculate the sum of Cost(u,v) for all pairs of vertices u and v, where u < v

The Solution:

To describe the solution we'll need a few notations:

bound(x,y) = the last edge, that has to be deleted if we want to disconnect vertex x and y by the process described in the problem statement.
f(u,v) = number of pair of vertices (x,y) such that, bound(x,y) = edge (u,v)
w(u,v) = weight of the edge (u,v)
csum(u,v) = cumulative sum of weights of all edge (u',v') such that w(u',v') <= w(u,v)

so, result = sum over ( csum(u,v)*f(u,v) ) for all edge (u,v)


Now, the problem is to calculate f(u,v) efficiently.

Consider the following process which is the reverse of the process described in the problem statement.

Lets assume that, initially all the vertices are disconnected. We add the edges one by one in the decreasing order of their weights.

define, g(u,v) = the number of pair of vertices (x,y) such that, (x,y) becomes connected when we add the edge (u,v) in the reverse process.

Note that, f(u,v) = g(u,v) (the proof is left to the reader)

Here is the algorithm that calculates g(u,v) for all the edges.

1. sort all the edges in the decreasing order of their weights
2. create a disjoint set of for all the nodes. (yes, we'll need the disjoint-set data structure)
3. in the root of each disjoint set, store the size of that set.
let's denote by sz(u), the size of the disjoint set that vertex u is in.

4. For each edge (u,v):

if u and v are connected already (i.e. in the same set)
f(u,v) = g(u,v) = 0
else:
f(u,v) = g(u,v) = sz(u) * sz(v)
result = result + f(u,v)*csum(u,v)
disjoint_set_union(u,v)

SPOJ :: PROBOR

Problem Link

type: dynamic programing, probability, expected value.

Solution:

define, dp[i][j][b] = after performing the probabilistic OR on the 0-th to i-th number, what is the probability that, the j-th bit is b.

expected_value = 1*dp[n-1][0][1] + 2*dp[n-1][1][1] + ... 2^k * dp[n-1][k][1] + ...

...hmm, it feels good to be back after a long long break.

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.