USACO 2018 Febuary: Snow Boots (Part 1)

USACO 2018 Febuary: Snow Boots (Part 1)

Using an Union-Find Set!

Problem

It's winter on the farm, and that means snow! There are N$N$ tiles on the path from the farmhouse to the barn, conveniently numbered 1…N$1\dots N$, and tile i$i$ is covered in fi$f_i$ feet of snow.

In his farmhouse cellar, Farmer John has B$B$ pairs of boots, numbered 1…B$1\dots B$. Some pairs are more heavy-duty than others, and some pairs are more agile than others. In particular, pair i$i$ lets FJ step in snow at most si$s_i$ feet deep, and lets FJ move at most di$d_i$forward in each step.

Farmer John starts off on tile 1$1$ and must reach tile N$N$ to wake up the cows. Tile 1$1$ is sheltered by the farmhouse roof, and tile N$N$is sheltered by the barn roof, so neither of these tiles has any snow. Help Farmer John determine which pairs of snow boots will allow him to make the trek.

INPUT FORMAT (file snowboots.in):

The first line contains two space-separated integers N$N$ and B$B$ (1≤N,B≤105).The second line contains N$N$ space-separated integers; the i$i$th integer is fi$f_i$, the depth of snow on tile i$i$ (0≤fi≤109). It's guaranteed that f1=fN=0$f_1=f_N=0$.
The next B$B$ lines contain two space-separated integers each. The first integer on line i+2$i+2$ is si$s_i$, the maximum depth of snow in which pair i$i$ can step. The second integer on line i+2$i+2$ is di$d_i$, the maximum step size for pair i$i$. It's guaranteed that 0≤si≤109$0\le s_i\le {10}^9$and 1≤di≤N−1$1\le d_i\le N-1$.

OUTPUT FORMAT (file snowboots.out):

The output should consist of B$B$ lines. Line i$i$ should contain a single integer: 1$1$ if Farmer John can trek from tile 1$1$ to tile N$N$ wearing the i$i$th pair of boots, and 0$0$ otherwise.

SAMPLE INPUT:

8 7
0 3 8 5 6 9 0 0
0 5
0 6
6 2
8 1
10 1
5 3
150 7

SAMPLE OUTPUT:

0
1
1
0
1
1
1

Problem credits: Dhruv Rohatgi

How We Should Think Of It

Given an array of integers, find if there are more than Di consecutive numbers larger than Si. There are B (no greater than 100,000) values of Di and Si, and the array is no longer than 100,000 entries.

How To Solve It (Method 1)

Method 2 is in an upcoming post.

Define a "barrier" as an entry OR an consecutive sequence of entries such that every entry in that sequence is greater than Si.

This leads us to an important optimization: sort the boots (pairs of Di and Si) by decreasing Si!

This optimization allows us to only increase the length of barriers, not decrease them or remake them for each new boot. 

Hmm.. only increase but no decreasing? An union-find set implements that quite well.  We're only adding tiles of snow that satisfy:

• it is adjacent to one of the barriers, AND
• its depth (entry value) is larger than Si.

It's necessary to sort the array now too, or we will be stuck trying to pair up integers.

NOTICE THAT WHEN SORTING EITHER THE ARRAY OR THE SET OF BOOTS, WE ALSO MUST INCLUDE ITS ORIGINAL INDEX.

If not, we can't track our answers. The problem asks us to output in order of input, not in sorted order or any order we want it to be in.

The union-find set, however, doesn't need to be implemented via OOP since we are only using one. A class isn't necessary; we only have on instance of that class - what's the use of that then?

What I Did Wrong

1. Used OOP (1st try) - you don't need to since you are only initializing one single instance of the union-find set - what's the point of making a whole type :P
2. Didn't sort the array (2nd try) - why of course you need to sort it, if you don't that's an O(N^2) algorithm and we don't have time for O(N^2) when N can be at most 100,000 and time limit two seconds, clearly we need optimization
3. Didn't assign special values to unvisited values (2nd try) - we need to track if we visited it, else we would make a barrier between , say, tiles 2 and 6 - in-consecutive tiles
4. Forgot to initialize array (3rd try) - the array is static if uninitialized. An uninitialized array can make random results if you pass static to an program!
5. Confused Si and Di together (3rd try) - they're different but I named them too similar. Oh noes. Moral: Don't name things too similarly.
6. Fixed infinite recursion and the unfixed it (3rd try). Well, I didn't need to fix it after fixing #4, but the hassle was really unnecessary.

Welp...

Code

#include <algorithm>

#include <fstream>

#define MAXN 100005

using namespace std;

struct boot

{

int dur, ag, i;

constexpr bool operator<(const boot other) const

{

return dur > other.dur;

}

} boots[MAXN];

struct tile

{

int am, i;

constexpr bool operator<(const tile other) const

{

return am > other.am;

}

} path[MAXN];

/* ------- START UFS -------- */

int rt[MAXN];

int root(int x)

{

if(rt[x] < 0) return x;

else return rt[x] = root(rt[x]);

}

void merge(int x, int y)

{

int rx = root(x), ry = root(y);

if(rx == ry) return;

if(rt[rx] > rt[ry]) swap(rx, ry);

rt[rx] += rt[ry];

rt[ry] = rx;

}

/* ------- END UFS ---------- */

ifstream cin("snowboots.in");

ofstream cout("snowboots.out");

int N, B, ans[MAXN];

void read()

{

cin >> N >> B;

for(int i=0; i<N; i++)

{

cin >> path[i].am;

path[i].i = i;

}

sort(path, path + N);

for(int i=0; i<B; i++)

{

cin >> boots[i].dur >> boots[i].ag;

boots[i].i = i;

}

sort(boots, boots + B);

}

void solve()

{

for(int i=0; i<N; i++) rt[i] = MAXN;

int best = 0, next = 0;

for(int b=0; b<B; b++)

{

for(; next < N && path[next].am > boots[b].dur; next++)

{

int id = path[next].i;

rt[id] = -1;

if(id > 0 && rt[id-1] != MAXN) merge(id-1, id);

if(id < N-1 && rt[id+1] != MAXN) merge(id, id+1);

best = max(best, -rt[root(id)]);

}

ans[boots[b].i] = boots[b].ag > best;

}

for(int i=0; i<B; i++) cout << ans[i] << endl;

}

int main()

{

read();

solve();

}