USACO 2018 February: Snow Boots (Part 2)

-

USACO 2018 February: Snow Boots (Part 2)

Using a Monotone Deque!

Problem

It's winter on the farm, and that means snow! There are N tiles on the path from the farmhouse to the barn, conveniently numbered 1…N, and tile i is covered in fi feet of snow.
In his farmhouse cellar, Farmer John has B pairs of boots, numbered 1…B. Some pairs are more heavy-duty than others, and some pairs are more agile than others. In particular, pair i lets FJ step in snow at most si feet deep, and lets FJ move at most diforward in each step.
Farmer John starts off on tile 1 and must reach tile N to wake up the cows. Tile 1 is sheltered by the farmhouse roof, and tile Nis 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 and B (The second line contains N space-separated integers; the ith integer is fi, the depth of snow on tile i (). It's guaranteed that f1=fN=0.
The next B lines contain two space-separated integers each. The first integer on line i+2 is si, the maximum depth of snow in which pair i can step. The second integer on line i+2 is di, the maximum step size for pair i. It's guaranteed that 0≤si≤109and 1≤di≤N−1.

OUTPUT FORMAT (file snowboots.out):

The output should consist of B lines. Line i should contain a single integer: 1 if Farmer John can trek from tile 1 to tile N wearing the ith pair of boots, and 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 2)

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

Let's try to force this problem into something searching for the first value smaller than a value.

Define L as an one-dimensional array. L[i] means, for the i-th element in the array, L[i] is the index of the first element that is smaller than the i-th element. Here, L[i] is on the left of i, and the first element means that its value will be as large as possible. 
Define R as an one-dimensional array that's the exact opposite. R[i] means, for the i-th element in the array, R[i] is the index of the last element that is smaller than the i-th element. Here, R[i] is on the right of i, and the last element means that its value will be as large as possible. 

This converts the problem into one in which the monotone stack can be used. It asks for the first such element that is smaller than a value (min monotone stack), and it asks for the last such value that is smaller than a value (min monotone stack but flipped array). 

The length of the barrier would be L[i] - R[i] - 1, which we directly compare to Di to see if the "boot" can "step over".

We cannot use a queue because this problem requires us to add elements to the monotone "queue" from the front and remove elements from the monotone "queue" also from the front - LIFO, not FIFO.





Teacher's Code

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

const int maxN = 100000 + 10;
const int maxB = 100000 + 10;

struct a_t
{
 int f, id;
}a[maxN];

struct b_t
{
 int s, d, id;
}b[maxB];

int n, B, f[maxN], L[maxN], R[maxN];
int tail, queue[maxN];

bool ans[maxB];

void init()
{
 scanf("%d%d", &n, &B);
 for (int i = 0; i < n; ++i)
 {
  scanf("%d", &a[i].f);
  a[i].id = i;
 }
 for (int i = 0; i < B; ++i)
 {
  scanf("%d%d", &b[i].s, &b[i].d);
  b[i].id = i;
 }
}

bool cmpF(a_t a, a_t b)
{
 return a.f > b.f;
}

bool cmpS(b_t a, b_t b)
{
 return a.s > b.s;
}

void solve()
{
 tail = 0;
 queue[tail] = -1;
 for (int i = 0; i < n; ++i)
 {
  while (tail > 0 && a[i].f <= a[queue[tail]].f)
   --tail;
  L[i] = queue[tail];
  queue[++tail] = i;
 }
 tail = 0;
 queue[tail] = n;
 for (int i = n-1; i >= 0; --i)
 {
  while (tail > 0 && a[i].f <= a[queue[tail]].f)
   --tail;
  R[i] = queue[tail];
  queue[++tail] = i;
 }

 sort(a, a+n, cmpF);
 sort(b, b+B, cmpS);
 int next = 0, longest = 0;
 for (int i = 0; i < B; ++i)
 {
  int s = b[i].s;
  for (; next < n && a[next].f > s; ++next)
  {
   int id = a[next].id;
   longest = max(longest, R[id]-L[id]-1);
  }
  ans[b[i].id] = b[i].d > longest;
 }

 for (int i = 0; i < B; ++i)
  printf("%d\n", ans[i]);
}

int main()
{
 for (int t = 1; t <= 10; ++t)
 {
  char name[256];
  sprintf(name, "%d.in", t);
  freopen(name, "r", stdin);
  sprintf(name, "%d.ans", t);
  freopen(name, "w", stdout);

  init();
  solve();
 }

 return 0;
}





My Code







#include <stack>



#include <fstream>



#include <algorithm>



#define MAXN 100005



using namespace std;







ifstream cin("snowboots.in");



ofstream cout("snowboots.out");







struct boot



{



 int s, d, i;



 constexpr bool operator<(const boot other) const



 {



  return s > other.s;



 }



} boots[MAXN];







struct tile



{



 int s, i;



 constexpr bool operator<(const tile other) const



 {



  return s > other.s;



 }



} path[MAXN];







stack<int> moq;



int N, B, ans[MAXN], R[MAXN], L[MAXN];







void read()



{



 cin >> N >> B;



 for(int i=0; i<N; i++) { cin >> path[i].s; path[i].i = i; }



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



 {



  cin >> boots[i].s >> boots[i].d;



  boots[i].i = i;



 }



}







void solve()



{



 moq.push(-1);



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



 {



  while (moq.size() > 1 && path[i].s <= path[moq.top()].s) moq.pop();



  L[i] = moq.top();



  moq.push(i);



 }



 moq = { };



 moq.push(N);



 for(int i=N-1; i>=0; i--)



 {



  while (moq.size() > 1 && path[i].s <= path[moq.top()].s) moq.pop();



  R[i] = moq.top();



  moq.push(i);



 }



 sort(boots, boots + B);



 sort(path, path + N);



 int A = 0, barrier = 0;



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



 {



  for (; A<N && path[A].s>boots[i].s; A++)



   barrier = max(barrier, R[path[A].i]-L[path[A].i]-1);



  ans[boots[i].i] = boots[i].d > barrier;



 }



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



}







int main()



{



 read();



 solve();



}

















































Comments











Post a Comment































Popular posts from this blog









USACO Training "subset": Subset Sums






-















 USACO Training "subset": Subset Sums   Problem Statement    Subset Sums JRM  For many sets of consecutive integers from 1 through N (1 <= N <= 39), one can partition the set into two sets whose sums are identical.  For example, if N=3, one can partition the set {1, 2, 3} in one way so that the sums of both subsets are identical:   {3} and {1,2}   This counts as a single partitioning (i.e., reversing the order counts as the same partitioning and thus does not increase the count of partitions).  If N=7, there are four ways to partition the set {1, 2, 3, ... 7} so that each partition has the same sum:   {1,6,7} and {2,3,4,5}  {2,5,7} and {1,3,4,6}  {3,4,7} and {1,2,5,6}  {1,2,4,7} and {3,5,6}   Given N, your program should print the number of ways a set containing the integers from 1 through N can be partitioned into two sets whose sums are identical. Print 0 if there are no such ways.  Your program must calculate the answer, not look it up from a table.   PROGRAM NAME: s...








Read more










USACO 2018 Open: Talent Show






-














Image







 USACO 2018 Open Talent Show   In Short  Given N objects with value Vi and weight Wi, a collection of elements is said to have total value-to-weight ratio as (the sum of their value) divided by (the sum of their weight). Find the best possible value-to-weight ratio of these X objects, given the restraint that the collection must have total weight at least W.  Return that ratio multiplied by 1000 and floored.   Analysis   It would be very difficult to calculate this optimal ratio - we'd have to either    try all possible collections - O(2^n), where n is at most 250, about 10 to the power of 75 calculations, OR  use a greedy heuristic - get the objects with the best ratio until it satisfies the weight limit.    Neither of those are too to our liking, so how about searching for it?    The search space is linear and not infinite - it asks for the ratio to the closest thousandths.   The search space is sorted as well - if ratio X is achievable, then ratio Y < X is also achievable, if...








Read more










UVA 787 and Big Number Multiplication






-















 UVA 787 and Big Number Multiplication   Problem        Background: Big Numbers in this problem  Big numbers are effectively storing sequence of digit chunks and directly manipulating them as if they were a large number. The most intuitive way to do this is to make an array where every element is a digit, but this is not effectively using the memory. Hence, it is logical to store numbers "millions at a time", i.e.   324876498726832746   [2]  | [1] | [0]   like that.   Necessities to Implement  Notice that although this problem may LOOK like DP, it's really solvable by O(N^2) enumeration. Also notice that in this enumeration we will only be multiplying a large number with a normal number. Pseudocode for algorithm:   CREATE LargeNumber NAME best SET -INFINITY  FOR EACH i BETWEEN 0 and LENGTH OF list DO:      CREATE LargeNumber NAME product SET 1      FOR EACH j BETWEEN i AND LENGTH OF list DO          SET product TO product TIMES list[j]  ...








Read more