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.
Here is a short list of network flow and bpm problems that I managed to solve from SPOJ and HDU. This is not much and there are other sources of these kinds of problems, but I think these are some good starting points. Also I did not classify them on the types of flow or bpm, that would be up to the reader.
| ANGELS | BABY | DIVREL | FASTFLOW | MATCHING |
| MSE06I | MTOTALF | MUDDY | PCPC12H | PROFIT |
| PT07X | QUEST4 | SCITIES | STEAD | TAXI |
| 1532 | 1533 | 1853 | 2448 | 2686 |
| 2732 | 2833 | 3081 | 3277 | 3315 |
| 3376 | 3395 | 3416 | 3419 | 3435 |
| 3468 | 3472 | 3488 | 3491 | 3572 |
| 3667 | 3987 | 3998 | 4183 | 4309 |
Note: UVa has a lot of flow and bpm problems, please visit uHunt for guidelines.
Note: It is very possible that there are many other problems from these online judges which can be solved by flow or bpm algorithms. And, some problems here could be mistakenly added as flow or bpm category due to copy paste errors. Please feel free to leave a note on the comment section, add more links if you like to. Happy coding \m/
Problem link: SPOJ Problem Set (classical): 10810. Its a Murder!
Given a sequence of integers (at most 105 integers ranging from 0 to 106. You have to go from left to right, and for each position, you have to add the sum of all the numbers before current position which are strictly smaller than the number in current position.
Well, if the numbers where sorted, then we could do it more easily, i.e. keep an array for cumulative sum, and then calculate the answer in O(n) time. However, this is not the case. So, what can we do? According the problem, you have to maintain the cumulative sum anyway. So for each number in the sequence, if we keep adding them one by one, we can break down the problem in two parts. Let's think of a data structure which keeps cumulative sums, and we can add numbers anywhere and still maintain the sum. Segment tree / or binary indexed tree could come handy in this situation, where, the later one is more straight forward and less memory hungry. Now the steps are:
1 ⇒ Query: When a number is to be added, what is the sum of numbers smaller than current one? Note, as we are adding one by one in the order they appear, so the question whether there are any numbers which came after current number is eliminated. It is guaranteed that, when you are adding the ith number, all the numbers already present in the data-structure came before position i.
2 ⇒ Update: Once you have taken the partial sum for current number, it is now time to add the number in proper place, and update the cumulative sum structure. Here, clearly, appropriate position means, the position where the number would be placed when sorted. Now, we can do two things here. (a), we can sort the number and give each number an unique id to indicate its position in the sorted array. And (b), as the numbers are up to 106, we can use the numbers as their indices or positions in the sorted array. It is faster and the memory overhead is not that of a big issue here.
Now, here are two more things to be taken care about, (a), there can be duplicate numbers, and (b), 0 can be present in the input sequence, which can cause some trouble if you use BIT. However, (a) is handled naturally, because the problem wanted you to add only strictly smaller numbers, so it doesn't matter if you add same numbers in the same positions. There will be no query points in-between the equal numbers. And for (b), there is really no need to worry about 0, cause it contributes nothing at all, just ignore 0.
So, the overall algorithm looks like the following:
for each number ai:
if ai > 0:
ans += BIT_Query(ai - 1)
BIT_Update(ai, ai)
Here: BIT_Query(pos) returns the sum up to position pos and BIT_Update(pos, val) adds val in pos in the BIT structure. Solutions involving the segment tree is also similar. Just keep the tree of total sums, whenever you are trying to add a number, read the partial sum, and then update the structure.
Happy coding..
I’ve always imagined what BIT (I will omit the dots, but don't confuse it with binary bits) can do and can’t. I have seen numerous times, experienced solvers say “Oh it’s easily solvable using BIT” leaving me wondering, “BIT on this problem! How on earth!” Still I haven’t found quite a good answer for this question. Looks like BIT can do as much as you can imagine it to do (and obviously design it to do so).
However, I am not going to explain the structure of BIT or how it works etc. As there are lots of well documented articles available on the net. I can’t help putting one specific link here, which is a TopCoder algorithm tutorial for BIT. So, if you are not familiar with BIT yet, first go ahead, and read that post.
In this post, we will discuss some of the most common application of BIT for solving data structure related problems, more specifically, where range sum updates and queries are involved.
Some methods used in this post:
Update(x, v): Adds V at the position x in BIT.
Query(x): Returns the cumulative value on position x in BIT.
Read the above tutorial to know how these methods are implemented.
We will be using 1-based indexing throughout the post.
This is the most common form of BIT, and just about 99% of online tutorials you will find on the net will describe this application. So here we don't have much to say. If your updates are like “Add v in the x position of the array”, and queries are like “What is the sum of elements in index range [a, b] in the array?”, then all you do for update is call Update(x, v) and answer queries by Query(b) - Query(a-1). Simple cumulative sum formula, nothing really astonishing. This problem is can be solved using BIT: SPOJ - MSE06H.
Although not something you see every now and then, but it's readily doable. Now you are required to update v over the range [a, b] and the query is performed on a single index x. So now you call update twice, first add v at index a, then remove v for indices larger than b, which is: Update(a, v); Update(b+1, -v); And for query, you simply call Query(x). Now to see why this works, the following reasoning can be made:
Lets consider, initially you have everything 0. So Query(x) will return 0, no matter what index you call it with. Suppose you have called Update(a, v) and Update(b+1, -v). Now what will happen if you call Query(x)? Three cases can arise:
1. if x < a, the query is not affected by the updates. So you get correct result.
2. if x > b, x will be affected by the update(a, v) since x ≥ a, and update(b+1, -v) since x ≥ b+1, therefore, v-v=0 so everything cancels out. Again, you get the correct result.
3. a ≤ x ≤ b. x is only affected by update(a, v), but not update(b+1, -v), therefore, Query(x)'s value is increased by v, and it will return the correct result.
As we can see, in this fashion, we can increment or decrement for a range [a, b], and get a single index effect for some index x. This problem is an example: SPOJ - UPDATEIT
I didn't even know it exists until I read some post in TopCoder forums (the post was made by: AnilKishore).
I will just re-state his explanation as it was quite clear itself. All we want here is to support range updates, and do range queries. As from the previous type, if we try to store range updates, the BIT structure effectively captures updates for single positions, instead of range/cumulative sums. However, we can do some tweaking to work around this problem.
Let's just consider only one update: Add v to [a, b] while the rest elements of the array is 0.
Now, consider sum(0, x) for all possible x, again three situation can arise:
1. 0 ≤ x < a : which results in 0
2. a ≤ x ≤ b : we get v * (x - (a-1))
3. b < x < n : we get v * (b - (a-1))
This suggests that, if we can find v*x for any index x, then we can get the sum(0, x) by subtracting T from it, where:
1. 0 ≤ x < : Sum should be 0, thus, T = 0
2. a ≤ x ≤ : Sum should be v*x-v*(a-1), thus, T = v*(a-1)
3. b < x < n : Sum should be 0, thus, T = -v*b + v*(a-1)
As, we can see, knowing T solves our problem, we can use another BIT to store this additive amount from which we can get:
0 for x < a, v*(a-1) for x in [a..b], -v*b+v(a-1) for x > b.
Now we have two BITs.
To add v in range [a, b]: Update(a, v), Update(b+1, -v) in the first BIT and Update(a, v*(a-1)) and Update(b+1, -v*b) on the second BIT.
To get sum in range [0, x]: you simply do Query_BIT1(x)*x - Query_BIT2(x);
Now you know how to find range sum for [a, b]. Just find sum(b) - sum(a-1) using the formula stated above.
Pretty impressive this one! SPOJ - HORRIBLE can be solved in this approach. And thanks to Iqram Mahmud for this nice problem.
How to write Update and Query methods for 2D BIT is well described in the TopCoder tutorial I've mentioned above. The only thing to notice here is how the queries and updates work. 2D BIT is basically a BIT where each element is another BIT. Adding v on (x, y) means it's effect will be found throughout the rectangle [(x, y), (W, H)], and query for (x, y) gives you the result of the rectangle [(0, 0), (x, y)], assuming the total rectangle is [(0, 0), (W, H)]. SO when you query and update on this BIT, you have to be careful about how many times you are subtracting a rectangle and adding it. Simple set union formula works here. So if you want to get the result of a specific rectangle [(x1, y1), (x2, y2)], the following steps are necessary to do so:
V = Query(x2, y2)
V -= Query(x2, y1-1)
V -= Query(x1-1, y2)
V += Query(x1-1, y1-1)
This problem is an example: SPOJ - MATSUM
This page is likely to be updated if I find and manage to solve new types of BIT problems. Please let me know if there are mistakes. This post is inspired by some random posts lying around in TopCoder forums, I just wanted to put them in one place for future reference.
Fun problem! First it wants you to run a sieve from 2 to N, and then do the similar operations starting from N to 2, except, this time, you have to mark the factors of N and then find the next largest N1 not yet marked, then mark factors of N1 and so on... Finally, you have to tell how many numbers will be unmarked by both algorithms up to N.
First observation is, you only need to consider those numbers which are primes, so, we can run a sieve up to 107, which will allow us to test whether a number is prime or not in O(1) time.
Now, for each N, we can pre-calculate the result. Just note that, say if you know ans[n-1] and want to determine ans[n] from it, this inequality will hold |ans[n] - ans[n-1]| <= 1. Because the current N will be added as an unmarked, or there may be a number which you added in the past, will be removed by one of the factors of this N. Or, if N is not a prime, then it will be already removed by the first algorithm i.e. sieve.
If N is a prime number, then no N1 has removed this N already, so in this case the ans[n] = ans[n-1] + 1.
If N is an even number, and if N/2 was a prime, you have added that with your result, but this should be removed at this stage. So in such a case, ans[n] = ans[n-1].
Why don't you need to consider other factors like N/3, N/5 ... ? 2 is the only even prime factor and it can produce even numbers by multiplying other primes with it. For other primes, p = 3, 5 and so on, if N/p is prime, then N cannot be even. So the basic idea is as follows:
for( i = 2; i <= N; i++ ) {
ans[i] = ans[i - 1];
if( i is even and i/2 is prime ) ans[i] = ans[i] - 1;
if( i is prime ) ans[i] = ans[i] + 1;
}
I had absolutely no clue at the first glance. Really nice problem.
A perfect rhyme is not a crime,
it is something that exceeds time,
a bit of science, a piece of art,
soft as a pillow, sharp as a dart.
I really love this little rhyme.
Basically the problem is, you are given a dictionary of words, and some query words. For each query word q, you have to find a dictionary word u such that, u != q and the common suffix of q and u are of maximum length possible. In case there is a tie, the problem requires the lexicographically smallest such word.
This problem can be solved using STL maps and storing the suffixes along with their sorted id, but there is a more elegant solution using Trie data structure, i.e. prefix tree. As we are interested in maximizing common suffix length, we can store the strings in the Trie in reversed form, so now the suffixes will become prefixes in this tree. For each dictionary word, we also need to store its index number, when sorted, as a termination marker for that word, so that, we can find the id of an word easily during the query. On each node, we also need to keep two additional information, the ids of lexicographically smallest and second smallest strings passing through that node, which we call min1 and min2. Initially both should contain an infinite value.
Now for each query word, we also search the word in reversed form. If it is not found in the tree, i.e. a path may exist, but the end marker is not present, then the task is simple, we just return the lexicographically smallest id, which is min1, from the current node, i.e. the node which we reached while trying to match the query string.
But extra cares should be taken when the query string is found on the tree, because, then we have to look for another candidate, for which, we have kept min2, i.e. second lexicographically smallest index. If we can deduce that, going to node x from current node cur, if it evidently means we will end up finding the exact same word, then we can't follow that path, instead, we decide which index to return from current node cur, if its min1 index refers to the word itself, then we return min2, otherwise we return min1. And if we have no other choice but end up at the exact matching point, then we are also sure that there is at least another string which follows the same path, but does not end at our current node, i.e. at least two different words. Then depending on our query word, we select min1 or min2 from our current node.
So, if you know how to code a Trie, it is not really a hard one, but indeed a tricky one.
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.
This was also one of the problems I was asked on my recent interview with Google. Problem is a simple one for segment tree based algorithm. The solution basically requires us to maintain a Range Maximum Query (RMQ) algorithm, and I implemented this using segment tree.
Given, there are N items and a window of size K, we have to find the maximum item in each K sized window. First, we insert the first K items in the RMQ, so the segment tree root now knows the maximum item at this stage. Now if you observe you will see, for the (k+1)th item, 1st item will be removed from the tree and (k+1)th item will be inserted. This can be done by inserting (k+1)th item at the position of 1st item. Because for (k+1)th item, 1st item is in the oldest position. And clearly, for each of the next items, we can just insert it in the current oldest position on the K sized window. so (k+1) will be inserted at index 1, (k+2) at 2, (k+3) at 3 ... (2k) at k, (2k+1) at 1, (2k+2) at 2 and so on. So all we need is to keep inserting the items in the RMQ in a circular fashion and each time taking the updated range maximum value.
So, basically the structure of the code is:
for(i = 0; i < k; i++) insert(root, 0, k-1, item[i]);
output Tree[root];
for(; i < n; i++) {
insert(root, 0, k-1, item[i % k]);
output Tree[root];
}
// considering item indexes to be 0 based in code
// insert is the function that inserts an item on a specific index in the RMQ tree
So, once you write down the RMQ function insert, you are pretty much done with it. Happy coding!
Euler Totient / Phi Function φ(n) counts the number of positive integers less than or equal to n which are relatively prime to n, i.e. do not have any common divisor with n except 1.
Formula for Euler Phi function:
If you look closely to the formula, you will see that, we multiply n with (p-1)/p for each prime p that divides n. Now recall what do we do when we run Sieve of Eratosthenes for marking primes / non-primes. On the outer loop of the sieve, we determine if a number is prime, then in inner loop, instead of setting flags, if we can keep multiplying the number with (p-1)/p where p is the current prime number from outer loop, at the end of the iterations, we can actually generate φ(n) for each n over the range we are asked for. Here is a source code example that does exactly the same thing. Just take a look and try to understand what are the loops doing here, and how we are performing calculation and storing results.
#include <cstdio>
const int MAX = 1000001;
int phi[MAX];
void euler_phi() {
phi[1] = 1;
for(int i=2; i<MAX; i++) {
if(!phi[i]) {
phi[i] = i-1;
for(int j=(i<<1); j<MAX; j+=i) {
if(!phi[j]) phi[j] = j;
phi[j] = phi[j]/i*(i-1);
}
}
}
}
int main() {
euler_phi();
for(int t=1; t<MAX; t++) printf("%d\n", phi[t]);
return 0;
}
A bit of explanation on what we are doing here: Initially the phi[] array is set to 0 (as it is declared global). We know that, phi[1] = 1 and phi[n] = n-1 when n is a prime number. So, similar to sieve algorithm, first we check if current number is prime in the outer loop, if phi[i] = 0, it means i is prime. So, we update it with i-1 accordingly. Now, for all the multiples of i greater than i, which starts from 2*i, calling it j in inner loop, we need to multiply phi[j] by (i-1) / i. Here, we first check if phi[j] is 0, i.e. visiting it for the first time, in this case we set it with j, as I said earlier that, for φ(n) we will multiply n with (p-1)/p where p are the primes that divide n. Also, one thing to note here: a * b / c and a / c * b are not always same for integer calculation unless you can assure that c divides a. In this case it does, why? cause this is basically a prime factoring algorithm, and c = i here. As we are traversing i's multiples, it is guaranteed that a=phi[j] can be divided by c=i and instead of a * b / c format, we will always use a / c * b in these types of situations, because it will help preventing overflow many times.
Now, think about the optimizations we could apply here, and try applying them, like discarding even numbers, starting inner loop from squares, increment inner loop twice the prime number each time, won't work here. Because, we need to go through every numbers in inner loop, as we are trying to find Totient function for every n in the range 1 to MAX. Test the code on smaller range, and try to check if it is doing this correctly, play around with it.
σx(n) is defined as the sum of xth powers of the distinct positive divisors of n. The function can be expressed as:
Here, r = ω(n), which is the number of distinct positive prime factors of n. pi for i = 1 to r, are the prime factors and ai is the maximum power of piby which n is divisible.
Clearly, this function can be used for various problems, for example, when x = 0, it simply means the number of distinct positive divisors of n, if x = 1, it is the sum of distinct positive divisors of n, for x = 2, its the sum of squares of positive divisors of n and so on.
For programming contest practice, there are a few problems that requires sum of divisors, or number of divisors, which can be calculated by simply calculating the prime factors with their count, and then evaluating the function shown above with appropriate value on x. Also, the form of function definition can be changed when you set a value for x. After putting x = 0, we get this:
So this is easy, you just need to find frequency of each prime, and then multiply each (ai + 1) for all primes, you get the number of divisors of n.
For sum of divisor, the idea is similar, here x = 1. The following code shows how to find sum of distinct positive divisors of n:
#include <cstdio>
#include <cmath>
using namespace std;
#define sq(x) ((x)*(x))
#define i64 unsigned long long
#define MAX 784
#define LMT 28
unsigned flag[MAX/64];
unsigned primes[5761460], total;
#define chkC(n) (flag[n>>6]&(1<<((n>>1)&31)))
#define setC(n) (flag[n>>6]|=(1<<((n>>1)&31)))
/*
Regular sieve of eratosthenes, bitwise implementation
*/
void sieve()
{
unsigned i, j, k;
flag[0]|=0;
for(i=3;i<LMT;i+=2)
if(!chkC(i))
for(j=i*i,k=i<<1;j<MAX;j+=k)
setC(j);
primes[(j=0)++] = 2;
for(i=3;i<MAX;i+=2)
if(!chkC(i))
primes[j++] = i;
total = j;
}
/*
finds n^p in log(p) time
*/
i64 power(unsigned n, unsigned p)
{
i64 x=1, y=n;
while(p > 0)
{
if(p&1) x *= y;
y *= y;
p >>= 1;
}
return x;
}
/*
calculates the sigma(1) function, we don't need to find prime frequencies.
*/
inline void update(i64 &sigma1, i64 n, unsigned p)
{
if(p==1) sigma1 *= (n+1);
else sigma1 *= ((power(n,p+1)-1)/(n-1));
}
/*
Factorization function, we do not need to store the primes here,
instead, whenever a prime is found, you update corresponding prime
and frequency with sigma 1
*/
void factor(i64 n, i64 &sigma1)
{
unsigned i, v;
i64 t;
for(i=0, t=primes[i]; i<total && t*t <= n; t = primes[++i])
{
if(n % t == 0)
{
v = 0;
while(n % t == 0)
{
v++;
n /= t;
}
update(sigma1, primes[i], v);
}
}
if(n>1) update(sigma1, n, 1);
}
/*
Our beloved main function
*/
int main()
{
int t, x;
i64 n, sigma1;
sieve();
scanf("%d", &t);
for(x=1; x<=t; x++)
{
scanf("%llu", &n);
factor(n, sigma1);
printf("%llu\n",sigma1);
}
return 0;
}
We just need the values of σ, so here we will not store the prime factors. Some similar problem would be to find the number of odd divisors of n, or testing if a number is square free, i.e. no perfect square divides n, going to leave these as an exercise for readers.
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.
This is just another simple Euler path problem. Given a undirected unweighted graph, which contains multiple edges, you have to find the lexicographically smallest Euler path.
I don't know what the problem setter was thinking, but he made a big mistake. Problem statement says "Your program must output the path of intersections that, if interpreted as a base 500 number, would have the smallest magnitude." where nodes are numbered from 1 to 500. Clearly, 500 is not a base 500 digit. I made several wrong submissions for trying to do some foolish tricks to get this done, then I just did a lexicographic ordering, and it passed. Pretty funny!
Problem statement ensures that there is no input for which Euler path does not exist. This makes the solution easier, just check if all the degrees are even, if so, start from the smallest numbered node, otherwise start from smaller numbered odd degree node.
algorithm for finding euler path:
graph[u][v] contains number of edges between u and v
find( node u ):
for each adjacent v of u in lexicographical order:
while( graph[u][v] > 0 ):
graph[u][v]--;
graph[v][u]--;
find(v);
stack.push(u);
Now the stack contains the euler path in reverse order, so just keep popping!
Nice problem! The first observation is, if you want to reach the city, say, point 0, you have to ensure that every single point between the current position and city must also be reachable. Now, the task is to minimize the number of stoppages for fuel, which is at most 10000. So, we sort the fuel stations, and start from current position. For every fuel station, if we want to reach it, we must have fuel f more than or equal to the distance d. Also, using the larger capacities will always reduce the number of stations we must stop.
So, for each stoppage, starting from farthest, if we can reach this stoppage with existing fuel, we push it in a priority queue (max heap in this case) for future use. If we cannot reach a particular stoppage, then we keep popping the queue and keep adding the amounts with currently available until we are able to reach current stoppage, and then pushing this value. This strategy ensures an optimal solution to reach a particular stoppage, as the priority queue will hold maximum capacities seen so far along the path, but not used yet.
If at any time, the queue gets empty and the amount of fuel is not sufficient, then the particular stoppage cannot be reached, hence, it will be impossible to reach the city.
Happy Coding
/*
Author: Zobayer Hasan
*/
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
public class Apriori extends Thread {
public static boolean debugger = false;
private final Database db;
private final List< Integer > itemset;
private final List< List< Integer > > frequent;
private double minsup;
public Apriori(String thrName, Database db, double minsup) {
super(thrName);
this.db = db;
itemset = db.getItemset();
frequent = new ArrayList< List< Integer > >();
this.minsup = minsup;
}
@Override
public void run() {
double startTime = System.currentTimeMillis();
int k = 1, n = db.dbSize();
List< List< Integer > > Ck = new ArrayList< List< Integer > >();
List< List< Integer > > Lk = new ArrayList< List< Integer > >();
HashMap< List< Integer>, Integer > seenK = new HashMap< List< Integer >, Integer >();
for(Integer item : itemset) {
List< Integer > temp = new ArrayList< Integer >();
temp.add(item);
Lk.add(temp);
}
while(k <= n && !Lk.isEmpty()) {
if(debugger) {
System.out.println("Step " + k);
System.out.println("Lk: " + Lk);
}
seenK.clear();
Ck.clear();
for(List< Integer > kth : Lk) {
int count = db.scanDatabase(kth);
if((double)count < Math.ceil(minsup * (double)n / 100.0)) continue;
Ck.add(kth);
}
if(debugger) {
System.out.println("Ck: " + Ck);
}
if(Ck.isEmpty()) break;
for(List< Integer > freq : Ck) {
frequent.add(freq);
seenK.put(freq, k);
}
int[] prefixlen = new int[Ck.size()];
prefixlen[0] = 0;
for(int i = 1; i < Ck.size(); i++) {
prefixlen[i] = prefixLen(Ck.get(i-1), Ck.get(i));
}
List< List< Integer > > temp = new ArrayList< List< Integer > >();
for(int i = 0; i < Ck.size(); i++) {
for(int j = i + 1; j < Ck.size(); j++) {
if(prefixlen[j] == k-1) {
if(debugger) {
System.out.println("Joining: " + i + ":" + Ck.get(i) + " + " + j + ":" + Ck.get(j) + " Prefix Length " + prefixlen[j]);
}
temp.add(prefixJoin(Ck.get(i), Ck.get(j)));
}
else break;
}
}
if(debugger) {
System.out.println("Temporary: " + temp);
}
Lk.clear();
for(List< Integer > list : temp) {
boolean candid = true;
if(k > 1) {
for(int i = 0; i < list.size(); i++) {
List< Integer > prev = new ArrayList< Integer >();
for(int j = 0; j < list.size(); j++) {
if(i != j) prev.add(list.get(j));
}
if(!seenK.containsKey(prev)) {
candid = false;
break;
}
}
}
if(candid) {
Lk.add(list);
}
}
if(debugger) {
System.out.println("Pruned: " + Lk);
}
k++;
}
double endTime = System.currentTimeMillis();
System.out.println("Apriori completed in " + (endTime - startTime)/1000.0 + " seconds");
}
public void printPatterns() {
System.out.println("Frequent Itemsets");
for(List< Integer > pattern : frequent) {
System.out.println(pattern);
}
System.out.println("Total " + frequent.size() + " itemsets");
}
private int prefixLen(List< Integer > left, List< Integer > right) {
int len = 0;
for(len = 0; len < left.size() && len < right.size(); len++) {
if(left.get(len).compareTo(right.get(len)) != 0) return len;
}
return len;
}
private List< Integer > prefixJoin(List< Integer > left, List< Integer > right) {
List< Integer > ret = new ArrayList< Integer >();
for(Integer i : left) {
ret.add(i);
}
ret.add(right.get(right.size() - 1));
return ret;
}
}
This class is threaded, so it is possible to take advantages of multicore processors.
/*
Author: Zobayer Hasan
*/
public class FIMtest {
public static void main(String[] args) {
Database db = null;
try {
db = new Database("mushroom.dat");
} catch(Exception e) {
e.printStackTrace();
}
System.out.println("\nStarting Apriori");
Apriori test1 = new Apriori("test1", db, 40.0);
Apriori.debugger = true;
test1.start();
try {
test1.join();
test1.printPatterns();
} catch(Exception e) {
e.printStackTrace();
}
}
}
/*
Author: Zobayer Hasan
*/
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
class Entry {
public Integer first;
public Integer second;
Entry() {}
Entry(Integer first, Integer second) {
this.first = first;
this.second = second;
}
}
public class Database {
public static boolean debugger = false;
private final List< List< Integer > > transactions;
private final List< Integer > items;
public Database(String dataFileName) throws Exception {
if(debugger) {
System.out.println("Processing " + dataFileName);
}
transactions = new ArrayList< List< Integer > >();
items = new ArrayList< Integer >();
FileInputStream fin = new FileInputStream(dataFileName);
InputStreamReader istream = new InputStreamReader(fin);
BufferedReader stdin = new BufferedReader(istream);
String line;
double startTime = System.currentTimeMillis();
while((line = stdin.readLine()) != null) {
List< Integer > transaction = new ArrayList< Integer >();
String[] temp = line.split("\\s+");
for(String num : temp) {
transaction.add(Integer.parseInt(num));
}
if(transaction.isEmpty()) continue;
Collections.sort(transaction);
transactions.add(transaction);
}
fin.close();
istream.close();
stdin.close();
int n = transactions.size();
int[] header = new int[n];
PriorityQueue< Entry > pQ = new PriorityQueue< Entry >(n, new Comparator< Entry >() {
public int compare(Entry item1, Entry item2) {
if(item1.first.equals(item2.first)) {
return item1.second.compareTo(item2.second);
} else {
return item1.first.compareTo(item2.first);
}
}
});
for(int i = 0; i < n; i++) {
header[i] = 0;
pQ.add(new Entry(transactions.get(i).get(header[i]), i));
}
while(!pQ.isEmpty()) {
Entry peek = pQ.remove();
int val = peek.first;
int idx = peek.second;
if(items.isEmpty() || items.get(items.size()-1) < val) {
items.add(val);
}
while(header[idx] < transactions.get(idx).size() && transactions.get(idx).get(header[idx]) <= val) {
header[idx]++;
}
if(header[idx] < transactions.get(idx).size()) {
pQ.add(new Entry(transactions.get(idx).get(header[idx]), idx));
}
}
double endTime = System.currentTimeMillis();
System.out.println("Database created in " + (endTime - startTime)/1000.0 + " seconds");
}
public int scanDatabase(List< Integer > transaction) {
int count = 0;
for(List< Integer > row : transactions) {
boolean found = true;
for(Integer item : transaction) {
int idx, stp, st = 0, en = row.size(), cnt = en - st;
while(cnt > 0) {
stp = cnt >> 1; idx = st + stp;
if(row.get(idx).compareTo(item) < 0) {
st = ++idx;
cnt -= stp+1;
}
else {
cnt = stp;
}
}
if(st == row.size() || row.get(st).compareTo(item) != 0) {
found = false;
break;
}
}
if(found) count++;
}
return count;
}
public List< Integer > getItemset() {
return items;
}
public int dbSize() {
return transactions.size();
}
public List< Integer > getRow(int row) {
try {
return transactions.get(row);
} catch(Exception e) {
throw e;
}
}
}
Clearly it provides some interface to access the database where the constructor must be called with a file name for example 'mushroom.dat'. The sorting on line 56 is not necessary if you know the transactions in the file will be sorted in ascending order. All the data files in this repository are already sorted, so sorting can be disabled.