p250 is easy since plain xor cipher gives you key. And each cipher maps to one plain so you can try them all.
p500 reads daunting but is actually simple. each row is a 50-ary number. Since each col is independent, just accumulate counts and assign 0 to the max cnt, 1 to second max cnt, etc. Watch for integer overflow when do multiplication.
p1000 is a tricky problem, even petr did a resubmission. First of all, the problem asks for an lexico first eulerian tour. We all know eulerian tour and there is a linear time algorithm with simple implementation using recursion. So what is the difficult part? In the tour, an edge cannot have the same label as its prev edge. The problem statement goes through all the trouble to disguise this by saying no two consecutive edges are same labelled except the begin edge and last edge of the tour. So how to do that? A greedy algorithm would use the minimum valid edge as next edge, but this fails. See this example
edge(0,1)='a'
edge(0,4)='f'
edge(1,2)='c'
edge(1,3)='c'
edge(1,4)='b'
edge(2,4)='d'
edge(3,4)='e'
A valid tour is 0-1-3-4-2-1-4-0, with edges a-c-e-b-c-d-f
Now greedy will choose edge(1,4)=b as next edge instead of edge(1,3)=c, then it is doomed since we will have to enter 1 and leave 1 using two edges both labeled 'c'. And it is not a valid tour.
So the algorithm? Pretty much brute force. You try all possible next edge, see if use this edge will allow the rest to have a valid tour, and pick the minimum label edge as your choice. It is obvious that the solution is valid and lexico minimum. Now how do you check the rest edges?
For each node, it needs to have an even number of edges, and the max cnt of them cannot be more than 1/2 of total cnt. It is clear that if this holds for all vertices and the subgraph is connected, then the subgraph has a valid eulerian tour. In fact, you are checking an eulerian path from vertex first to vertex last, each vertex other than first/last should have maxcnt=othercnt. For first and last, each get an extra deg for othercnt because for first=last, it has to be first=last=0, then you can have an extra 2 othercnt since it is valid to have maxcnt=othercnt+2 for vertex[0]. For first!= last, it is maxcnt=othercnt before, and if you use one of maxcnt, then you are good, if you use one othercnt, then you will have maxcnt=othercnt+1 and it is allowed.
Since we only have 40 nodes, and at most 40*40/2=800 edges. For each vertex and each of its neighbor, we remove that edge and do a check. the check is linear time. So the total is 40*40*40*40=800*800=640000, which is a small number and will run in time limit.
OK, code here, also at here
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
#define sz(a) int(a.size())
bool valid(int first, int last, const vector<string> &graph);
vector<int> euler(char prev, int v, vector<string> graph)
{
//cout << "euler " << prev << ' ' << v << endl;
//for(int i=0; i<sz(graph); ++i)
//{
//for(int j=0; j<sz(graph[0]);++j) cout << graph[i][j];
//cout << endl;
//}
int n = sz(graph);
int deg[50]={0};
for(int i=0; i<n; ++i) for(int j=0; j<n; ++j) deg[i]+=(graph[i][j]!='.');
vector<int> ans(1,v);
if (deg[v]==0) return ans; // basecase, when v has deg=0
// find a neighbor and remove edge, decr deg
int next=sz(graph[v]);
for(int k=0; k<sz(graph[v]); ++k)
{
char ch = graph[v][k];
if (ch=='.'||ch==prev) continue;
//use edge(v,k) and check the rest
graph[v][k]=graph[k][v]='.';
// need to use min vertex so the first valid k is next
if (valid(k,0,graph)) { next=min(next,k); }
graph[v][k]=graph[k][v]=ch;
}
if (next>=sz(graph[v])) return vector<int>();
char ch = graph[v][next];
graph[v][next]=graph[next][v]='.';
vector<int> sub=euler(ch,next,graph);
if (sub.empty()) return vector<int>();
for(int i=0; i<sz(sub); ++i) ans.push_back(sub[i]);
return ans;
}
void dfs(int v, int visit[], const vector<string> &graph)
{
if (visit[v]) return;
visit[v]=1;
int n = sz(graph);
for(int i=0; i<n; ++i) if (!visit[i] && graph[v][i]!='.')
dfs(i,visit,graph);
}
// all non-isolated vertices must be connected
bool connected(const vector<string> &graph)
{
int n = sz(graph);
int visit[50]={0};
dfs(0,visit,graph);
int deg[50]={0};
for(int i=0; i<n; ++i) for(int j=0; j<n; ++j) if (graph[i][j]!='.') deg[i]++;
for(int i=0; i<n; ++i) if (deg[i] && !visit[i]) return false;
return true;
}
// every node has to be balanced, #maxcnt <= #total/2
bool valid(int first, int last, const vector<string> &graph)
{
int n = sz(graph);
if (!connected(graph)) return false;
for(int i=0; i<n; ++i)
{
int total=0;
int cnt[100]={0};
for(int j=0; j<n; ++j)
{
char ch = graph[i][j];
if (ch=='.') continue;
int k;
if ('A'<=ch && ch<='Z') k=ch-'A';
else k=ch-'a'+26;
cnt[k]++; total++;
}
sort(cnt,cnt+sizeof(cnt)/sizeof(int), greater<int>());
int extra=0;
// first=last only possible when both are 0, and maxcnt=other+2 is fine
// when first!=last, both can have maxcnt=other+1 because we have
// maxcnt=other before use one edge
if (i==first) { ++total; ++extra; }
if (i==last) { ++total; ++extra; }
if (total%2!=0) return false;
if (cnt[0]>total-cnt[0]+extra) return false;
}
return true;
}
class LexSmallestTour
{
public:
vector<int> determineTour(vector<string> roads, vector<int> queries)
{
vector<int> empty;
if (!valid(0,0,roads)) return empty;
vector<int> tour=euler(' ', 0, roads);
if (tour.empty()) return empty;
vector<int> ans;
for(int i=0; i<sz(queries); ++i)
{ if (i) cout << ' '; cout << tour[queries[i]];
ans.push_back(tour[queries[i]]);
}
cout << endl;
return ans;
}
};
// SRM 516 div1 p250
//
// brute force
//
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef pair<int,int> PI;
#define INF (1<<29)
#define fort(i,a) for(typeof a.begin() i=a.begin(); i!=a.end(); ++i)
#define ALL(x) x.begin(), x.end()
#define PB push_back
#define MP make_pair
#define sz(a) int(a.size())
class NetworkXOneTimePad
{
public:
int crack(vector <string> plain, vector <string> cipher)
{
int ans=0;
string c = cipher[0];
for(int i=0; i<sz(plain); ++i)
{
string key;
for(int j=0; j<sz(c); ++j)
{
char ch;
if (plain[i][j]==c[j]) ch='0';
else ch='1';
key+=ch;
}
bool good=true;
for(int k=1; k<sz(cipher); ++k)
{
bool found=false; // found a plain for cipher[k]
for(int kk=0; kk<sz(plain); ++kk)
{
bool match=true; // plain[kk] match cipher[k]
for(int j=0; j<sz(cipher[k]); ++j)
{
char ch;
if (plain[kk][j]==key[j]) ch='0';
else ch='1';
if (ch!=cipher[k][j]) { match=false; break; }
}
if (match) { found=true; break; }
}
if (!found) { good=false; break; }
}
if (good) ++ans;
}
return ans;
}
// BEGIN CUT HERE
public:
void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); }
private:
template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }
void test_case_0() { string Arr0[] = {"110", "001"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arr1[] = {"101", "010"}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 2; verify_case(0, Arg2, crack(Arg0, Arg1)); }
void test_case_1() { string Arr0[] = {"00", "01", "10", "11"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arr1[] = {"00", "01", "10", "11"}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 4; verify_case(1, Arg2, crack(Arg0, Arg1)); }
void test_case_2() { string Arr0[] = {"01", "10"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arr1[] = {"00"}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 2; verify_case(2, Arg2, crack(Arg0, Arg1)); }
void test_case_3() { string Arr0[] = {"000", "111", "010", "101", "110", "001"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arr1[] = {"011", "100"}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 6; verify_case(3, Arg2, crack(Arg0, Arg1)); }
// END CUT HERE
};
// BEGIN CUT HERE
int main()
{
NetworkXOneTimePad __test;
__test.run_test(-1);
}
// END CUT HERE
[lyan@localhost topcoder]$ cat RowsOrdering.cpp
// SRM 516 div1 p500
//
// The problem reads daunting but turned out to be very easy
//
// basically you are treating each row as a number in 50-ary
// since each col is independent, you can work with them without
// worry about other cols
//
// since you are to minimize the sum, you can assign 0 to the
// max cnt char in the col, 1 to 2nd max cnt char, ...
//
// then you sum the weighted cnt in each col
//
// now you work with a vector of sums and you assign larger
// weight to smaller sum
//
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef pair<int,int> PI;
#define INF (1<<29)
#define fort(i,a) for(typeof a.begin() i=a.begin(); i!=a.end(); ++i)
#define ALL(x) x.begin(), x.end()
#define PB push_back
#define MP make_pair
#define sz(a) int(a.size())
class RowsOrdering
{
public:
int order(vector <string> rows)
{
const int MOD = 1000000000+7;
int M = sz(rows[0]);
vector<LL> cols(M);
for(int c=0; c<M; ++c)
{
int row[55]={0};
for(int r=0; r<sz(rows); ++r)
{
int val=0;
char ch = rows[r][c];
if ('a'<=ch && ch<='z') val = ch-'a';
else if ('A'<=ch && ch<='X') val = ch-'A'+26;
row[val]++;
}
sort(row,row+sizeof(row)/sizeof(int),greater<int>());
LL sum=0LL;
for(int i=0; i<51; ++i)
{
sum += i*row[i];
}
cols[c]=sum;
}
sort(cols.begin(), cols.end(), greater<LL>());
LL factor=1LL, ans=0LL;
for(int i=0; i<M; ++i)
{
ans = (ans+cols[i]*factor%MOD) % MOD;
factor = factor*50LL % MOD;
}
ans = (ans+sz(rows))%MOD;
return ans;
}
// BEGIN CUT HERE
public:
void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); if ((Case == -1) || (Case == 5)) test_case_5(); }
private:
template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }
void test_case_0() { string Arr0[] = {"bb", "cb", "ca"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 54; verify_case(0, Arg1, order(Arg0)); }
void test_case_1() { string Arr0[] = {"abcd", "ABCD"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 127553; verify_case(1, Arg1, order(Arg0)); }
void test_case_2() { string Arr0[] = {"Example", "Problem"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 943877448; verify_case(2, Arg1, order(Arg0)); }
void test_case_3() { string Arr0[] = {"a", "b", "c", "d", "e", "f", "g"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 28; verify_case(3, Arg1, order(Arg0)); }
void test_case_4() { string Arr0[] = {"a", "a"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 2; verify_case(4, Arg1, order(Arg0)); }
void test_case_5() { string Arr0[] = {"dolphinigle", "ivanmetelsk", "lympandaaaa"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 356186235; verify_case(5, Arg1, order(Arg0)); }
// END CUT HERE
};
// BEGIN CUT HERE
int main()
{
RowsOrdering __test;
__test.run_test(-1);
}
// END CUT HERE
No comments:
Post a Comment