### fatemehkarimi's blog

By fatemehkarimi, history, 7 months ago, ,

Hello my dear friends @codeforces!

my team failed to solve Problem H of Tehran ICPC 2018 during the contest. I tried to solve it with a greedy algorithm after the contest but I failed. I have the test cases, and even when I solve the failed test case with hand, it ends with a wrong answer always greater than the accepted answer. this shows my approach is totally wrong. I thought a lot about the problem, but no other algorithm comes to my mind. can anyone help me to solve it?

problem statements

test case

this is the code that fails.

//TEHRAN SITE
//2018-Problem H

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void)
{
int n, smaller, bigger;
cin >> n >> smaller >> bigger;
if(bigger < smaller)
swap(smaller, bigger);

vector <int> coordinates(n);
for(int i = 0; i < n; ++i)
cin >> coordinates[i];

sort(coordinates.begin(), coordinates.end());

vector <int> anntena(n, smaller);

for(int i = 0; i < n; ++i){
int max_dis = max((i - 1 >= 0 ? coordinates[i] - coordinates[i - 1] : 0)
, i + 1 < n ? coordinates[i + 1] - coordinates[i]: 0);

if(max_dis > smaller)
anntena[i] = bigger;
if(max_dis > bigger){
cout << -1 << endl;
return 0;
}
}

long long int result = 0;
for(auto a : anntena)
result += a;
cout << result << endl;
return 0;
}


• +2

By fatemehkarimi, history, 23 months ago, ,

I had a hard time finding a solution to the problem "Sherlock and cost" [](https://www.hackerrank.com/challenges/sherlock-and-cost/problem)but I wasn't able to solve it. then I searched the whole internet and read the people's code. I understood what they do(i.e understand their code) but I can't understand why this algorithm is true and what is the recursion??

can anyone tell me how does its dynamic approach work?? this is the code I read for this problem