Here's a short list of some mixed geometry flavored problems from POJ.
There is a possibility that some of these may not be geometry problem at all, tried my best to sort them out though. Also, some of these problems are not solvable by only geometry knowledge. Graph, dynamic programming, and understanding of advanced data structure may also be required.
This is exactly the same problem from 2006 TopCoder Collegiate Challenge, problem DominoesFinding. I am not sure whether this problem can be solved by bipartite matching algorithm or dynamic programming, probably both will run out of time limit. But it can be solved by straight forward backtracking with a little bit pruning. The backtracking idea is pretty simple, just keep track of which tiles are used (each tile must be used exactly once), and try filling the grid in row major fashion. So there is no point discussing the solution, it is better to discuss why backtracking can be used here. I am not going to write these on my own words as it has already been written, so I will repost the analysis from TopCoder
DominoesFinding
by soul-net
Backtracking. Yes, that's it. Knowing that a problem is in fact solvable with a backtracking approach is most times a matter of intuition gained with experience. Anyway, in this and some other cases, there can be found more formal estimators that the idea is in fact THE idea.
I'll describe a possible backtracking approach, possibly the easiest to implement, but there are other possibilities. The idea is based on the fact that all squares must be used. For example, if we take the upper-left square of the board, we can see that we must connect it with one of its two neighbors. With this in mind, we can iterate over all squares and, each time we find an unused one, we know that we must match it with one of its two (or one) remaining neighboors -- or both, if we iterate in a column-row or a row-column fashion; when we find an unused square, we know that everybody in its upper-left rectangle is already used.
As we do this, we go marking each used piece and only continue trying if the new piece made by each new matching is "new". In this way, if we finally get all squares to be used, we know also that all pieces are used (because we managed to get no repeats) and then, we add 1 to the counter.
To be sure this approach works perfectly in time, you can conduct a little experiment and run the algorithm over an empty board without the "new piece" pruning. This will show you that there are less than 1.3 million ways to divide the board (1,292,697 actually), so it is perfectly feasible to try every one of them. Of course, the pruning of the "new piece" will reduce the running time dramatically in most cases.
There is also a good theoretical estimator that the approach will work in time, to convince ourselves before programming anything (many programmers think this is a must). There is a total of 56 squares in the board, our algorithm does nothing for half of them (when it finds them already used) and tries 2 or less cases for the other half (the ones it finds unused). This means the total number of leaves in the search tree will be bounded by 256/2 which is roughly 256 millions. This is pretty big, but considering it is a wide margin upper bound, it can be pretty well used as a "proof" that time limits won't bother.
Facebook hacker cup 2013: Round 1 has been finished, and the results are out as well. The problem set will be found here.
Problem A: Card Game 20 pts problem. If you take a little bit time observing the results, you can easily see what is really happening here. Any number X can be maximum in a set if all the other numbers are less or equal to X, so if we have at least K-1 such numbers, we will be able to make K sized subset where X is the maximum. If we can make M such subsets, X will be added to result M times.
Now, say, for X, there are P numbers which are less or equal to X and P >= K-1. So, we can choose K-1 numbers from P numbers in C(P, K-1) ways, everyone knows that. So, first sort all the numbers, and start from the Kth number (it will be pointless to take previous items, as they will not be maximum for any other subset). So, the Kth number will be added C(K-1, K-1) times, (K+1)th number will be added C(K, K-1) times, next one for C(K+1, K-1) times and so on while the last number will be added C(N-1, K-1) times, consider N as total number of integers.
So the solution is simple (Note, you will need modular inverse to properly count combinations, and the overall complexity is O(n lg n) ):
typedef __int64 i64;
const i64 MOD = 1000000007;
const int MAX = 10009;
i64 a[MAX];
i64 fact[MAX];
class Euclid {
public:
i64 x, y, d;
Euclid() {}
Euclid(i64 _x, i64 _y, i64 _d) : x(_x), y(_y), d(_d) {}
};
Euclid egcd(i64 a, i64 b) {
if(!b) return Euclid(1, 0, a);
Euclid r = egcd(b, a % b);
return Euclid(r.y, r.x - a / b * r.y, r.d);
}
i64 modinv(i64 a, i64 n) {
Euclid t = egcd(a, n); // here n is always prime, no check needed
i64 r = t.x % n;
return (r < 0 ? r + n : r);
}
int main() {
//freopen("card_game.txt", "r", stdin);
//freopen("card_game.out", "w", stdout);
int test, cs, n, k, i;
i64 sum, num, deno;
for(fact[0] = i = 1; i < MAX; i++) fact[i] = (fact[i-1] * i) % MOD;
scanf("%d", &test);
for(cs = 1; cs <= test; cs++) {
scanf("%d %d", &n, &k);
for(i = 0; i < n; i++) scanf("%I64d", &a[i]);
sort(a, a + n);
for(sum = 0, num = deno = fact[k-1], i = k-1; i < n;) {
sum = (sum + (((a[i] * num) % MOD) * modinv(deno, MOD)) % MOD) % MOD;
i++; num = (num * i) % MOD; deno = (deno * (i-k+1)) % MOD;
}
printf("Case #%d: %I64d\n", cs, sum);
}
return 0;
}
Problem B: Security 35 pts. I got a cross here :( Will talk about it after describing the solution. Basically two forms of the same string is given, and each one has M segments, all the segments have equal length. As we know, string 1 is actually the real string while string 2 is the permuted string (only whole segments are permuted). So we can run a maximum bipartite matching among the segments of two strings. If they do not match, the the answer is obviously possible. While comparing, if the current character of both string is equal, or any of them is a ? mark, then we also consider them to be equal.
The tricky part of this solution is, we can have multiple matches, and in those case we need to choose the match which will give us lexicographically smallest string. (I failed in this part). It can be achieved in many ways, like putting weights in matching and taking minimum weighted match, or just trying bipartite matching cutting every edge once and see if we get a better match. We then need to copy the letters from string 2 segments to string 1 segments where there is a ? in string 1. Finally, on the remaining ?, just put 'a'. Not posting the code, because it was not fully correct, but the idea is ok (confirmed by others who were able to solve it correctly).
Problem C: Dead Pixels 45 pts. Looks tricky at a first glance. Here, notable thing is, each problem has only one query, i.e. there is not dynamic update + query. So, we don't really need to do anything like segment tree here. Although, segment tree can be used to solve this one as well.
The solution is actually simple, we just sort the points by X axis, and run sliding window of width equal to picture width. We maintain a set of Y values in current window. When we skip a X value, we remove (if available) corresponding y values from the set and update number of possible positions, and then we add the y values (if available) of new X that we've just touched by our window and update accordingly. Here is my solution, pretty simple I should say.
const double EPS = 1e-9;
const int INF = 0x7f7f7f7f;
const int MAX = 1000032;
pii p[MAX];
int W, H, P, Q, N, X, Y, a, b, c, d;
map< int, int > M;
map< int, int >::iterator it;
set< int > S;
set< int > :: iterator Curr, Prev, Next;
void generate() {
p[0].ff = X, p[0].ss = Y;
for(int i = 1; i < N; i++) {
p[i].ff = (p[i - 1].ff * a + p[i - 1].ss * b + 1) % W;
p[i].ss = (p[i - 1].ff * c + p[i - 1].ss * d + 1) % H;
}
}
int lowerbound(pii *a, int st, int en, int val) {
int idx, cnt, stp;
cnt = en - st;
while(cnt > 0) {
stp = cnt >> 1; idx = st + stp;
if(a[idx].ff < val) st = ++idx, cnt -= stp+1;
else cnt = stp;
}
return st;
}
int upperbound(pii *a, int st, int en, int val) {
int idx, cnt, stp;
cnt = en - st;
while(cnt > 0) {
stp = cnt >> 1; idx = st + stp;
if(a[idx].ff <= val) st = ++idx, cnt -= stp+1;
else cnt = stp;
}
return st;
}
inline int span(int lt, int rt) {
return (rt-Q)-(lt+1)+1;
}
void insert(int cv, int &zeros) {
int lt, rt, gap;
it = M.find(cv);
if(it == M.end()) {
M.insert(pii(cv, 1));
S.insert(cv);
Next = Prev = Curr = S.find(cv);
Prev--; Next++;
lt = (Curr == S.begin()) ? -1 : *Prev;
rt = (Next == S.end()) ? H : *Next;
gap = span(lt, rt); if(gap > 0) zeros -= gap;
gap = span(lt, cv); if(gap > 0) zeros += gap;
gap = span(cv, rt); if(gap > 0) zeros += gap;
}
else it->ss++;
}
void remove(int cv, int &zeros) {
int lt, rt, gap;
it = M.find(cv); if(it == M.end()) return;
if(it->ss == 1) {
Next = Prev = Curr = S.find(cv);
Prev--; Next++;
lt = (Curr == S.begin()) ? -1 : *Prev;
rt = (Next == S.end()) ? H : *Next;
gap = span(lt, cv); if(gap > 0) zeros -= gap;
gap = span(cv, rt); if(gap > 0) zeros -= gap;
gap = span(lt, rt); if(gap > 0) zeros += gap;
S.erase(Curr);
M.erase(it);
}
else it->ss--;
}
int main() {
//READ("dead_pixels.txt");
//WRITE("dead_pixels.out");
int test, cs, i, j, zeros, tmp, total, st, en;
scanf("%d", &test);
for(cs = 1; cs <= test; cs++) {
scanf("%d %d %d %d %d %d %d %d %d %d %d", &W, &H, &P, &Q, &N, &X, &Y, &a, &b, &c, &d);
generate();
sort(p, p + N);
M.clear(); S.clear();
zeros = H - Q + 1; total = 0;
tmp = upperbound(p, 0, N, P-1);
for(i = 0; i < tmp; i++) {
insert(p[i].ss, zeros);
}
for(i = 0; i <= W - P; i++) {
total += zeros;
st = lowerbound(p, 0, N, i);
en = upperbound(p, 0, N, i);
for(j = st; j < en; j++) {
remove(p[j].ss, zeros);
}
st = lowerbound(p, 0, N, i+P);
en = upperbound(p, 0, N, i+P);
for(j = st; j < en; j++) {
insert(p[j].ss, zeros);
}
}
printf("Case #%d: %d\n", cs, total);
}
return 0;
}
However, could not make it to top 500 because of the time penalty and the mistake in problem B. Overall, problems were nice. And again, 45 pts one was easier than the 35 pts.
It was a 72 hours contest, and solving at least one problem was enough to qualify for next round. As expected for qualification round, problems were quite easy. Problem statements are here.
Problem A: Beautiful strings: This was the 20 points problem. Quite elementary level. Just count the occurrences of each letter, then assign highest value to most frequent one, next highest value to next most frequent one and so on..
#include <cstdio>
#include <cstring>
#include <cctype>
int main() {
int test, cs, i, sum;
char buff[1024];
int cnt[26];
//freopen("beautiful_strings.txt", "r", stdin);
//freopen("beautiful_strings.out", "w", stdout);
scanf("%d", &test);
gets(buff);
for(cs = 1; cs <= test; cs++) {
gets(buff);
memset(cnt, 0, sizeof cnt);
for(i = 0; buff[i]; i++) if(isalpha(buff[i])) cnt[tolower(buff[i]) - 'a']++;
sort(cnt, cnt + 26);
for(sum = 0, i = 26; i; i--) sum += cnt[i-1] * i;
printf("Case #%d: %d\n", cs, sum);
}
return 0;
}
Problem B: Balanced Smileys: This was the 35 points problem. Generally a simple dynamic programming problem, however can also be solved using regular expressions as the expected answer is only YES or NO. For dynamic programming approach, we only need two states, index and sum, here, index is the position in the given string, and sum is the parenthesis weight so far. To find weight, for a '(', we add +1 and for a ')' we add -1, all the other characters are balanced, hence we add 0 for those. When we find a ':' followed by any of the parenthesis, we can make two decisions, either skip next parenthesis, or account it.
#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
using namespace std;
const int MAX = 128;
char str[MAX];
int dp[MAX][MAX], len;
int solve(int pos, int sum) {
if(pos == len) return sum;
int &ret = dp[pos][sum];
if(ret != -1) return ret;
if(str[pos] == '(') ret = solve(pos + 1, sum + 1);
else if(str[pos] == ')') {
if(sum > 0) ret = solve(pos + 1, sum - 1);
else ret = INT_MAX;
}
else if(str[pos] == ':' && pos + 1 < len && (str[pos+1] == '(' || str[pos+1] == ')')) {
ret = min(solve(pos+2, sum), solve(pos+1, sum));
}
else ret = solve(pos + 1, sum);
return ret;
}
int main() {
int test, cs;
//freopen("balanced_smileys.txt", "r", stdin);
//freopen("balanced_smileys.out", "w", stdout);
scanf("%d", &test);
gets(str);
for(cs = 1; cs <= test; cs++) {
len = strlen(gets(str));
memset(dp, -1, sizeof dp);
if(!solve(0, 0)) printf("Case #%d: YES\n", cs);
else printf("Case #%d: NO\n", cs);
}
return 0;
}
Problem C: Find the Min: 45 points problem, and supposed to be hardest in this round. By playing around with the given series (or by applying some sense of pegionhole principle) we can find that, except for the first k+1 terms, the rest of the series is consists of repeating (k+1) terms, and these k+1 values will be always in range [0, k]. So we first find first 2k+2 terms of the series, and use modular arithmetic to find the position of nth term in this series.
#include <cstdio>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
typedef __int64 i64;
const int MAX = 1 << 18;
i64 m[MAX];
set< i64 > S;
map< i64, int > M;
int main() {
int test, cs, n, k, i;
i64 a, b, c, r;
//freopen("find_the_min.txt", "r", stdin);
//freopen("find_the_min.out", "w", stdout);
scanf("%d", &test);
for(cs = 1; cs <= test; cs++) {
S.clear(); M.clear();
scanf("%d %d %I64d %I64d %I64d %I64d", &n, &k, &a, &b, &c, &r);
b %= r, c %= r; m[0] = a;
for(i = 1; i < k; i++) m[i] = ((b * m[i-1]) % r + c) % r;
for(i = 0; i < k; i++) M[m[i]]++;
for(i = 0; i <= k; i++) S.insert(S.end(), (i64)i);
for(i = 0; i < k; i++) S.erase(m[i]);
for(i = k; i < 2*k+2; i++) {
m[i] = *S.begin();
M[m[i]]++; M[m[i-k]]--;
S.erase(S.begin());
if(!M[m[i-k]]) S.insert(m[i-k]);
}
printf("Case #%d: %I64d\n", cs, m[n % (k+1) + k+1 - 1]);
}
return 0;
}
Solved all three, now waiting for the score, not sure if I made any stupid mistake but the algorithms look fine to me.
Edit: Yes, all three passed, looking forward to what next round brings.
#define SET(x) memset(x, -1, sizeof(x))
#define CLR(x) memset(x, 0, sizeof(x))
#define MAX 100
vector < int > edges[MAX];
bool visited[MAX];
int Left[MAX], Right[MAX];
bool dfs(int u) {
if(visited[u]) return false;
visited[u] = true;
int len = edges[u].size(), i, v;
for(i=0; i<len; i++) {
v = edges[u][i];
if(Right[v]==-1) {
Right[v] = u, Left[u] = v;
return true;
}
}
for(i=0; i<len; i++) {
v = edges[u][i];
if(dfs(Right[v])) {
Right[v] = u, Left[u] = v;
return true;
}
}
return false;
}
int match() {
SET(Left);
SET(Right);
int i, ret = 0;
bool done;
do {
done = true;
CLR(visited);
for(i=0; i<MAX; i++) {
if(Left[i]==-1 && dfs(i)) {
done = false;
}
}
} while(!done);
for(i=0; i<MAX; i++) ret += (Left[i]!=-1);
return ret;
}
Thanks to Jane Alam Jan vai for this, It will be a great help... :)
/*
Author : Jan
Problem Name : Big int for contest
Algorithm :
Complexity :
*/
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;
struct Bigint {
string a;
int sign;
Bigint() {}
Bigint( string b ) { (*this) = b; }
int size() { return a.size(); }
Bigint inverseSign() { sign *= -1; return (*this); }
Bigint normalize( int newSign ) {
sign = newSign;
for( int i = a.size() - 1; i > 0 && a[i] == '0'; i-- ) a.erase(a.begin() + i);
if( a.size() == 1 && a[0] == '0' ) sign = 1;
return (*this);
}
void operator = ( string b ) {
a = b[0] == '-' ? b.substr(1) : b;
reverse( a.begin(), a.end() );
this->normalize( b[0] == '-' ? -1 : 1 );
}
bool operator < ( const Bigint &b ) const {
if( a.size() != b.a.size() ) return a.size() < b.a.size();
for( int i = a.size() - 1; i >= 0; i-- ) if( a[i] != b.a[i] ) return a[i] < b.a[i];
return false;
}
Bigint operator + ( Bigint b ) {
if( sign != b.sign ) return (*this) - b.inverseSign();
Bigint c;
for( int i = 0, carry = 0; i < (int)a.size() || i < (int)b.size() || carry; i++ ) {
carry += (i < (int)a.size() ? a[i] - 48 : 0) + (i < (int)b.a.size() ? b.a[i] - 48 : 0);
c.a += (carry % 10 + 48);
carry /= 10;
}
return c.normalize(sign);
}
Bigint operator - ( Bigint b ) {
if( sign != b.sign ) return (*this) + b.inverseSign();
if( (*this) < b ) return (b - (*this)).inverseSign();
Bigint c;
for( int i = 0, borrow = 0; i < (int)a.size(); i++ ) {
borrow = a[i] - borrow - (i < b.size() ? b.a[i] : 48);
c.a += borrow >= 0 ? borrow + 48 : borrow + 58;
borrow = borrow >= 0 ? 0 : 1;
}
return c.normalize(sign);
}
Bigint operator * ( Bigint b ) {
Bigint c("0");
for( int i = 0, k = a[i]; i < (int)a.size(); i++, k = a[i] ) {
while(k-- - 48) c = c + b;
b.a.insert(b.a.begin(), '0');
}
return c.normalize(sign * b.sign);
}
Bigint operator / ( Bigint b ) {
if( b.size() == 1 && b.a[0] == '0' ) b.a[0] /= ( b.a[0] - 48 ) ;
Bigint c("0"), d;
for( int j = 0; j < (int)a.size(); j++ ) d.a += "0";
int dSign = sign * b.sign; b.sign = 1;
for( int i = a.size() - 1; i >= 0; i-- ) {
c.a.insert( c.a.begin(), '0');
c = c + a.substr( i, 1 );
while( !( c < b ) ) c = c - b, d.a[i]++;
}
return d.normalize(dSign);
}
Bigint operator % ( Bigint b ) {
if( b.size() == 1 && b.a[0] == '0' ) b.a[0] /= ( b.a[0] - 48 ) ;
Bigint c("0");
int cSign = sign * b.sign; b.sign = 1;
for( int i = a.size() - 1; i >= 0; i-- ) {
c.a.insert( c.a.begin(), '0');
c = c + a.substr( i, 1 );
while( !( c < b ) ) c = c - b;
}
return c.normalize(cSign);
}
void print() {
if( sign == -1 ) putchar('-');
for( int i = a.size() - 1; i >= 0; i-- ) putchar(a[i]);
}
};
int main() {
Bigint a, b, c;
a = "511";
b = "10";
c = a + b;
c.print();
putchar('\n');
c = a - b;
c.print();
putchar('\n');
c = a * b;
c.print();
putchar('\n');
c = a / b;
c.print();
putchar('\n');
c = a % b;
c.print();
putchar('\n');
return 0;
}
Hope this helps my friends as well. Actually many of us are afraid of big integers, and also the above code may look hard, but this is actually what we do when performing these operations in real life... Use with caution, not a very first algorithm. Do not attempt to use *, /, % if numbers are 104 or more digits long.
/*
USER: zobayer
TASK: template
ALGO: template
*/
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <iterator>
#include <utility>
using namespace std;
template< class T > T _abs(T n) { return (n < 0 ? -n : n); }
template< class T > T _max(T a, T b) { return (!(a < b) ? a : b); }
template< class T > T _min(T a, T b) { return (a < b ? a : b); }
template< class T > T sq(T x) { return x * x; }
template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a%b) : a); }
template< class T > T lcm(T a, T b) { return (a / gcd<T>(a, b) * b); }
template< class T > bool inside(T a, T b, T c) { return a<=b && b<=c; }
template< class T > void setmax(T &a, T b) { if(a < b) a = b; }
template< class T > void setmin(T &a, T b) { if(b < a) a = b; }
#define MP(x, y) make_pair(x, y)
#define REV(s, e) reverse(s, e)
#define SET(p) memset(p, -1, sizeof(p))
#define CLR(p) memset(p, 0, sizeof(p))
#define MEM(p, v) memset(p, v, sizeof(p))
#define CPY(d, s) memcpy(d, s, sizeof(s))
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define ALL(c) c.begin(), c.end()
#define SIZE(c) (int)c.size()
#define PB(x) push_back(x)
#define ff first
#define ss second
#define i64 __int64
#define ld long double
#define pii pair< int, int >
#define psi pair< string, int >
const double EPS = 1e-9;
const double BIG = 1e19;
const int INF = 0x7f7f7f7f;
int main() {
//READ("in.txt");
//WRITE("out.txt");
return 0;
}
105 119 136 138 145 154 190 200
256 264 272 278 294 332 344 355
362 374 378 382 389 394 401 409
412 412 414 417 422 424 426 438
441 444 445 455 458 460 465 466
468 474 476 477 478 482 483 484
486 489 490 492 494 495 496 498
499 530 535 543 568 573 575 579
583 587 591 621 713 834 900 944
974 10006 10008 10013 10018 10019 10035 10055
10060 10071 10078 10079 10093 10104 10110 10161
10195 10209 10221 10242 10281 10297 10302 10323
10340 10347 10407 10432 10451 10469 10490 10499
10515 10522 10533 10573 10591 10678 10679 10683
10783 10784 10790 10812 10815 10922 10929 10931
10991 11058 11121 11152 11172 11192 11192 11219
11220 11233 11332 11343 11388 11417 11437 11455