patterncppMinor
Counting the occurrences of bank account numbers for SPOJ challenge
Viewed 0 times
thecountingoccurrenceschallengenumbersaccountspojbankfor
Problem
I am solving a problem on SPOJ and am currently unsatisfied with my submission time, given that my fastest time is 0.28s (which ranks me 123/5037) and the leading submission is 0.04s.
The problem is pretty simple: Given a list of bank account numbers, print the bank account number along with the frequency at which it is repeated.
Input
t [the number of tests <= 5]
n [the number of accounts<= 100 000]
[list of accounts]
[empty line]
[next test cases]
Output
[sorted list of accounts with the number of repeated accounts]
[empty line]
[other results]
Example:
In order to solve this, I am using a map where the key is the bank account and the value is the frequency of repetition. However, I am first loading the bank accounts into a vector, and I am pretty sure this is one area where I am losing efficiency. I have tried to avoid using the vector, but my efficiency is greatly reduced.
What are some things that I can do to either improve my algorithm, or perhaps increase my I/O speed?
```
#include
#include
#include
#include
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int t;
std::cin >> t;
while (t--) {
int n, i;
std::cin >> n;
std::cin.ignore();
std::vector accounts(n);
for (i
The problem is pretty simple: Given a list of bank account numbers, print the bank account number along with the frequency at which it is repeated.
Input
t [the number of tests <= 5]
n [the number of accounts<= 100 000]
[list of accounts]
[empty line]
[next test cases]
Output
[sorted list of accounts with the number of repeated accounts]
[empty line]
[other results]
Example:
Input:
2
6
03 10103538 2222 1233 6160 0142
03 10103538 2222 1233 6160 0141
30 10103538 2222 1233 6160 0141
30 10103538 2222 1233 6160 0142
30 10103538 2222 1233 6160 0141
30 10103538 2222 1233 6160 0142
5
30 10103538 2222 1233 6160 0144
30 10103538 2222 1233 6160 0142
30 10103538 2222 1233 6160 0145
30 10103538 2222 1233 6160 0146
30 10103538 2222 1233 6160 0143
Output:
03 10103538 2222 1233 6160 0141 1
03 10103538 2222 1233 6160 0142 1
30 10103538 2222 1233 6160 0141 2
30 10103538 2222 1233 6160 0142 2
30 10103538 2222 1233 6160 0142 1
30 10103538 2222 1233 6160 0143 1
30 10103538 2222 1233 6160 0144 1
30 10103538 2222 1233 6160 0145 1
30 10103538 2222 1233 6160 0146 1In order to solve this, I am using a map where the key is the bank account and the value is the frequency of repetition. However, I am first loading the bank accounts into a vector, and I am pretty sure this is one area where I am losing efficiency. I have tried to avoid using the vector, but my efficiency is greatly reduced.
What are some things that I can do to either improve my algorithm, or perhaps increase my I/O speed?
```
#include
#include
#include
#include
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int t;
std::cin >> t;
while (t--) {
int n, i;
std::cin >> n;
std::cin.ignore();
std::vector accounts(n);
for (i
Solution
One area of inefficiency is here:
You're reading each account number, storing them then going back through the data to get the counts. The map class allows for a key that doesn't exist to create an entry on the fly. Using this will eliminate the second loop:
for (i = 0; i count;
for (i = 0; i second++;
} else {
count[accounts[i]] = 1;
}
}You're reading each account number, storing them then going back through the data to get the counts. The map class allows for a key that doesn't exist to create an entry on the fly. Using this will eliminate the second loop:
std::string temp = "";
std::map count;
for (i = 0; i < n; ++i) {
std::getline(std::cin, temp);
count[temp]++;
}
std::cout << "\n";Code Snippets
for (i = 0; i < n; ++i) {
std::getline(std::cin, accounts[i]);
}
std::cout << "\n";
std::map<std::string, int> count;
for (i = 0; i < accounts.size(); ++i) {
auto map_it(count.find(accounts[i]));
if (map_it != count.end()) {
map_it->second++;
} else {
count[accounts[i]] = 1;
}
}std::string temp = "";
std::map<std::string, int> count;
for (i = 0; i < n; ++i) {
std::getline(std::cin, temp);
count[temp]++;
}
std::cout << "\n";Context
StackExchange Code Review Q#156251, answer score: 2
Revisions (0)
No revisions yet.