Falling Rocks with Cached Paths
National Olympiad — National round (2019 season)
Submission name: rocks.cpp
Problem summary
Drop rocks from specified top columns. They fall into empty cells, stop above walls, and when supported by a rock roll left if both side and lower-left cells are empty; otherwise try right, then stop.
Input
R C, R board rows using . and X, N and N 1-based drop columns.
Output
The final board with settled rocks marked O.
Constraints
1 ≤ R ≤ 30000; 1 ≤ C ≤ 30; 1 ≤ N ≤ 100000. Every chosen top cell is empty.
Worked example
Input and output for the worked example discussed below.
Input
5 4 .... .... X... .... .... 4 1 1 1 1
Output
.... O... X... .... OOO.
Solution analysis
- A naive simulation restarts at the top for every rock and may repeat a 30000-cell fall 100000 times. Cache a descending path separately for each source column. The board changes only from empty to occupied.
- Before dropping, pop occupied suffix cells from that source’s cached path, restarting at its top cell only if the cache becomes empty. Resume the same deterministic rules from the last valid cached cell, appending new positions. A roll may be combined with the following downward step because the diagonal cell is required to be empty.
- An X directly below stops the rock; only an O permits rolling. Test left before right, and require both horizontal and diagonal cells empty. In the sample the first rock stops above X, while later rocks spread across the bottom to OOO.
- Each cached path has strictly increasing row indices. Its popped cells are charged to newly occupied board cells, while pushes equal pops plus the final path length. This bounds total repeated work.
Why it works
A valid cached prefix follows exactly the fresh rock’s deterministic descent; removing newly blocked suffix cells and resuming the original rules gives the same resting position.
Watch out. Do not roll around an X wall. Keep caches separate by source column, remove occupied suffixes, and respect left priority.
Commented C++17 solution
An independently written complete program with standard headers.
// A valid cached prefix follows exactly the fresh rock’s deterministic descent; removing newly blocked suffix
// cells and resuming the original rules gives the same resting position.
#include<iostream>
#include<string>
#include<utility>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int rows,columns;
cin>>rows>>columns;
vector<string>board(rows);
for(string&row:board){
cin>>row;
}
vector<vector<pair<int,int>>>path(columns);
int drops;
cin>>drops;
while(drops--){
int source;
cin>>source;
source--;
auto&cached=path[source];
while(!cached.empty()&&board[cached.back().first][cached.back().second]!='.'){
cached.pop_back();
}
if(cached.empty()){
cached.push_back({0,source});
}
while(true){
auto[row,column]=cached.back();
if(row+1==rows||board[row+1][column]=='X'){
board[row][column]='O';
break;
}
if(board[row+1][column]=='.'){
cached.push_back({row+1,column});
}
else if(column>0&&board[row][column-1]=='.'&&board[row+1][column-1]=='.'){
cached.push_back({row+1,column-1});
}
else if(column+1<columns&&board[row][column+1]=='.'&&
board[row+1][column+1]=='.'){
cached.push_back({row+1,column+1});
}
else{
board[row][column]='O';
break;
}
}
}
for(const string&row:board){
cout<<row<<'\n';
}
}