fatemehkarimi's blog

By fatemehkarimi, history, 7 months ago, In English,

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;
}

Read more »

 
 
 
 
  • Vote: I like it
  • +2
  • Vote: I do not like it

By fatemehkarimi, history, 23 months ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it
  • +4
  • Vote: I do not like it