12049 – Just Prune The List UVA Solution

This is an easy problem from uva judge http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3200

Data structures, map, set.

How I did it

• I read the number of cases.
• I read the total elements for list 1 and list 2.
• I read the items in the list one. keep a track about the total number of appearances per number in a STL map.
• Insert the current item into a STL set.
• I read the items in the list two. keep a track about the total number of appearances per number in a STL map. (Different maps per list).
• Insert the current item into the STL set.
• Traver the set, and calculate the difference between map1 and map 2 with the current set element.
• Print the answer.

Hints

•  I calculate the different element with the diferent quantity of element for a number in the STL set and O save the appereance of a number in the maps.

Code

#include <cstdio>
#include <cstdlib>
#include <map>
#include <set>
using namespace std;
int main()
{
int casos, l1, l2, val;
scanf("%d", &casos);

while(casos--)
{
    map<int, int> mySet1, mySet2;
    set<int> enums;
    scanf("%d %d", &l1, &l2);
    for(int i=0; i<l1; i++)
    {
        scanf("%d", &val);
        mySet1[val]++;
        enums.insert(val);
    }
    for(int i=0; i<l2; i++)
    {
        scanf("%d", &val);
        mySet2[val]++;
        enums.insert(val);
    }

    int ans = 0, tmp;
    for(set<int>::iterator it=enums.begin(); it!=enums.end(); it++)
    {
        tmp =  abs(mySet1[*it] - mySet2[*it]);
        ans += tmp;
    }
    printf("%d\n", ans);
}
return 0;
}

12646 – Zero or One UVA Solution

This is an easy problem from uva judge http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=4375

Ad hoc, complete search.

How I did it

• Read a, b, c.
• Generate all possible scenarios.
• Print the answer.

Hints

•  We have 8 possibles scenarios. ((states a * states b * states c) = 2 * 2 * 2. Because abc can have 0 or 1).
• Possible input: 0 0 0, 0 0 1, 0 1 0, 1 0 0, 0 1 1, 1 0 1, 1 1 0, 1 1 1

Code

#include <stdio.h>
int main()
{
int a,b,c;
while(scanf("%d %d %d", &a, &b, &c) == 3)
{
    if(a == b && b == c)
      printf("*\n");
    else if(a != b && b == c)
            printf("A\n");
    else if(a != b && a == c)
            printf("B\n");
    else if(a == b && a != c)
            printf("C\n");
}
return 0;
}

10505 – Montesco vs Capuleto UVA Solution

This is an easy problem from uva judge http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1446

Graphs, bfs, bipartite graph.

How I did it

• Read the number of cases.
• For each case read the number of nodes.
• Read the graph into a adjacency list.
• Traverse the graph anc call bfs in every not visited node.
• After the call to bfs check if the graph o subgraph is bipartite. If graph is bipartite count the most bigger group (0 or 1) and add it to the total invitations.
• Print the answer.

Hints

•  In the input we can have the subgraphs.
• My code gives AC using C++ 11.

Code

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef vector<int> vi;

vector <vi> graph;
vector<bool> discovered;
vector<int> parent;
vector<int> distances;

bool  isBipartite;
int zero;
int one;

void read_graph(int nodos)
{
    int vertex, enemies;
    int i;
    for(i = 0; i < nodos; i++)
    {
        scanf("%d", &enemies);
        for(int j=0; j<enemies; j++)
        {
            scanf("%d", &vertex);
            graph[i].push_back(vertex - 1);
            graph[vertex - 1].push_back(i);
        }
    }
}

void init(int nodes)
{
    parent.assign(nodes, -1);//stores the nodes ancestor that discovered it for the first time
    distances.assign(nodes, -1);//stores the distance to reach each node from the source
    zero = one = 0;
}

void countVal()
{
    for(int x=0; x<distances.size(); x++)
    {
        if(distances[x] == 0)
           zero++;
        else if(distances[x] == 1)
                one++;
    }
}

void bfs(int start)
{
    int current;//current node being processed
    int next;//reached node by current
    unsigned int i;
    queue<int> vertices;//vertices to process
    distances[start] = 0;
    discovered[start] = true;
    vertices.push(start);
    isBipartite = true;

    while(!vertices.empty())
    {
        current = vertices.front();
        vertices.pop();
        for(i = 0; i < graph[current].size(); i++)//for each node connected to current
        {
            next = graph[current][i];
            if(!discovered[next])//if it hasn't been reached
            {
                discovered[next] = true;//mark it as reached
                parent[next] = current;//store its parent
                distances[next] = 1 - distances[current];//save the distance
                vertices.push(next);//push it to the queue for further analysis
            }
            else if(distances[next] == distances[current])
            {
                isBipartite = false;
                //break;
            }
        }
    }
}

/*void print()
{
    for(int c=0; c<graph.size(); c++)
    {
        cout<<"Node "<<c<<":";
        for(int d=0; d<graph[c].size(); d++)
        {
            cout<<graph[c][d]<<" ";
        }
        cout<<endl;
    }

}*/

int main()
{
int casos, nodes, total;
scanf("%d", &casos);
while(casos--)
{
    total = 0;
    scanf("%d", &nodes);
    graph.assign(nodes, vi());
    discovered.assign(nodes, false);
    read_graph(nodes);
    init(nodes);
    //print();
    for(int x=0; x<graph.size(); x++)
    {
        if(discovered[x] == false)
        {
            init(nodes);
            bfs(x);
            //print();
            //cout<<"Node call "<<x<<endl;
            //for(int g=0; g<distances.size(); g++)
              //  cout<<distances[g]<<" ";
            //cout<<endl;
            if(isBipartite)
            {
                countVal();
                int tmp = max(zero, one);
                total += tmp;
            }
        }
    }
    printf("%d\n", total);
}
return 0;
}

12247 – Jollo UVA Solution

This is an easy problem from uva judge http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3399

Ad hoc,  complete search, data structures.

How I did it

• Read the cards from the princess, read the cards from the prince.
• If the cards are equal to 0 stop the program.
• Generate all possible games with the cards. (12 possibles games).
• For every game find the lowest card to win the game and save that card in a set of probable answers.
• In all possible games try every possible answer and check if is enough to win every game.(12 games).
• Print the answer.

Hints

•  Generate all possible games. (Always 12)
• The possible status of a game for prince:  Win Win, Win Lose, Lose Win, Lose Lose.
• If we have a game Lose Lose, print -1.

Critical Input

1 2 3 51 52

Critical Output

4

Code

#include <iostream>
#include <cstdio>
#include <vector>
#include <bitset>
#include <set>
using namespace std;
typedef pair<int,int> ii;

struct game
{
    ii p1;
    ii p2;
    ii p3;
};

vector<int>girl,boy;
vector<game> gameArray;
bitset<54> myCards;
set<int> mySet;

bool isWW(int pos)
{
    game tmp = gameArray[pos];

    if(tmp.p1.first < tmp.p1.second && tmp.p2.first < tmp.p2.second)
       return true;
    else
        return false;
}

vector<int> getNotUsed(int x, vector<int>vec)
{
    vector<int> ans;

    for(int a=0; a<vec.size(); a++)
        if(x!=a)
           ans.push_back(vec[a]);
return ans;
}

void generate()
{
    vector<int> nGirl, nBoy;
    for(int x=0; x<girl.size(); x++)
    {
        for(int y=0; y<boy.size(); y++)
        {
            ii p1 = make_pair(girl[x], boy[y]);

            nGirl = getNotUsed(x,girl);
            nBoy  = getNotUsed(y, boy);

            ii p2 = make_pair(nGirl[0], nBoy[0]);
            ii p3 = make_pair(nGirl[1], -1);

            game g1, g2;
            g1.p1 = p1;g1.p2 = p2;g1.p3 = p3;
            gameArray.push_back(g1);

            p2 = make_pair(nGirl[1], nBoy[0]);
            p3 = make_pair(nGirl[0], -1);
            g2.p1 = p1;g2.p2 = p2;g2.p3 = p3;
            gameArray.push_back(g2);
        }
    }
}

void print()
{
    for(int u=0; u<gameArray.size(); u++)
    {
        game tmp = gameArray[u];
        cout<<"Res\n";
        cout<<tmp.p1.first<<"  "<<tmp.p1.second<<endl;
        cout<<tmp.p2.first<<"  "<<tmp.p2.second<<endl;
        cout<<tmp.p3.first<<"  "<<tmp.p3.second<<endl<<endl;
    }
}

bool impossible()
{
    int cont;
    for(int x=0; x<gameArray.size(); x++)
    {
        game tmp = gameArray[x];
        cont = 0;
        if(tmp.p1.first > tmp.p1.second)
           cont++;
        if(tmp.p2.first > tmp.p2.second)
           cont++;

        if(cont == 2)
           return true;
    }
return false;
}

int getProbAnswer()
{
    for(int i=1; i<=52; i++)
        if(!myCards.test(i))
           return i;
return -1;
}

int getProbVal(int u)
{
    game tmp = gameArray[u];
    int card = tmp.p3.first;

    for(int i=card; i<=52; i++)
        if(!myCards.test(i))
           return i;
return -1;
}

int getAnswer()
{
    set<int>:: iterator it;
    bool flag;
    int tmp,card;
    for(it=mySet.begin(); it!=mySet.end(); it++)
    {
        tmp = (*it);
        if(tmp == -1)
           return -1;

        flag = true;
        for(int a=0; a<gameArray.size(); a++)
        {
            if(isWW(a))
               continue;
            game g1 = gameArray[a];
            card = g1.p3.first;

            if(tmp < card)
            {
                flag = false;
                break;
            }
        }
        if(flag)
           return tmp;
    }
return -1;
}

int main()
{
int a,b,c,x,y, tmpAnswer, answer;
while(scanf("%d %d %d %d %d", &a, &b, &c, &x, &y))
{
    if(!a && !b  && !c  && !x  && !y)
       break;

    girl.clear(),boy.clear();gameArray.clear();
    girl.push_back(a);girl.push_back(b);girl.push_back(c);
    boy.push_back(x);boy.push_back(y);
    myCards.reset();
    mySet.clear();
    myCards.set(a, 1);myCards.set(b, 1);myCards.set(c, 1);myCards.set(x, 1);myCards.set(y, 1);
    generate();
    //print();
    if(impossible())
       printf("-1\n");
    else
    {
        for(int u=0; u<gameArray.size(); u++)
        {
            if(isWW(u))
            {
                tmpAnswer = getProbAnswer();
                mySet.insert(tmpAnswer);
            }
            else
            {
                tmpAnswer = getProbVal(u);
                mySet.insert(tmpAnswer);
            }
        }
        /*cout<<"Posibles respuestas";
        for(set<int>::iterator it=mySet.begin(); it!=mySet.end(); it++)
            cout<< *it <<" ";
        cout<<endl;*/
        answer = getAnswer();
        printf("%d\n", answer);
    }
}
return 0;
}

11683 – Laser Sculpture UVA Solution

This is an easy problem from uva judge http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2730

Ad hoc, linear scan.

How I did it

• Read the number of rows and columns. If row == 0 and columns = 0 stop the program.
• Read the final heigth and insert this values inside a vector.
• Traverse the vector. If is the first time save the diference between the row and current vector position(set current equal to vector current position), otherwise if the current vector position  is less than current variable save the diference between current and the current vector position.
• Print the total.

Hints

•  Simulate the process will finish in TLE.
• To solve thism problem a linear scan is enough.

Code

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int main()
{
int row, col, val, current, tot;

while(scanf("%d %d", &row, &col))
{
    if(!row && !col)
       break;

    vector<int> vec;
    tot = 0;

    for(int x=0; x<col; x++)
    {
        scanf("%d", &val);
        vec.push_back(val);
    }

    for(int y=0; y<vec.size(); y++)
    {
        if(y == 0)
        {
            tot = row - vec[y];
            current = vec[y];
        }
        else
        {
            if(vec[y] < current)
               tot = tot + (current - vec[y]);
        }
        current = vec[y];
    }
    printf("%d\n", tot);
}

return 0;
}