UVa 299 Train Swapping Solution in C++ (Counting Inversions)

This problem is about counting the number of inversions in the given array. This problem can be solved with the help of insertion sort, but will be a naive method as it takes O(N²), so we are solving it with the help of merge sort in O(NlogN).
Things to learn:

• Divide and Conquer Paradigm to solve a given problem

#include<cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

long long merge(int* arr, int* temp, int left, int mid, int right){
	
	int i, j, k;
	long long inv_count = 0;

	i = left; j = mid; k = left;
	while ((i <= mid - 1) && (j <= right)) {
		if (arr[i] <= arr[j]) temp[k++] = arr[i++];
		else{
			temp[k++] = arr[j++];
			inv_count = inv_count + (mid - i);
		}
	}

	while (i <= mid - 1) temp[k++] = arr[i++];
	while (j <= right) temp[k++] = arr[j++];
	for (i=left; i <= right; i++) arr[i] = temp[i];
	
	return inv_count;
}

long long merge_sort(int* arr, int* temp, int left, int right)
{
	int mid;
	long long inv_count = 0;
	if (right > left){
		mid = (right + left)/2;
		inv_count  = merge_sort(arr, temp, left, mid);
		inv_count += merge_sort(arr, temp, mid+1, right);
		inv_count += merge(arr, temp, left, mid+1, right);
	}
	return inv_count;
}

  
int main(){
	int T; scanf("%d", &T);
	for(int t = 0; t<T; t++){
		int N; scanf("%d", &N);
		int A[N];
		for(int i = 0; i<N; i++){
			scanf("%d", &A[i]);
		}
		int* B = (int *)malloc(N*sizeof(int));
		printf("Optimal train swapping takes %lld swaps.\n", merge_sort(A, B, 0, N-1));
	}
	return 0;
}

Sample Input:

3
3
1 3 2
4
4 3 2 1
2
2 1

Sample Output:

Optimal train swapping takes 1 swaps.
Optimal train swapping takes 6 swaps.
Optimal train swapping takes 1 swaps.

Runtime: 0.002s

UVa 10194 Football (aka Soccer) Solution in C++

A fairly straight forward problem, just one time sorting is required. There are many things to learn from this problem, which are:

• Using constructor in struct
• Creating comparator function for two struct
• Interchangably using C++ and C string
• Map also accepts C string data format
• A pair can directly be inserted in map
• Copying a map to vector

#include<cstdio>
#include<cstring>
#include<map>
#include<algorithm>
#include<string>
#include<cstring>
#include<vector>

using namespace std;

struct Team{
	int n_games, n_wins, n_ties, n_loss,
		n_goals, n_goals_against, n_points;
	char* name;
	Team(char* TN) {
		name = TN;
		n_games = 0, n_wins = 0, n_ties = 0, n_loss = 0,
			n_goals = 0, n_goals_against = 0, n_points = 0;
	}
	Team(){
		n_games = 0, n_wins = 0, n_ties = 0, n_loss = 0,
			n_goals = 0, n_goals_against = 0, n_points = 0;
	}
};

bool teams_comparator(pair<string,Team> e1, pair<string,Team> e2){
	Team t1 = e1.second, t2 = e2.second;
    int p_a = t1.n_wins*3 + t1.n_ties, p_b = t2.n_wins*3 + t2.n_ties;
    int gd_a = t1.n_goals - t1.n_goals_against;
	int gd_b = t2.n_goals - t2.n_goals_against;
 
    if (p_a != p_b) return p_a > p_b;
    if (t1.n_wins != t2.n_wins) return t1.n_wins > t2.n_wins;
    if (gd_a != gd_b) return gd_a > gd_b;
    if (t1.n_goals != t2.n_goals) return t1.n_goals > t2.n_goals;
    if (t1.n_games != t2.n_games) return t1.n_games < t2.n_games;

    for(int i=0; i < strlen(t1.name); i++)
		t1.name[i] = tolower(t1.name[i]);
    for(int i=0; i < strlen(t2.name); i++)
		t2.name[i] = tolower(t2.name[i]);
 
    return strcmp( t1.name, t2.name) < 0;
 
}

int main(){
	int N; scanf("%d\n", &N);
	for(int n = 0; n<N; n++){
		char t_name[101]; gets(t_name);
		int n_teams; scanf("%d\n", &n_teams);
		map<string, Team> teams;
		for(int nt = 0; nt<n_teams; nt++){
			char team_name[31];
			gets(team_name);
			Team t = Team(team_name);
			teams.insert(make_pair(team_name, t));
		}

		int n_games; scanf("%d\n", &n_games);
		char game[1001];

		for(int ng = 0; ng<n_games; ng++){
			gets(game);
			int len = strlen(game);
			int i = 0, j = 0;

			// Teamname A and B
			char tn_a[31], tn_b[31];
			
			while(game[i]!='#'){tn_a[j++] = game[i++];}
			tn_a[j] = '\0'; j = 0; i++;

			// Number of goals characters
			char ngc_a[16], ngc_b[16];
			// Number of goals
			int ng_a, ng_b;

			while(game[i]!='@'){ngc_a[j++] = game[i++];}
			ngc_a[j] = '\0'; ng_a = atoi(ngc_a); j = 0; i++;
			while(game[i]!='#'){ngc_b[j++] = game[i++];}
			ngc_b[j] = '\0'; ng_b = atoi(ngc_b); j = 0; i++;

			while(game[i]!='\0'){tn_b[j++] = game[i++];}
			tn_b[j] = '\0'; j = 0; i++;

			// Getting the reference of the team A and B objects
			Team *ta = & teams[tn_a]; Team *tb = & teams[tn_b];

			(ta->n_games)++; (tb->n_games)++;
			ta->n_goals += ng_a; tb->n_goals += ng_b;
			ta->n_goals_against += ng_b; tb->n_goals_against += ng_a;

			if(ng_a == ng_b) (ta->n_ties)++, (tb->n_ties)++;
			else if(ng_a > ng_b) (ta->n_wins)++, (tb->n_loss)++;
			else (ta->n_loss)++, (tb->n_wins)++;
		}
		// Creating new vector for sorted teams
		vector< pair<string, Team> > s_teams;
		// Copying all the elements from map to a vector
		copy(teams.begin(), teams.end(), back_inserter(s_teams));
		// Sorting the teams according to the required parameters
		sort(s_teams.begin(), s_teams.end(), teams_comparator);

		puts(t_name);
		for (int j = 0; j<s_teams.size(); j++){
			printf("%d) %s %dp, %dg (%d-%d-%d), %dgd (%d-%d)\n",
				j+1, s_teams[j].first.c_str(),
				s_teams[j].second.n_wins*3 + s_teams[j].second.n_ties,
				s_teams[j].second.n_games, s_teams[j].second.n_wins,
				s_teams[j].second.n_ties, s_teams[j].second.n_loss,
				s_teams[j].second.n_goals - s_teams[j].second.n_goals_against,
				s_teams[j].second.n_goals, s_teams[j].second.n_goals_against);
		}
        if (n != N-1) printf("\n");
	}
	return 0;
}

Sample Input:

2
World Cup 1998 - Group A
4
Brazil
Norway
Morocco
Scotland
6
Brazil#2@1#Scotland
Norway#2@2#Morocco
Scotland#1@1#Norway
Brazil#3@0#Morocco
Morocco#3@0#Scotland
Brazil#1@2#Norway
Some strange tournament
5
Team A
Team B
Team C
Team D
Team E
5
Team A#1@1#Team B
Team A#2@2#Team C
Team A#0@0#Team D
Team E#2@1#Team C
Team E#1@2#Team D

Sample Output:

World Cup 1998 - Group A
1) Brazil 6p, 3g (2-0-1), 3gd (6-3)
2) Norway 5p, 3g (1-2-0), 1gd (5-4)
3) Morocco 4p, 3g (1-1-1), 0gd (5-5)
4) Scotland 1p, 3g (0-1-2), -4gd (2-6)

Some strange tournament
1) Team D 4p, 2g (1-1-0), 1gd (2-1)
2) Team E 3p, 2g (1-0-1), 0gd (3-3)
3) Team A 3p, 3g (0-3-0), 0gd (3-3)
4) Team B 1p, 1g (0-1-0), 0gd (1-1)
5) Team C 1p, 2g (0-1-1), -1gd (3-4)

Runtime: Giving incorrect answer when submitted on judge, but running correctly on sample test!

UVa 146 ID Codes Solution in C++

Use of next_permutation, which gives the lexicographical next permutation of the given array.

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

int main(){
	char a[51];
	while(gets(a)){
		if(a[0]=='#') break;
		else{
			if(next_permutation(a, a+strlen(a))) puts(a);
			else puts("No Successor");
		}
	}
	return 0;
}

Sample Input:

abaacb
cbbaa
#

Sample Output:

ababac
No Successor

Runtime: 0.009s

UVa 11340 Newspaper Solution in C++

Character mapping and increasing the count of money of every occurring character by fetching the value from the map ;).

#include<cstdio>
#include<map>
using namespace std;

int main(){
	long T; scanf("%d", &T);
	map<char, int> m;
	for(int t = 0; t<T; t++){
		int K; scanf("%d", &K);
		m.clear();
		int price;
		char c;
		for(int k = 0; k<K; k++){
			getchar(); c = getchar();
			scanf("%d", &price);
			m[c] = price;
			
		}
		int M; scanf("%d", &M);
		c = getchar();
		long count = 0;
		while((c = getchar())!=EOF)
			if(c!=' ' || c!='\n') count += m[c];
		printf("%0.2f$\n", count/100.0);
	}
	return 0;
}

Sample Input:

1
7
a 3
W 10
A 100
, 10
k 7
. 3
I 13
7
ACM International Collegiate Programming Contest (abbreviated
as ACM-ICPC or just ICPC) is an annual multi-tiered competition
among the universities of the world. The ICPC challenges students
to set ever higher standards of excellence for themselves
through competition that rewards team work, problem analysis,
and rapid software development.
From Wikipedia.

Sample Output:

3.74$

UVa 594 One Little, Two Little, Three Little Endians Solution in C++

Reversing the bytes takes a simple formula, and directly using bitset object. Can also be done without using bitset by doing x%2 in the if condition and x>>1 at the end of the loop.

#include<cstdio>
#include<bitset>

using namespace std;

long convert_endian(long x){
	bitset<32> b(x);
	long ret = 0;
	for (int j=0; j<32; j++) if (b[j]) ret |= 1<<(3-j/8)*8+(j%8);
	return ret;
}

int main(){
	long x;
	while(scanf("%ld", &x)==1) printf("%ld converts to %ld\n",
		x, convert_endian(x));
	return 0;
}

Sample Input:

123456789
-123456789
1
16777216
20034556

Sample Output:

123456789 converts to 365779719
-123456789 converts to -349002504
1 converts to 16777216
16777216 converts to 1
20034556 converts to -55365375