ACM ICPC 2013 A – Attacking rooks

Problem: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=602&page=show_problem&problem=4406

Wiki Theory: http://en.wikipedia.org/wiki/Matching_(graph_theory)

Sigue leyendo

Anuncios

UVA 459 – Graph Connectivity (Depth First Search solution)

Simple solution using DFS algorithm.

#include <iostream>
#include <sstream>
#include <utility>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <functional>
#include <algorithm>
#include <numeric>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <stdio.h>
#include <string.h>
using namespace std;
typedef long long   LL;

bool G[300][300], vis[300];

void dfs(int x) {
  if(vis[x]) return;
  vis[x] = true;
  for(char i='A'; i<='Z' ;i++)
    if(G[x][i])
      dfs(i);
}

int main() {
  int casos;
  string cad;
  char N;
  cin >> casos >> cad;
  for(int i=0; i<casos ;i++) {
    memset(vis, 0, sizeof(vis));
    memset(G, 0, sizeof(G));
    int r = 0;
    if(i) printf("n");
    N = cad[0];
    while(cin>>cad && cad.size() != 1)
      G[ cad[0] ][ cad[1] ] = G[ cad[1] ][ cad[0] ] = true;
    for(char i='A'; i<=N ;i++) {
      if(vis[i]) continue;
      dfs(i);
      r++;
    }
    printf("%dn", r);
  }
}

IOI 2012 – Crayfish Scrivener

Problem description: Crayfish Scrivener

The first thing that we need is save the TEXT and know how it can be undo. This is easy we need a tree when it do undo only jump for the actions saved, for do TypeLetter add the new letter in the tree (see image).

IMG_0053

With this tree we can obtain the i-th character in the text, we always point to the last character and climb in the tree.

IMG_0054
IMG_0055

Ok it can solve task-4 but we need solve task-5 (The total number of commands and queries is between 1 and 1.000.000), our problem is ‘GetLetter’ function, it is O(P) for now. In the worst case the P can be 500.000 and it can be called 500.000 times.

IMG_0056

A good improvement is for do ‘GetLetter’ in O( sqrt(height of the tree) ). It need save the dad of the node and the ‘sqrt(height of the tree)’-th dad of each node. When the search is for a ‘P’ upper to ‘sqrt(height of the tree)’ we can jump ‘sqrt(height of the tree)’ nodes. Now ‘GetLetter’ function is O(sqrt(height of the tree) )

IMG_0057

This is my implementation

#include<iostream>
#include<cmath>
#include<vector>
using namespace std;

char T[1000001];
int dad[1000001], dadH[1000001], H[1000001];
vector<int> v;
int act, it;

void Init() {
  it = 1;
  act = 0;
  H[0] = -1;
  dad[0] = dadH[0] = 0;
  v.clear();
}

void TypeLetter(char L) {
  T[it] = L;
  H[it] = H[act]+1;
  dad[it] = act;
  if(H[it] % 1000 == 0) //sqrt(1000000) => 1000
    dadH[it] = it;
  else
    dadH[it] = dadH[act];
  v.push_back(it);
  act = it++;
}

void UndoCommands(int U) {
  act = v[v.size() - U - 1];
  v.push_back(act);
}

char GetLetter(int P) { // O(sqrt(height))
  int i = act;
  while(H[ dadH[i] ] > P) i = dadH[i];// O(sqrt(height))
  while(H[ dad[i] ] >= P) i = dad[i]; // O(sqrt(height))
  return T[i];
}

int main(){
  Init();
  TypeLetter('a');			//  a
  TypeLetter('b');			//  ab
  cout<<GetLetter(1)<<endl;	//b ab
  TypeLetter('d');			//  abd
  UndoCommands(2);			//  a
  UndoCommands(1);			//  abd
  cout<<GetLetter(2)<<endl;	//d abd
  TypeLetter('e');			//  abde
  UndoCommands(1);			//  abd
  UndoCommands(5);			//  ab
  TypeLetter('c');			//  abc
  cout<<GetLetter(2)<<endl;	//c abc
  UndoCommands(2);			//  abd
  cout<<GetLetter(2)<<endl;	//d abd
}

TopCoder SRM 498 – DIV 1 Level 2

The solution of the problem is as follows.

#define MP     make_pair
typedef long long   LL;

int xx[]={-1,-1,0,1,1,1,0,-1};
int yy[]={0,-1,-1,-1,0,1,1,1};

vector<int> res;

void bfs(vector<vector<int> >&v, int n, int m, int x, int y){
    queue<pair<int, pair<int,int> > > q;
    q.push(MP(1, MP(x, y)));
    while(!q.empty()){
        int val = q.front().first;
        x = q.front().second.first;
        y = q.front().second.second;
        q.pop();
        if(x < 0 || y < 0) continue;
        if(x >= n || y >= m) continue;
        if(v[x][y]) continue;
        v[x][y] = val;
        res[val]++;
        for(int k=0; k<8;k++)
            q.push(MP(val+1, MP(x+xx[k], y+yy[k])));
    }
}

void bfs1(vector<vector<int> >&v, int n, int m, int x, int y){
    vector<vector<pair<int,pair<int,int> > > > mark(202);
    vector<vector<bool> > vis(n, vector<bool>(m, 0));
    queue<pair<int, pair<int,int> > > q;
    q.push(MP(1, MP(x, y)));
    while(!q.empty()){
        int val = q.front().first;
        x = q.front().second.first;
        y = q.front().second.second;
        q.pop();
        if(x < 0 || y < 0) continue;
        if(x >= n || y >= m) continue;
        if(vis[x][y]) continue;
        vis[x][y] = true;
        mark[val].PB(MP(v[x][y], MP(x,y)));
        for(int k=0; k<8 ;k++)
            q.push(MP(val+1, MP(x+xx[k], y+yy[k])));
    }
    int it = 1;
    for(int i=1; i<202 ;i++){
        map<int,int> mapa;
        for(int j=0; j<mark[i].size();j++){
            int val = mark[i][j].first;
            x = mark[i][j].second.first;
            y = mark[i][j].second.second;
            if(mapa.find(val) == mapa.end()) mapa[val] = it++;
            v[x][y] = mapa[val];
        }
    }
}

LL fact(int x){
    LL r=1;
    for(LL i=2; i<=LL(x) ;i++)
        r = (r*i)%1000000009LL;
    return r;
}

class FoxStones{
    public:
    int getCount(int n, int m, vector<int> sx, vector<int> sy) {
        vector<vector<int> > v(n, vector<int>(m, 0));
        res = vector<int> (201, 0);
        bfs(v, n, m, sx[0]-1, sy[0]-1);
        for(int i=1; i            bfs1(v, n, m, sx[i]-1, sy[i]-1);
        vector<int> sol(40002, 0);
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                sol[v[i][j]]++;
        LL r = 1LL;
        for(int i=0;i<sol.size();i++)
            if(sol[i])
                r = (r*fact(sol[i]))%1000000009LL;
        return r;
    }
};

Codeforces Beta Round #56

A. Where Are My Flakes?

In this problem only you have obtain the “maximum right” parameter and the “minimum left” parameter.
Example:
n = 9
initial

right = 0 and left = n+1 = 9+1 = 10

Always the solution is (left-right-1)

0  1  2  3  4  5  6  7  8  9  10
^right                        ^left  now the solution is (10-0-1) = 9
if insert "To the left of 7"
0  1  2  3  4  5  6  7  8  9  10
^right               ^left           now the solution is (7-0-1) = 6
if insert "To the right of 2"
0  1  2  3  4  5  6  7  8  9  10
      ^right         ^left           now the solution is (7-2-1) = 4
if insert "To the right of 6"
0  1  2  3  4  5  6  7  8  9  10
             right^  ^left           now the solution is (7-6-1) but 0 => -1

This is my code.

int main(){
    int n, m, aux;
    scanf("%d %d", &n, &m);
    int a = 0, b = n+1;
    string ch, pp;
    for(int i=0; i<m ;i++){
        cin>>pp>>pp>>ch>>pp>>aux;
        if(ch[0] == 'l') b = min(b, aux);
        else a = max(a, aux);
    }
    if(a+1 >= b) printf("-1n");
    else printf("%dn", b-a-1);
}

 

B. Serial Time!

This problem was a Tridimensional “Flood Fill” problem and my code is next.

struct ST{
    int x, y, z;
    ST(int a=0, int b=0, int c=0):x(a),y(b),z(c){}
};

int main(){
    int k, n, m, x, y;
    scanf("%d %d %d", &k, &n, &m);
    vector<vector<string> > v(k, vector(n));
    for(int i=0;i<k;i++)
        for(int j=0;j<n;j++)
            cin>>v[i][j];
    scanf("%d %d", &x, &y);
    queue<ST> q;
    q.push(ST(0, x-1, y-1));
    int tot = 0;
    while(!q.empty()){
        ST aux = q.front();
        q.pop();
        if(aux.x < 0 || aux.x >= k) continue;
        if(aux.y < 0 || aux.y >= n) continue;
        if(aux.z < 0 || aux.z >= m) continue;
        if(v[aux.x][aux.y][aux.z] == '.'){
            tot++;
            v[aux.x][aux.y][aux.z] = '$';
            q.push(ST(aux.x-1, aux.y, aux.z));
            q.push(ST(aux.x, aux.y-1, aux.z));
            q.push(ST(aux.x, aux.y, aux.z-1));
            q.push(ST(aux.x+1, aux.y, aux.z));
            q.push(ST(aux.x, aux.y+1, aux.z));
            q.push(ST(aux.x, aux.y, aux.z+1));
        }
    }
    printf("%dn", tot);
}