Skip to content

Instantly share code, notes, and snippets.

@Tokiyomi
Last active October 21, 2022 21:48
Show Gist options
  • Save Tokiyomi/edd031f2d69835a36b53f14ca0c01a3f to your computer and use it in GitHub Desktop.
Save Tokiyomi/edd031f2d69835a36b53f14ca0c01a3f to your computer and use it in GitHub Desktop.
Equal sum solution in C#
// Code Jam Individual Problem - Equal Sum - Carolina Garma
// Prev knowledge: binary representation, partitions
using System;
using System.Collections.Generic;
using System.Linq;
namespace GoogleJam
{
class EqualSum
{
static List<long> powers_of_two(int N)
/*
This function generates my proposed tactical N sets of numbers made of powers of 2
and the remaining N-30 numbers will be the last N numbers before 10**9 inclusive.
As N is always 100, this fuction is always performed without problems
*/
{
var A = new List<long>();
for (double i = 0; i < 30; i++) // Add 30 tattical numbers
{
A.Add(Convert.ToInt64(Math.Pow(2, i)));
}
for (int i = 0; i < N-30; i++) // Add N-30 ramaining numbers (they can be whatever)
{
A.Add(Convert.ToInt64((Math.Pow(10, 9)))-i);
}
return A;
}
static List<long> solve_sum(List<long> A, List<long> B)
/*
This function implements a greedy approach to minimize the sum difference
among two sets A and B
*/
{
// Join A and B into a new list C
var C = new List<long>();
C.AddRange(A);
C.AddRange(B);
// Sort C in descending order for a faster search
C = C.OrderByDescending(i => i).ToList();
long a_sum = 0L; // initialize a_sum
long b_sum = 0L; // initialize b_sum
var equal_sum_set = new List<long>(); // A set containing N_1 numbers with equal sum as the N_2 numbers
foreach(var item in C) // Minimize difference and distribute numbers
{
if (a_sum > b_sum) {
b_sum += item;
equal_sum_set.Add(item);
} else {
a_sum += item;
}
}
return equal_sum_set; // Return resulting set with equal_sum, sum diff is 0 now
}
static void Main(string[] args)
{
long T = Convert.ToInt64(Console.ReadLine()); // Read # of Cases
for (int i = 0; i < T; i++){
int N = Convert.ToInt32(Console.ReadLine()); // Read N
if (N == -1) { // if N==-1, end program
break;
}
// Generate our A set of powers of two
var A = powers_of_two(N);
// Print A set in terminal
foreach(var item in A)
{
Console.Write(item + " ");
}
Console.WriteLine();
// Read B set from terminal
var B_string = Console.ReadLine();
List<long> B = B_string.Split(' ').ToList().Select(x => Convert.ToInt64(x)).ToList();
// Solve Case
var C = solve_sum(A,B);
// Print result
foreach(var item in C)
{
Console.Write(item + " ");
}
Console.WriteLine();
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment