11. DATE WITH THE HIGHEST EARNINGS - SOLUTION
The TASK is on the Qualifying page for district competitions
Two ways of solving will be shown here, one is with the use of dynamic arrays - vectors, and the other is with the application of a data-map dictionary. The first method is not efficient enough for a large amount of data, and in that case an error would be obtained when testing TLE (timeline exception). However, by solving in this way, about 70% of the test cases would pass. The second way is also effective for a large amount of data.
And the solution method - using a dynamic array
To use vectors, you can use the following article Dynamic array-vector
Instruction:
Load data as strings line by line. From the string, first extract the date as a separate string and the earnings separately. Arrange in two rows. Change the date so that it first contains the year, then the month, and finally the day, so that sorting can be done more easily. Sort both strings by date, from oldest to newest date. Rewrite the strings into new strings, but so that the dates are unique (repeated only once), and the earnings corresponding to that date are in the same position only in the second string. There should be a sum of earnings with the same date. At the end, write the first element of the series of earnings, because the first element is actually the highest earned income. After that, print the initial elements of the string with dates as many times as there are dates with maximum earnings.
Solution:
First you need to include the required headers:
#include < iostream >
#include< vector >
#include< string >
#include< iomanip >
Then inside the main method, we create vectors as well as other necessary data
int n,ind=0;/*n-number of items on the account*/
cin>>n; //Entering n
cin.ignore();//Empty string buffer
vector< string >datesAll;/* dates that are extracted from the loaded rows*/
vector< string >dates; /*unique dates*/
vector< double >money; /*earnings separated from the entered rows*/
vector< double >earnings;
string line; //single row
int positions[2]= {2,5}; //positions where sub-string separator characters are locatedInside the loop, one row is loaded, then the dates and earnings are separated and placed in separate strings.
while(getline(cin,line)) /*loads the next line from standard input*/
{
int pos=line.find(" ");// The space character is used to separate the entered line of text into date and earnings
string date=line.substr(0,pos);//extracts a date from a string
string dd=date.substr(0,positions[0]);//extracts the day from the date
string mm=date.substr(positions[0]+1,2);//extracts the month from the date
string yyyy=date.substr(6);// extracts the year from the date
string datesReversed=yyyy+mm+dd;//prints the date as "yyyymmdd"
double earnings=stod(line.substr(poz+1));//extracts the earnings as a string, and then converts it into a double data
datesAll.push_back(datesReversed); //adds a date to the end of the "datesAll" vector
money.push_back(earnings); //adds profit to the end of the "money" vector
ind++; //increases the number of cycles by 1
if(ind==n)break; // break the loop when "n" rows are read
}
Then the loaded vectors are sorted. Here, the selection method was used for sorting. You can view the algorithm on the website: Sorting arrays
/*sorting an array using the selection method*/
for(int i=0; i < datesAll.size()-1; i++)
{
for(int j=i+1; j
{
string d1=datesAll[j];
string d2=datesAll[i];
bool relocation=d1 < d2;
if(relocation)
{
double b=money[i];
money[i]=money[j];
money[j]=b;
string a=datesAll[i];
datesAll[i]=datesAll[j];
datesAll[j]=a;
}
}
}
The next thing to do is to add up all earnings during the same date and form two new series of earnings and dates, so that each date appears only once and in the second series, in the corresponding position, is the total earnings for the corresponding date.
//calculation of total earnings
string prevDate=""; /*previous date */
for(int i=0,day=-1; i < datesAll.size(); i++) /*loop through the loaded array with all dates*/
{
string date=datesAll[i]; /*the extracted date at the current string position*/
double moneySingle=money[i]; /*separated earnings from a series of earnings in the current position*/
if(date!=prevDate) /*if the date is different from the previous one in the sequence*/
{
day++; /*increments the position of the overwritten string only if the date is different from the previous one*/
dates.push_back(date);/*adds a date to a new vector for dates(unique)*/
earnings.push_back(moneySingle);// /*adds earnings to a new array*/
}
else /*if the dates are equal*/
{
earnings[day]=earnings[day]+moneySingle; /*if it is the same date, the earnings are added together*/
}
prevDate=date; /*the current date becomes the previous date for the next cycle*/
}
Then the new strings are sorted, by earnings, from the highest to the lowest.
/*sort by earnings, descending*/
for(int i=0; i < earnings.size()-1; i++)
{
for(int j=i+1; j
{
if(earnings[j]>earnings[i])
{
double b=earnings[i];
earnings[i]=earnings[j];
earnings[j]=b;
string a=dates[i];
dates[i]=dates[j];
dates[j]=a;
}
}
}
It remains to write the highest earnings, as well as all dates with those highest earnings.
double prev=-1;
for(int i = 0; i < earnings.size(); i++)
{
double moneySingle=earnings[i];
if(i==0)
cout << fixed << setprecision(2) << moneySingle << endl;
if(i>0 && moneySingle!=prev)
break;
string year=dates[i].substr(0,4);
string month=dates[i].substr(4,2);
string day=dates[i].substr(6,2);
cout << day + "-" + month + "-" + year << endl;
prev=moneySingle;
}
A special method for sorting, with a somewhat more efficient algorithm
If we write the previous code a little better, with the use of a special sorting method and for the sorting algorithm we use the insertion method, which is faster to execute than the selection method, the code would be:
#include < iostream >
#include < vector >
#include < string >
#include < iomanip >
using namespace std;
void sorting(vector &datesAll,vector &money)
{
int main()
{
#include < vector >
#include < string >
#include < iomanip >
using namespace std;
void sorting(vector
{
//sorting an array using the insertion method
int j;
for(int i=1; i < datesAll.size(); i++)
{
}int j;
for(int i=1; i < datesAll.size(); i++)
{
string b=datesAll[i];
double a=money[i];
for(j=i-1; j>=0; j--)
{
datesAll[j+1]=b;
money[j+1]=a;
}double a=money[i];
for(j=i-1; j>=0; j--)
{
if(datesAll[j] > b)
{
else break;
}{
datesAll[j+1]=datesAll[j];
money[j+1]=money[j];
}money[j+1]=money[j];
else break;
datesAll[j+1]=b;
money[j+1]=a;
int main()
{
int n,ind=0;
cin >> n;
cin.ignore();
vector < string > datesAll;
vector < string > dates;
vector < double >money;
vector < double >profit;
string line;
int positions[2]= {2,5};
while(getline(cin,line))
{
/*sorting*/
sorting(datesAll,money);
/*calculating the earning*/
string prevDate="";
for(int i=0, dan=-1; i < datesAll.size(); i++)
{
/*sorting by earnings*/
for(int i=0; i < profit.size()-1; i++)
{
double prev=-1;
// printing
for(int i=0; i < profit.size(); i++)
{
return 0;
}
cin >> n;
cin.ignore();
vector < string > datesAll;
vector < string > dates;
vector < double >money;
vector < double >profit;
string line;
int positions[2]= {2,5};
while(getline(cin,line))
{
int pos=line.find(" ");
string date=line.substr(0,poz);
string dd=date.substr(0,positions[0]);
string mm=date.substr(positions[0]+1,2);
string yyyy=date.substr(6);
string dateReversed=yyyy+mm+dd;
double earnings=stod(line.substr(pos+1));
datumiSvi.push_back(dateReversed);
money.push_back(earnings);
ind++;
if(ind==n)break;
}string date=line.substr(0,poz);
string dd=date.substr(0,positions[0]);
string mm=date.substr(positions[0]+1,2);
string yyyy=date.substr(6);
string dateReversed=yyyy+mm+dd;
double earnings=stod(line.substr(pos+1));
datumiSvi.push_back(dateReversed);
money.push_back(earnings);
ind++;
if(ind==n)break;
/*sorting*/
sorting(datesAll,money);
/*calculating the earning*/
string prevDate="";
for(int i=0, dan=-1; i < datesAll.size(); i++)
{
string date=datumiSvi[i];
double moneySingle=money[i];
if(date!=prevDate)
{
else
{
prevDate=date;
}double moneySingle=money[i];
if(date!=prevDate)
{
day++;
dates.push_back(date);
profit.push_back(moneySingle);
}dates.push_back(date);
profit.push_back(moneySingle);
else
{
profit[day]=profit[day]+moneySingle;
}prevDate=date;
/*sorting by earnings*/
for(int i=0; i < profit.size()-1; i++)
{
for(int j=i+1; j < profit.size(); j++)
{
}{
if(profit[j] > profit[i])
{
}{
double b=profit[i];
profit[i]=profit[j];
profit[j]=b;
string a=dates[i];
dates[i]=dates[j];
dates[j]=a;
}profit[i]=profit[j];
profit[j]=b;
string a=dates[i];
dates[i]=dates[j];
dates[j]=a;
double prev=-1;
// printing
for(int i=0; i < profit.size(); i++)
{
double moneySingle=profit[i];
if(i==0)
break;
string year=dates[i].substr(0,4);
string month=dates[i].substr(4,2);
string day=dates[i].substr(6,2);
cout << day + "-" + month + "-" + year << endl;
prev=moneySingle;
}if(i==0)
cout << fixed << setprecision(2) << moneySingle << endl;
if(i>0 && moneySingle!=prev)break;
string year=dates[i].substr(0,4);
string month=dates[i].substr(4,2);
string day=dates[i].substr(6,2);
cout << day + "-" + month + "-" + year << endl;
prev=moneySingle;
return 0;
II way of solving - using a data dictionary
A map is used here to house key-value data pairs. Dates are used as the key, and earnings values are used as the key. You will find what you need to know about maps at the following link: Dictionary of data-maps in C++
To use maps, you need to include the "map" header. Besides "map", there is also multimap. While the "map" data type only stores unique keys, in our case dates, the "multimap" can repeat keys. In this example, it is more convenient to use "map". What should also be noted is that the keys in the map are sorted in ascending order. In order for them to be sorted in descending order, the comparator cmp is introduced as the third parameter, which is defined as a function that returns the logical data bool.
Solution:
#include < iostream >
#include < vector >
#include < string >
#include< map >
#include< algorithm >
#include < functional >
#include < iomanip >
using namespace std;
// Comparator function to sort pairs
// according to second value
bool cmp(pair< string, double >& a, pair< string, double >& b)
{
int main()
{
#include < vector >
#include < string >
#include< map >
#include< algorithm >
#include < functional >
#include < iomanip >
using namespace std;
// Comparator function to sort pairs
// according to second value
bool cmp(pair< string, double >& a, pair< string, double >& b)
{
return a.second > b.second;
}int main()
{
int n,ind=0;
cin >> n;
cin.ignore();
map < string, double > dailyEarnings;
string line;
int positions[2]= {2,5};
while(getline(cin,line))
{
/*printing the data stored inside the map*/
map < string, double>::iterator itr;
/* Declaring a vector of pairs from a map*/
vector < pair< string, double > > A;
/* Copy key-value pair from Map */
/* to vector of pairs */
for (auto& it : dailyEarnings)
{
sort(A.begin(),A.end(),cmp);
vector < pair< string, double > >::iterator itA;
vector<pair < string, double>>::iterator itrPre=A.begin();
int i=0;
vector < pair< string, double > >::iterator itrR;
for(itrR = A.begin(); itrR !=A.end(); ++itrR )
{
return 0;
}
cin >> n;
cin.ignore();
map < string, double > dailyEarnings;
string line;
int positions[2]= {2,5};
while(getline(cin,line))
{
int pos=line.find(" ");
string date=line.substr(0,pos);
string dd=date.substr(0,positions[0]);
string mm=date.substr(pozicije[0]+1,2);
string yyyy=date.substr(6);
string dateReversed=yyyy+mm+dd;
double earning=stod(line.substr(poz+1));
map<string,double >::iterator itKey;
itKey=dailyEarnings.find(dateReversed);/*Search for the position of the same date in the map, if there is one*/
if(itKey == dailyEarnings.end())/*if the same date was found */
{
else
{
ind++;
if(ind==n)break;
}string date=line.substr(0,pos);
string dd=date.substr(0,positions[0]);
string mm=date.substr(pozicije[0]+1,2);
string yyyy=date.substr(6);
string dateReversed=yyyy+mm+dd;
double earning=stod(line.substr(poz+1));
map<string,double >::iterator itKey;
itKey=dailyEarnings.find(dateReversed);/*Search for the position of the same date in the map, if there is one*/
if(itKey == dailyEarnings.end())/*if the same date was found */
{
dailyEarnings.insert(pair<string,double>(dateReversed,earning));
}else
{
itKey->second += earning;
}ind++;
if(ind==n)break;
/*printing the data stored inside the map*/
map < string, double>::iterator itr;
/* Declaring a vector of pairs from a map*/
vector < pair< string, double > > A;
/* Copy key-value pair from Map */
/* to vector of pairs */
for (auto& it : dailyEarnings)
{
A.push_back(it);
}sort(A.begin(),A.end(),cmp);
vector < pair< string, double > >::iterator itA;
vector<pair < string, double>>::iterator itrPre=A.begin();
int i=0;
vector < pair< string, double > >::iterator itrR;
for(itrR = A.begin(); itrR !=A.end(); ++itrR )
{
if(i==0)
double earnPrev=itrPre->second;
if(i>0 && earn!=earnPrev)
string year=date.substr(0,4);
string month=date.substr(4,2);
string day=date.substr(6,2);
cout << day + "-" + month + "-" + year << endl;
i++;
itrPre=itrR;
}
cout << fixed << setprecision(2) << itrR->second << endl;
double earn=itrR->second;double earnPrev=itrPre->second;
if(i>0 && earn!=earnPrev)
break;
string date=itrR->first;string year=date.substr(0,4);
string month=date.substr(4,2);
string day=date.substr(6,2);
cout << day + "-" + month + "-" + year << endl;
i++;
itrPre=itrR;
return 0;
Return to the web page Preparation for district competitions