Софтуерно Инженерство
Loading...
+ Нов въпрос
WasteOfRAM avatar WasteOfRAM 5 Точки

04. Ranges

Кода изпълнява задачата но за 0.920 s. Пробвах няколко вариации но нещо не ми се получава. Ако може някои да подскаже коя е бавната част.

void chckIfInRange(const std::vector<std::shared_ptr<std::pair<int, int>>>& ranges, const std::vector<int>& numbersToCheck)
{
	std::string inOrOut;
	for (const int& num : numbersToCheck)
	{
		for (const auto& range : ranges)
		{
			if (num >= range->first && num <= range->second)
			{
				inOrOut = "in";
				break;
			}
			else
			{
				inOrOut = "out";
			}
		}
		std::cout << inOrOut << '\n';
	}
}

int main()
{
	
	std::vector<std::shared_ptr<std::pair<int, int>>> ranges;
	std::shared_ptr<std::pair<int, int>> range;
	int from;
	int to;

	while (std::cin >> from >> to)
	{
		range = std::make_shared<std::pair<int, int>>(from,to);
		ranges.emplace_back(range);
	}

	std::cin.clear();
	std::cin.ignore(1);

	int checkNum;
	std::vector<int> numbersToCheck;

	while (std::cin >> checkNum)
	{
		numbersToCheck.emplace_back(checkNum);
	}


	chckIfInRange(ranges, numbersToCheck);
	

	//system("PAUSE");
 	return 0;
}

 

Тагове:
0
C++ Advanced
galin_kostadinov avatar galin_kostadinov 163 Точки

Привет!

 

1. Ако се очаква да четеш или печаташ повече на брой входни/изходни данни, то за да стане по-бързо използвай следното преди четенето:

std::cin.sync_with_stdio(false);
std::cout.sync_with_stdio(false);

или

std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);

https://stackoverflow.com/questions/31162367/significance-of-ios-basesync-with-stdiofalse-cin-tienull

 

2. Бих те посъветвал да използваш lower_bound на вместо обхождане на ranges чрез Range-based for loop, като за целта колекцията ти трябва да е сортирана:

std::vector<std::pair<int, int>> ranges;

std::sort(ranges.begin(), ranges.end());

auto iterator = lower_bound(ranges.begin(), ranges.end(), std::make_pair(num, num));

http://www.cplusplus.com/reference/algorithm/lower_bound/

 

(По прицип може да минеш и без pair<> тъй като нямаш пресичане на отделните интервали)

 

( lower_bound ще ти върне итератор към коткретния pair ако first == num или към следващия pair ако first < num.

Имаш възможност да използаш iterator--;

int id = std::distance(ranges.begin(), iterator); - индекс
if (num >= ranges.at(id).first && num <= ranges.at(id).second){
...
}else{
...
})

 

3. Може директо да четеш число от конзолата, вместо да го записваш във вектор и след това да го проверяваш дали е в даден интервал.

 

4. Има ли някаква причина да използаваш пойтър към pair?

std::shared_ptr<std::pair<int, int>>

 

Поздрави!

0
16/12/2019 16:53:07
MartinBG avatar MartinBG 1284 Точки

Решението е бавно, защото за всяко число се обхождат всички* ranges, т.е. алгоритъмът е със сложност O(N * R), където N - брой числа, R - брой ranges.

По условие в 30% от тестовете N и R са с до 10 елемента, т.е. имаме до 100 проверки (N * R = 10 * 10 = 100).

За останалите тестове, N може да е до 100 000, а R - до 10 000, т.е получаваме 1 000 000 000 проверки за най-лошият сценарий. 

 

Трябва да потърсиш алтернативно решение, при което няма толкова силна зависимост между N и R.

В условието се казва, че няма застъпване в ranges: 

You are given a set of ranges, in which no two ranges intersect. That means that no range contains the from or to of another range.
 

Това е важно, защото ни позволява да сортираме ranges еднократно, а търсенето в сортирани колекции е с логаритмична сложност (напр. за 10 000 елемента ще имаме ~13.3 проверки).

Оптимален алгоритъм за тази задача ще има сложност O(N * log(R)), което при лимитите дадени в условието, е около 750 пъти по-бързо от O(N * R).

Algorithm library има полезни функции, които може да спестят част от кода, например:

 

[*] Разбира се, ако числото е в първия range, не се обхождат останалите, но правилото е да се гледа най-лошия сценарий, т.е. когато числото не е в никой range, или е в последният такъв. 

0
16/12/2019 17:45:54
Zmyrt avatar Zmyrt 3 Точки

Заформи се клуб  "30/100"  в групата явно. И аз имам същите проблеми със скоростта а вече 4 решения написах. В нито едно от тях не се избягва проверката отнемаща R*N операции ( за всяко число да се обходят всички обхвати ) и ми се струва , че основният проблем е там както каза Мартин . Как точно да го заобиколим обаче не се сещам до момента 

0
Filipbg avatar Filipbg 26 Точки

Добави този include #include <bits/stdc++.h>

https://www.geeksforgeeks.org/fast-io-for-competitive-programming/

Също така добави и този код преди потоците 

    cin.sync_with_stdio(false);
    cout.sync_with_stdio(false);
    ios_base::sync_with_stdio(false);
    ostringstream::sync_with_stdio(false);
    istringstream::sync_with_stdio(false);
    ostream::sync_with_stdio(false);
    istream::sync_with_stdio(false);
    cin.tie(NULL);

И ползвай '/n' вместо std::endl при принтирането.

Така се маха сихронизацията на input/output-a и проверките минават доста по-бързо. Особено при 1 000 000 000 проверки.

lower_bound и upper_bound както MartinBG е добавил са нужни за тази задача и помагат доста. 

До вчера и аз си късах нервите с тази задача. И така мина. Разрових се в нета за тези разлики в скоростта и намерих тази статия в която е много добре обяснено: 

https://www.modernescpp.com/index.php/c-core-guidelines-improved-performance-with-iostreams

0