Check out "simplify the problem" problem solving strategy on my quora blog

Post by Mahmoud Radwan:

Strategy: Simplify the problem

Check out "simplify the problem" problem solving strategy on my quora blog

Post by Mahmoud Radwan:

Strategy: Simplify the problem

Check out Focus on the solution problem solving strategy on my quora blog

Post by Mahmoud Radwan:

Strategy: Focus on the solution

This is an interesting 2-Sat problem, get familiar with the problem here

Check out last seven slides here for more understanding how to solve the problem.

Now how do we approach a problem using 2-Sat, its usually easier to think of it as implications, think what happens when you Don’t satisfy something, what should be done to still make things work.

Lets apply this to the problem we have here

So we have a simple route request from (i0,j0) to (i1,j1) where i1 > i0, j0 > j1

what would happen if we had the street i0 going west only ? then the route would need to go (i0,j0) -> (i1,j0) -> (i1,j1) which requires that j0 is south and i1 is east.

so now we know that

i0 west implies j0 south and i0 west implies i1 east

which is the same as saying

(i0 east or j0 south) AND (i0 east or i1 east)

we should repeat this for i1, j0 and j1.

if we supply all the constraints we’ll have a 2-Sat, here’s the code.

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Manhattan_10319 { static class SlowTwoSatSolver { byte[][] graph; public SlowTwoSatSolver(int nvars) { graph = new byte[nvars * 2][nvars * 2]; } public void addImplication(int x, int v_x, int y, int v_y) { graph[x * 2 + v_x][y * 2 + v_y] = 1; } public boolean solve() { int n = graph.length; for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) graph[i][j] |= graph[i][k] & graph[k][j]; for (int i = 0; i < n; i++) if ((graph[i][i ^ 1] & graph[i ^ 1][i]) == 1) return false; return true; } } public static void main(String[] args) throws Exception { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer strtok; strtok = new StringTokenizer(in.readLine()); int tc = Integer.parseInt(strtok.nextToken()); while (tc-- > 0) { strtok = new StringTokenizer(in.readLine()); int n = Integer.parseInt(strtok.nextToken()); int m = Integer.parseInt(strtok.nextToken()); int r = Integer.parseInt(strtok.nextToken()); SlowTwoSatSolver solver = new SlowTwoSatSolver(n + m); for (int i = 0; i < r; i++) { strtok = new StringTokenizer(in.readLine()); int i0 = Integer.parseInt(strtok.nextToken()) - 1; int j0 = Integer.parseInt(strtok.nextToken()) - 1; int i1 = Integer.parseInt(strtok.nextToken()) - 1; int j1 = Integer.parseInt(strtok.nextToken()) - 1; int di = i1 - i0; int dj = j1 - j0; if (di == 0 && dj == 0) { continue; } else if (di == 0) { int dir = dj > 0 ? 1 : 0; solver.addImplication(i0, dir ^ 1, i0, dir); } else if (dj == 0) { int dir = di > 0 ? 1 : 0; solver.addImplication(n + j0, dir ^ 1, n + j0, dir); } else { int dir0 = dj > 0 ? 1 : 0; int dir1 = di > 0 ? 1 : 0; solver.addImplication(i0, dir0 ^ 1, i1, dir0); solver.addImplication(i0, dir0 ^ 1, n + j0, dir1); solver.addImplication(i1, dir0 ^ 1, i0, dir0); solver.addImplication(i1, dir0 ^ 1, n + j1, dir1); solver.addImplication(n + j0, dir1 ^ 1, n + j1, dir1); solver.addImplication(n + j0, dir1 ^ 1, i0, dir0); solver.addImplication(n + j1, dir1 ^ 1, n + j0, dir1); solver.addImplication(n + j1, dir1 ^ 1, i1, dir0); } } if (solver.solve()) System.out.println("Yes"); else System.out.println("No"); } } }

Let the number of ways to choose R objects from N objects be C(N,R) where the order does not matter, which has the famous closed form N!/(R! * (N-R)!).

Let the number of ways to choose R times from N objects with repetition be S(N,R) where the order of choosing does not matter.

for example if we were to choose from A,B and C four times A,B,C,C is the same as A,C,B,C so we should not count this twice in S(N,R)

S(N,R) turns also to be the number of solutions of

a1 + a2 + … + aN = R, where ai ≥ 0, and R is some non negative integer, simply imagine ai’s as objects the number of time an object is chosen is it’s value, and we choose from those objects R times so the sum would be equals R.

The question is how do we calculate S(N,R) using C(N,R) and this is the only reason for writing this post.

Lets try to solve an instance of the problem

lets assume N = 3 , R = 4

here are some possible solutions

a1 = 0, a2 = 2, a3 = 2

a1 = 1, a2 = 2, a3 = 1

a1 = 2, a2 = 2, a3 = 0

basically we are assigning a value to each variable such that their sum is 4 (youdon’tsay!)

but lets try to interpret this using binary numbers somehow, we can somehow write a solution using a binary number of length N + R – 1 bits as the following

a zero means move on to next variable

a one means increment current variable by 1

we can write a1 = 0, a2 = 2, a3 = 2 as 011011

at the beginning we have a1 = 0, we encounter a 0 so we move on to a2 increment it twice, then move on to a3 increment it twice.

similarly we can write a1 = 1, a2 = 2, a3 = 1 as 101101

since in any solution we need to move on to next variable N-1 times (N variables), and we have to increment all variables R times then from any binary number of N-1 zeroes, R ones we can construct a valid solution.

And if we have a solution we can construct a binary number.

Then there’s a one to one correspondence between the set of solutions and the set of binary numbers with N+R-1 bits where N-1 of them are zeroes and R of them are ones.

Counting those can be easily done using normal combinations so S(N,R) = C(N+R-1,R).

Update: it turns out that this post has a similar content to whats written here at topcoder tutorial :(, so you might want to check it out.

In NIM Game you have n piles each contains ai (0≤i<n) stones, two players alternate turns in each turn a player may remove any positive number of stones from a single pile, the player who cannot make a move loses the game.

Here’s an example n = 1,a0 = 30

First player take 29 stones.

Second player take 1 stone.

First player loses (a0 = 0).

However First player could’ve won if he took 30 stones in the first turn.

Another example n = 2,a0 =3,a1 = 3.

First player take 3 stones from a0.

Second player take 3 stones from a1.

Try playing the game here Stone game reading the next part

If **both** players play **optimally** who will win the game?

We can easily find who will win the game by calculating the bitwise XOR of all pile sizes(NIM sum) if this number is zero then second player wins otherwise first player wins.

So why does this work ? You can spend sometime trying to get some intuition by applying this rule on games with N ≤ 2, however when n grows a mathematical proof works best.

Here’s **a sketch of a proof** (Note: ^ is the bitwise xor)

lets assume we have piles a0,a1,…,an we prove that if a0^a1^…^an = 0 then we are in a losing position, otherwise we are in a winning position.

we prove the following

- A-base case if all piles contain 0 stones then we are in a losing state (0 ^ 0 ^ .. ^ 0 = 0)
- B-being in a losing state means that any move we make will put the opponent in a winning state

proof:

first being in a losing state means

a0 ^ a1 ^ a2 … ^ an = 0

lets assume without the loss of generality that we picked pile a0 to make our move and removed k (0<k≤an) stones from it

we need to prove that

(a0 – k) ^ a1 ^ a2 … ^ an != 0

starting from

a0 ^ a1 ^ a2 … ^ an = 0 xor both sides by a0 ^ (a0 – k)

we get

(a0 – k) ^ a1 ^ a2 … ^ an = a0 ^ (a0 – k)

but a0 ^ (a0 – k) will always be non zero for positive values of k.

- C-being in a wining state means that there exists a move that will put the opponent in a losing state

proof:

assume that

a0 ^ a1 ^ a2 … ^ an = x

lets write x in binary, and look at the highest bit set there exists at least one pile that has that bit set assume without the loss of generality that this pile a0

we need to prove that there’s some POSITIVE k such that

(a0-k) ^ a1 ^ a2 … ^ an = 0

but (a0-k) ^ a1 ^ a2 … ^ an = x ^ a0 ^ (a0 – k)

thus we need to solve x ^ a0 ^ (a0 – k) = 0

xor both sides by a0 – k

we get

x ^ a0 = a0 – k which means

k = a0 – (x ^ a0) and with the assumption that a0 has the highest bit in x means that x ^ a0 is strictly less than a0 thus k is positive and we’re done.

using A,B,C we can use induction to obtain the complete proof.

**Useful links**

**Sample Problems**

Box Game (Not direct NIM but try to get an observation and prove it in a similar way)

The problem here is asking us to calculate the minimum,maximum time it would take all ants to fall off from the stick, lets focus on the maximum time first

That maximum time would be the maximum time that would take the last ant to fall from the stick.

So how do we make this time maximum if we had one ant at position x, simply the time would be max(x,L-x) where L is the length of the stick.

What makes the problem harder is the collision, so lets focus on what happens when 2 ants collide

Assume we have 2 ants A,B in those directions —A—><—B— and they collided at point z, what happens that

before collision B should walk distance z, A should walk distance L-z

after collision A should walk distance z, B should walk distance L-z

so they just exchanged roles here, i.e before collision we were going to wait max(z,L-z) for both ants to fall (if they didn't collide and just shook hands 🙂 )

after collision we're also going to wait max(z,L-z), so collision doesn't change the result.

Knowing this the problem becomes direct, here's solution.

#include <stdio.h> int max(int a,int b){return a>b?a:b;} int min(int a,int b){return a<b?a:b;} int main() { int tc,i,n,c,l,h; scanf("%d",&tc); while(tc--){ scanf("%d %d",&c,&n); l = h = 0; while(n--){ scanf("%d",&i); l = max(l,min(c-i,i)); h = max(h,max(c-i,i)); } printf("%d %d\n",l,h); } return 0; }

At first I thought this problem can be solved using trie, which would be an easy way however the simple trie would use a lot of memory 4000 * 1000 * 26 integers or so, Then I had to use another way which would be sorting, using any comparison based sorting algorithm as quick sort or merge sort would also cause Time limit exceeded so instead I used my not-so-efficient radix sort which runs in O(num_words*max_length), then using the sorted words you can easily calculate the result, see the solution for more information.

#include <stdio.h> #include <string.h> #include <stack> using namespace std; typedef long long ll; char words[4005][1005]; int len[4005]; int loc[4005]; int temp[4005]; int word_count; int freq[128]; int charAt(int i, int j) { return (j < len[loc[i]]) ? words[loc[i]][j] : 0; } void count_sort(int j) { memset(freq, 0, sizeof freq); for (int i = 0; i < word_count; i++) freq[charAt(i, j)]++; for (int i = 1; i < 128; i++) freq[i] += freq[i - 1]; for (int i = word_count - 1; i >= 0; i--) temp[--freq[charAt(i, j)]] = loc[i]; memcpy(loc, temp, word_count * 4); } void radix_sort() { int max_len = 0; for (int i = 0; i < word_count; i++) { loc[i] = i; if (len[i] > max_len) max_len = len[i]; } for (int i = max_len - 1; i >= 0; i--) count_sort(i); } int main(int argc, char *argv[]) { int cc = 1; while (scanf("%d", &word_count) && word_count) { getchar(); for (int i = 0; i < word_count; i++) { gets(words[i]); len[i] = strlen(words[i]); } radix_sort(); stack<int> s; s.push(0); s.push(word_count - 1); s.push(0); ll res = 0; memset(freq, 0, sizeof(freq)); while (s.size()) { int j = s.top(); s.pop(); int r = s.top(); s.pop(); int l = s.top(); s.pop(); int all = r - l + 1; for (int i = l; i <= r; i++) freq[charAt(i, j)]++; res += freq[0] * (freq[0] - 1); res += freq[0] * (all - freq[0]); freq[0] = 0; for (int i = l; i <= r; i++) { char c = charAt(i, j); if (!c) continue; if ((i > l && c == charAt(i - 1, j)) || !c) continue; res += freq[c] * (freq[c] - 1); res += freq[c] * (all - freq[c] - i + l); s.push(i); s.push(i + freq[c] - 1); s.push(j + 1); freq[c] = 0; } } printf("Case %d: %lld\n", cc++, res); } return 0; }