Div 1, Level 1
Div 1, Level 2
Div 1, Level 3
Div 2, Level 1
Div 2, Level 2
Div 2, Level 3
Tutorials:
Division One - Level Three:
Solution
Source Code:
Division One - Level Two:
Solution
DFS.
Source Code:
//Fri Jun 3 08:40:30 CDT 2011
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <ctime>
using namespace std;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
class grafixMask {
public:
vector <int> sortedAreas(vector <string>);
void init(vector<string>);
int dfs(int, int);
bool avaiID[400][600];
};
void grafixMask::init(vector<string> rec){
memset(avaiID, false, sizeof(avaiID));
int M = rec.size();
for(int i=0; i<M; i++){
stringstream s(rec[i]);
int x1, y1, x2, y2;
s >> x1 >> y1 >> x2 >> y2;
// cout << x1 << "," << y1 << "," << x2 << "," << y2 << endl;
for(int x=x1; x<=x2; x++){
for(int y=y1; y<=y2; y++){
avaiID[x][y] = true;
}
}
}
}
int grafixMask::dfs(int x, int y){
if(avaiID[x][y])
return 0;
avaiID[x][y] = true;
int count = 1;
for(int i=0; i<4; i++){
int xx = x + dx[i];
int yy = y + dy[i];
if(xx <0 || xx >= 400 || yy < 0 || yy >= 600) continue;
count += dfs(xx, yy);
}
return count;
}
vector <int> grafixMask::sortedAreas(vector <string> rectangles) {
init(rectangles);
vector<int> res;
for(int i=0; i<400; i++){
for(int j=0; j<600; j++){
if(avaiID[i][j] == false){
int count = dfs(i, j);
res.push_back(count);
}
}
}
sort(res.begin(), res.end());
return res;
}
//Powered by [KawigiEdit] 2.0!;
Alternate Solution
Using Union-Find, Disjoint-set Data Structure.
Parent[] is like the id of the group,
While rank[] shows the amount in the group.
Source Code:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* SRM211-Div1-500.
* Using Union-Find Data Structure.
*/
/**
* @author antonio081014
* @time Sep 30, 2012, 12:16:47 PM
*/
public class grafixMask {
public int[] sortedAreas(String[] rectangles) {
UnionFind set = new UnionFind(400 * 600);
for (int i = 0; i < rectangles.length; i++) {
String[] str = rectangles[i].split(" ");
int r1 = Integer.parseInt(str[0]);
int c1 = Integer.parseInt(str[1]);
int r2 = Integer.parseInt(str[2]);
int c2 = Integer.parseInt(str[3]);
for (int p = r1; p <= r2; p++)
for (int q = c1; q <= c2; q++) {
set.avai[mapping(p, q)] = true;
}
}
for (int p = 0; p < 400; p++)
for (int q = 0; q < 600; q++) {
int m1 = mapping(p, q);
int m2 = mapping(p - 1, q);
int m3 = mapping(p, q - 1);
if (p > 0 && !set.avai[m1] && !set.avai[m2])
set.union(m1, m2);
if (q > 0 && !set.avai[m1] && !set.avai[m3])
set.union(m1, m3);
}
List<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < 400; i++)
for (int j = 0; j < 600; j++) {
int m1 = mapping(i, j);
if (!set.avai[m1] && set.rank[m1] != 0)
list.add(set.rank[m1]);
}
int[] array = new int[list.size()];
for (int i = 0; i < array.length; i++)
array[i] = list.get(i);
Arrays.sort(array);
return array;
}
public int mapping(int x, int y) {
return x * 600 + y;
}
}
class UnionFind {
int N;
int[] parent;
int[] rank;
boolean[] avai;
public UnionFind(int n) {
this.N = n;
parent = new int[n];
rank = new int[n];
avai = new boolean[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 1;
}
}
public int find(int x) {
if (parent[x] == x)
return x;
return parent[x] = find(parent[x]);
}
public void union(int x, int y) {
int r1 = find(x);
int r2 = find(y);
if (r1 == r2)
return;
if (rank[r1] >= rank[r2]) {
parent[r2] = r1;
rank[r1] += rank[r2];
rank[r2] = 0;
} else {
parent[r1] = r2;
rank[r2] += rank[r1];
rank[r1] = 0;
}
}
}
Division One - Level One:
Solution
Source Code:
//2009/08/14 02:19:55
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <sstream>
#include <algorithm>
using namespace std;
class grafixCorrupt
{
public:
int selectWord(vector <string> dictionary, string candidate)
{
int dex = -1;
int gap = 0;
for (int i=0; i<dictionary.size(); i++)
{
int ngap = 0;
for(int j=0; j<candidate.size(); j++)
{
if(candidate[j] == dictionary[i][j])
ngap++;
}
if(ngap > gap)
{
gap = ngap;
dex = i;
}
}
return dex;
}
};
Division Two - Level Three:
Solution
Source Code:
//2009/08/15 01:55:23
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <sstream>
#include <algorithm>
using namespace std;
#define MMAX 1000 // It can be set 51, since the number of commands is less than 50;
struct sel
{
int arc;
int cir;
int pol;
sel(int a, int b, int c)
{
arc = a;
cir = b;
pol = c;
}
};
class grafixGlobs
{
public:
vector <int> execute(vector <string> commands, int se)
{
vector<sel> v;
vector<int> res;
string s;
for (int i=0; i<MMAX; i++) v.push_back(sel(0,0,0));
for (int i=0; i<commands.size(); i++)
{
stringstream cmd(commands[i]);
cmd >> s;
if (s == "make")
{
int j;
for (j=0; j<MMAX; j++)
if (v[j].arc == 0 && v[j].cir == 0 && v[j].pol == 0) break;
cmd >> s;
if (s == "arc") v[j].arc ++;
if (s == "circle") v[j].cir ++;
if (s == "polygon") v[j].pol ++;
}
else if (s == "delete")
{
int j;
cmd >> j;
v[j].arc = 0;
v[j].cir = 0;
v[j].pol = 0;
}
else if (s == "merge")
{
int src, des;
cmd >> des;
cmd >> src;
v[des].arc += v[src].arc;
v[src].arc = 0;
v[des].cir += v[src].cir;
v[src].cir = 0;
v[des].pol += v[src].pol;
v[src].pol = 0;
}
else if (s == "split")
{
int src;
cmd >> src;
int t1 = v[src].arc;
v[src].arc = 0;
int t2 = v[src].cir;
v[src].cir = 0;
int t3 = v[src].pol;
v[src].pol = 0;
// Here, the new splited item can be rearranged in the original sel.
for (int j=0; j<1000; j++)
{
if (v[j].arc + v[j].cir + v[j].pol == 0)
{
if (t1 > 0)
{
v[j].arc ++;
t1 --;
}
else if (t2 > 0)
{
v[j].cir ++;
t2 --;
}
else if (t3 > 0)
{
v[j].pol ++;
t3 --;
}
}
if (t1 + t2 + t3 == 0) break;
}
}
}
if (v[se].arc + v[se].cir + v[se].pol > 0)
{
res.push_back(v[se].arc);
res.push_back(v[se].cir);
res.push_back(v[se].pol);
}
return res;
}
};
Division Two - Level Two:
Solution
Source Code:
//2009/08/14 02:19:55
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <sstream>
#include <algorithm>
using namespace std;
class grafixCorrupt
{
public:
int selectWord(vector <string> dictionary, string candidate)
{
int dex = -1;
int gap = 0;
for (int i=0; i<dictionary.size(); i++)
{
int ngap = 0;
for(int j=0; j<candidate.size(); j++)
{
if(candidate[j] == dictionary[i][j])
ngap++;
}
if(ngap > gap)
{
gap = ngap;
dex = i;
}
}
return dex;
}
};
Division Two - Level One:
Solution
Source Code:
//2009/08/14 01:14:55
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <sstream>
#include <algorithm>
using namespace std;
class grafixClick
{
public:
vector <int> checkSaveButton(vector <int> mouseRows, vector <int> mouseCols)
{
vector<int> ret;
for(int i=0; i<mouseRows.size(); i++)
{
if(mouseRows[i] >= 20 && mouseRows[i] <=39 && mouseCols[i] >= 50 && mouseCols[i] <= 99)
{
ret.push_back(i);
}
}
return ret;
}
};
import java.util.ArrayList; import java.util.Arrays; import java.util.List; /** * SRM211-Div1-500. * Using Union-Find Data Structure. */ /** * @author antonio081014 * @time Sep 30, 2012, 12:16:47 PM */ public class grafixMask { public int[] sortedAreas(String[] rectangles) { UnionFind set = new UnionFind(400 * 600); for (int i = 0; i < rectangles.length; i++) { String[] str = rectangles[i].split(" "); int r1 = Integer.parseInt(str[0]); int c1 = Integer.parseInt(str[1]); int r2 = Integer.parseInt(str[2]); int c2 = Integer.parseInt(str[3]); for (int p = r1; p <= r2; p++) for (int q = c1; q <= c2; q++) { set.avai[mapping(p, q)] = true; } } for (int p = 0; p < 400; p++) for (int q = 0; q < 600; q++) { int m1 = mapping(p, q); int m2 = mapping(p - 1, q); int m3 = mapping(p, q - 1); if (p > 0 && !set.avai[m1] && !set.avai[m2]) set.union(m1, m2); if (q > 0 && !set.avai[m1] && !set.avai[m3]) set.union(m1, m3); } List<Integer> list = new ArrayList<Integer>(); for (int i = 0; i < 400; i++) for (int j = 0; j < 600; j++) { int m1 = mapping(i, j); if (!set.avai[m1] && set.rank[m1] != 0) list.add(set.rank[m1]); } int[] array = new int[list.size()]; for (int i = 0; i < array.length; i++) array[i] = list.get(i); Arrays.sort(array); return array; } public int mapping(int x, int y) { return x * 600 + y; } } class UnionFind { int N; int[] parent; int[] rank; boolean[] avai; public UnionFind(int n) { this.N = n; parent = new int[n]; rank = new int[n]; avai = new boolean[n]; for (int i = 0; i < n; i++) { parent[i] = i; rank[i] = 1; } } public int find(int x) { if (parent[x] == x) return x; return parent[x] = find(parent[x]); } public void union(int x, int y) { int r1 = find(x); int r2 = find(y); if (r1 == r2) return; if (rank[r1] >= rank[r2]) { parent[r2] = r1; rank[r1] += rank[r2]; rank[r2] = 0; } else { parent[r1] = r2; rank[r2] += rank[r1]; rank[r1] = 0; } } }
