This is something which I was happy to achieve on my own for 2004D - Colored Portals. I quickly achieved the greedy binary search, but I had few un-intended bugs (ideally would've saved time if I did a code review instead of debugging, but as a trade-off you do get a confidence that it will get resolved after debugging)
Here is the why this blog is for you:
- You are newb like me.
- You get frustrated when your code randomly gets WA and you don't know what the edge case/bug is there in your code.
Here is probably why this blog is not for you:
- You are too good (please ignore, although, you can improvements are welcome!)
- You probably know what to do, but just don't feel like debugging. (well, that's the only way I know which will work for sure for now)
Thing which helped the most:
Debug template — by Anshul_Johri
TL;DR of the debugger
- Write the most correct version you can think of for the solution (i.e via brute force)
- Compare them both — to check for wrong answers.
- Fix the bugs/edge cases.
- Voila!
The code for debugging
My Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifndef ONLINE_JUDGE
#include "cp_templates/debug_template.cpp"
#else
#define debug(...)
#define debugArr(...)
#endif
#define errorl(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args);cout<<"\n";}
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args);cout<<"___";}
#define debugl(args...) {if(DEBUG){ string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args);cout<<"\n";}}
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
cout << *it << " = " << a <<" , ";
err(++it, args...);
}
#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define vars ll h,i,j,k,d,l,p,q,r,x,y,a,b,c,v,var,n,m,z,s,ans,ind1,ind2,flag,limit1,limit2,limit3,mod;
#define vll vector<ll>
#define testcase ll tt; cin >> tt; while(tt--)
const ll MOD = 1e9 + 7;
const ll INF = 1e9;
const ll ANTI_CONST = 7;
const bool DEBUG = true;
map<string, ll> asdf = {
{"BG", 1ll},
{"BR", 2ll},
{"BY", 3ll},
{"GR", 4ll},
{"GY", 5ll},
{"RY", 6ll},
};
vll anti{0, 6, 5, 4, 3 ,2 ,1};
vector<vll> graph{
{0},
{2, 3, 4, 5},
{1, 3, 4, 6},
{1, 2, 5, 6},
{1, 2, 5, 6},
{1, 3, 4, 6},
{2, 3, 4, 5},
};
ll calc_min_cost(ll a, ll b, vll &arr, vector<vll>&types, map<pair<ll,ll>, ll>& cache, bool debug){
debug(arr);
if(b<a){
ll c = a;
a = b;
b = c;
}
ll p = arr[a];
ll q = arr[b];
debug(a,b,p,q);
if (cache.find({a,b}) != cache.end()){
return cache[{a,b}];
}
if (p+q != ANTI_CONST){
cache[{a,b}] = abs(a-b);
return abs(a-b);
}
ll ans = INF;
for (ll i=0; i<graph[p].size(); i++){
ll ind = graph[p][i];
debug(a, b, ind, ans, types[ind]);
if (types[ind].size() == 0) continue;
// [x], a, b
auto itr = lower_bound(types[ind].begin(), types[ind].end(), a-1);
if(itr == types[ind].end())itr=prev(itr);
if(itr != types[ind].begin() && *itr>a)itr=prev(itr);
ll v = *itr;
debug(v);
ans = min(ans, abs(v-a) + abs(v-b));
// a, [x], b
itr = lower_bound(types[ind].begin(), types[ind].end(), a);
if(itr == types[ind].end())itr=prev(itr);
if (itr != types[ind].end()){
v = *itr;
ans = min(ans, abs(v-a) + abs(v-b));
}
debug(v);
// a, b, [x]
itr = lower_bound(types[ind].begin(), types[ind].end(), b);
if(itr == types[ind].end())itr=prev(itr);
if (itr != types[ind].end()){
v = *itr;
ans = min(ans, abs(v-a) + abs(v-b));
}
debug(v);
}
if (ans == INF)ans=-1;
cache[{a,b}] = ans;
debug(a,b,ans);
return ans;
}
ll calc_min_cost(ll a, ll b, vll &arr, vector<vll>&types, map<pair<ll,ll>, ll>& cache){
// debug(arr);
if(b<a){
ll c = a;
a = b;
b = c;
}
ll p = arr[a];
ll q = arr[b];
// debug(a,b,p,q);
if (cache.find({a,b}) != cache.end()){
return cache[{a,b}];
}
if (p+q != ANTI_CONST){
cache[{a,b}] = abs(a-b);
return abs(a-b);
}
ll ans = INF;
for (ll i=0; i<graph[p].size(); i++){
ll ind = graph[p][i];
// debug(a, b, ind, ans, types[ind]);
if (types[ind].size() == 0) continue;
// [x], a, b
auto itr = lower_bound(types[ind].begin(), types[ind].end(), a-1);
if(itr == types[ind].end())itr=prev(itr);
if(itr != types[ind].begin() && *itr>a)itr=prev(itr);
ll v = *itr;
// debug(v);
ans = min(ans, abs(v-a) + abs(v-b));
// a, [x], b
itr = lower_bound(types[ind].begin(), types[ind].end(), a);
if(itr == types[ind].end())itr=prev(itr);
if (itr != types[ind].end()){
v = *itr;
ans = min(ans, abs(v-a) + abs(v-b));
}
// debug(v);
// a, b, [x]
itr = lower_bound(types[ind].begin(), types[ind].end(), b);
if(itr == types[ind].end())itr=prev(itr);
if (itr != types[ind].end()){
v = *itr;
ans = min(ans, abs(v-a) + abs(v-b));
}
// debug(v);
}
if (ans == INF)ans=-1;
cache[{a,b}] = ans;
// debug(a,b,ans);
return ans;
}
ll calc_min_cost_brute(ll a, ll b, vll &arr, map<pair<ll,ll>, ll>& cache){
if(b<a){
ll c = a;
a = b;
b = c;
}
ll p = arr[a];
ll q = arr[b];
// debugl(a,b,p,q);
if (cache.find({a,b}) != cache.end()){
return cache[{a,b}];
}
if (p+q != ANTI_CONST){
cache[{a,b}] = abs(a-b);
return abs(a-b);
}
ll ans = INF;
for(ll i=0;i<arr.size();i++){
ll z = arr[i];
if(z!=p && z!=q){
ans = min(ans, abs(i-a) + abs(i-b));
}
}
if (ans == INF)ans=-1;
cache[{a,b}] = ans;
// debugl(a,b,ans);
return ans;
}
ll handle_testcase_optimized(vector<string> input, ll left, ll right){
ll i;
ll n = input.size();
vll arr(n);
vector<vll> types(7);
map<pair<ll,ll>, ll> cache;
for(i=0;i<n;i++){
arr[i]=asdf[input[i]];
types[asdf[input[i]]].emplace_back(i);
}
return calc_min_cost(left, right, arr, types, cache);
}
ll handle_testcase_optimized(vector<string> input, ll left, ll right, bool debug){
ll i;
ll n = input.size();
vll arr(n);
vector<vll> types(7);
map<pair<ll,ll>, ll> cache;
for(i=0;i<n;i++){
arr[i]=asdf[input[i]];
types[asdf[input[i]]].emplace_back(i);
}
return calc_min_cost(left, right, arr, types, cache, debug);
}
ll handle_testcase_brute(vector<string> input, ll left, ll right){
ll i;
ll n = input.size();
vll arr(n);
map<pair<ll,ll>, ll> cache;
for(i=0;i<n;i++){
arr[i]=asdf[input[i]];
}
return calc_min_cost_brute(left, right, arr, cache);
}
vector<vector<string>> generate_input(ll length){
vector<string> inputs = {"BG", "BR", "BY", "GR", "GY", "RY"};
if (length==1){
return {
{"BG"},
{"BR"},
{"BY"},
{"GR"},
{"GY"},
{"RY"},
};
}
vector<vector<string>>temp = generate_input(length-1);
vector<vector<string>>answer;
for(ll i=0;i<temp.size();i++){
vector<string>&row = temp[i];
for(ll j=0;j<inputs.size();j++){
row.emplace_back(inputs[j]);
answer.emplace_back(row);
row.pop_back();
}
}
return answer;
}
void wrong_answer_tester(){
ll i,j,k,l,x,y;
for(i=9;i<10;i++){
auto inputs = generate_input(i);
// print_all_inputs(inputs);
for(j=0;j<inputs.size();j++){
for(k=0;k<inputs[j].size();k++){
for(l=0;l<inputs[j].size();l++){
ll n = inputs[j].size();
auto input = inputs[j];
auto opti = handle_testcase_optimized(input, k, l);
auto brute = handle_testcase_brute(input, k, l);
if(opti != brute){
handle_testcase_optimized(input,k,l,true);
for(x=0;x<inputs[j].size();x++)cout<<inputs[j][x]<<" ";cout<<endl;
debugl(n, opti, brute, k, l);
return;
}
}
}
}
}
}
int main()
{
boost;
vars;
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
wrong_answer_tester();
cout<<"over!\n";
// testing/debugging
a = handle_testcase_optimized({"BG", "BG", "BG", "BR", "GY", "BR", "BG"}, 3, 4);
b = handle_testcase_brute({"BG", "BG", "BG", "BR", "GY", "BR", "BG"}, 3, 4);
debugl(a,b);
// debugging generate_input
// auto in = generate_input(3);
// for(i=0;i<in.size();i++){
// for(j=0;j<in[i].size();j++){
// cout<<in[i][j]<<", ";
// }cout<<endl;
// }
}
(feel free to suggest improvements which I am sure there will be as my main goal was to fix bugs and not improving my debugger code)
