Hi,
I have question about the solution to a CP question which a CodeChef problem, I couldn’t find a better place to post it—if you know of a more suitable forum please let me know.
Mock CCC 2024 Junior 5, Mathland—found on dmoj.ca problem id mccc6j5
For this problem, I implemented a BFS solution which explores the states for the shortest path.
#include <iostream>
#include <queue>
#include <unordered_set>
#include <tuple>
#include <utility>
using namespace std;
int n, k;
char m[800][800];
vector<pair<int, int>> dirs = {
{-1, 0},
{0, 1},
{1, 0},
{0, -1}
};
struct HashTuple {
size_t operator()(const tuple<pair<int, int>, int, int>& tuple) const {
size_t hash = 0;
hash_combine(hash, get<0>(tuple).first);
hash_combine(hash, get<0>(tuple).second);
hash_combine(hash, get<1>(tuple));
hash_combine(hash, get<2>(tuple));
return hash;
}
private:
template <class T>
void hash_combine(size_t& seed, const T& value) const {
hash<T> hasher;
seed ^= hasher(value) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
};
unordered_set<tuple<pair<int, int>, int, int>, HashTuple> visited;
queue<pair<int, int>> toVisit;
char indexRotation(pair<int, int> rc, int rotation){
switch (rotation) {
case 0:
return m[rc.first][rc.second];
case 1:
return m[n-rc.second-1][rc.first];
case 2:
return m[n-rc.first-1][n-rc.second-1];
case 3:
return m[rc.second][n-rc.first-1];
}
}
int main(void){
cin >> n >> k;
for (int i=0; i<n; i++)
for (int j=0; j<n; j++){
cin >> m[i][j];
if (m[i][j] == 'E') {
toVisit.push(make_pair(i, j));
visited.insert(make_tuple(make_pair(i, j), 0, 0));
}
}
int time = 0;
while (toVisit.size() > 0) {
int rotation = (time / k) % 4;
int nextRotation = rotation + ((time+1)%k == 0);
int sz = toVisit.size();
for (int i=0; i<sz; i++) {
pair<int, int> coord = toVisit.front(); toVisit.pop();
char coordC = indexRotation(coord, rotation);
if (coordC == 'X') {
cout << time;
return 0;
}
else if (coordC != 'W') {
for (pair<int, int> &dir: dirs) {
pair<int, int> next = make_pair(coord.first+dir.first, coord.second+dir.second);
tuple<pair<int, int>, int, int> nextState = make_tuple(next, (time+1)%k, nextRotation);
if ((next.first >= 0 && next.first < n) &&
(next.second >= 0 && next.second < n) &&
!visited.contains(nextState)) {
toVisit.push(next);
visited.insert(nextState);
}
}
}
}
time++;
}
cout << -1;
return 0;
}
This just about TLE’s for the second subtask and I can’t wrap my head around an elegant way to further optimise my solution.
The question makes repeated reference to the need to use calculus and maths in the question (from the problem description to the title itself) and I’m struggling to see where the concepts from calculus or mathematics could be applied besides perhaps an A* heuristic based approach?
If anyone has any ideas, please let me know—I’ve been working on this problem for a while now and hit a complete dead end.