this was a problem at a competition today, (which already ended, and my solution only got 25% of the examples correct)
the problem: A traveler traveled for N days, visiting a city on each day. Some cities have been visited multiple times. Write a program that tells us the length of the longest time period where the traveler went to a different city each day!
input : number of days (1 < N < 100,000) and in the next line, the "names" of the cities 1 < S[i] < N (which are just separate integers).
example input:
8
1 2 1 6 3 5 2 5
output : 5 ----- explanation: (1 6 3 5 2) (but I think by this logic 2 1 6 3 5 would also be correct?)
here is my solution, which gave a correct answer for 25% of the test cases, and wrong answer for the other 75%. We could only see two test cases, and the other one is with 10000 numbers, I would not copy that here.
#include <iostream>
#include <vector>
#include <set>
#include <bits/stdc .h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, input;
cin >> n;
vector<int> cities;
for(int i = 0; i < n; i )
{
cin >> input;
cities.push_back(input);
}
int maxlength = 0;
set<int> myset;
for(int i = 0; i < n; i )
{
if(myset.find(cities[i]) != myset.end())
{
myset.clear();
}
myset.insert(cities[i]);
if(myset.size() > maxlength)
maxlength = myset.size();
}
cout << maxlength << endl;
return 0;
}
I believe this problem really just boils down to finding the longest set of different numbers in the given array (It's possible that I'm wrong). However, my solution was not completely correct, according to the site.
PS: I find it weird that it gives a correct answer sometimes, and an incorrect other times. It never runs out of the time barrier. I thought a program is either always correct or always incorrect, anyways, sorry if this question had already been asked here, I didn't find an exact same question like this. And obviously I'm open to all sorts of criticism, after all, we're here to learn.
CodePudding user response：
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <complex>
#include <numeric>
using namespace std;
int main()
{
vector<int> cities = {1, 2, 1, 6, 3, 5, 2, 5};
vector<int>::size_type startingCityIndex = 0;
vector<int>::size_type maxStartCityIndex;
vector<int>::size_type maxEndCityIndex;
unsigned maxDistance = 0;
set<int> visitedCities = {cities[0]};
// Create distance vector F[n] := f[n 1] - f[n] (undefined for n = cities.size() - 1)
vector<int> distances;
for(vector<int>::size_type cityIndex = 0; cityIndex < cities.size() - 1; cityIndex)
distances.push_back(abs(cities[cityIndex 1] - cities[cityIndex]));
// Suppose he travels to each city from startingCityIndex
for(vector<int>::size_type traveledCityIndex = 1; traveledCityIndex < cities.size(); traveledCityIndex)
// If he has not visisted the city
if(visitedCities.find(cities[traveledCityIndex]) == visitedCities.end()) {
// If the visisted city isn't the last one
if(traveledCityIndex != cities.size() - 1)
visitedCities.insert(cities[traveledCityIndex]);
// Else it is the last one
else {
unsigned distance = accumulate(distances.cbegin() startingCityIndex, distances.cend(), 0U);
if(distance > maxDistance) {
maxEndCityIndex = traveledCityIndex;
maxStartCityIndex = startingCityIndex;
}
}
// Else he has visited the city. Consider his path up to that point and start new path, clearing visitedCities and setting new startingCityIndex
} else {
unsigned distance = accumulate(distances.cbegin() startingCityIndex, distances.cbegin() traveledCityIndex - 2, 0U);
if (distance > maxDistance) {
maxDistance = distance;
maxStartCityIndex = startingCityIndex;
maxEndCityIndex = traveledCityIndex - 1;
}
while(cities[startingCityIndex] != cities[traveledCityIndex]) {
visitedCities.erase(cities[startingCityIndex ]);
}
visitedCities.erase(cities[startingCityIndex ]);
--traveledCityIndex;
}
// Output answer
for(vector<int>::size_type cityIndex = maxStartCityIndex; cityIndex < maxEndCityIndex; cityIndex)
cout << cities[cityIndex] << " ";
cout << cities[maxEndCityIndex] << endl;
// Success!
return EXIT_SUCCESS;
}
O(N) memory and O(N) complexity as the startingCityIndex and traveledCityIndex march forward over the cities at most one time.
CodePudding user response：
Keep a deque of the current run, and a deque of the all time so far best run, and a set of elements in the current best run.
To advance, push the next city into the current run. Determine if there is a duplicate by looking in the set. If not, update best maybe, and continue.
If duplicate, walk current from front, removing from set and deque until you see the "next city" you just added in the current deque.
This should be correct, but there is a simple optimization: replace deques with pairs of indexes (half open interval) into original list. Avoids needless copies. At 100,000 elements can keep them all in memory.
I think this in O(nlgn), as each element is added to the active deque once and removed once, plus set lookups.
CodePudding user response：
The problem boils down to finding max consecutive cities which are not visited earlier.
You can use unordered_set to keep track of already visited cities and a variable to keep track of number of consecutive non-visited cities traveled.
int main() {
int n;
int cur_len;
int max_len;
unordered_set<int> s;
int city;
cin >> n;
for (int i = 0; i < n; i ) {
cin >> city;
if (s.find(city) == s.end()) {
// city is not visited earlier.
s.insert(city);
cur_len ;
if (cur_len > max_len) {
max_len = cur_len;
}
} else {
// reset max length.
cur_len = 0;
}
}
// Answer
cout << max_len;
return 0;
}