IMPRS - CRACK-A-CODE 2.0 Editorial

Practice
CAC2.0 Contest

Author: Priyanshu Damodhare
Tester: Mayuresh Patle
Editorialist: Priyanshu Damodhare

DIFFICULTY:

SIMPLE

PREREQUISITES:

Vectors, Pairs.

PROBLEM:

Given N coordinates on a 2D x-y plane, to find K coordinates closest to the origin(0,0) and calculate sum of all x and y coordinates.
If two points are at same distance, consider the one with smallest x,y co-ordinate sum first.

QUICK EXPLANATION:

Create a vector of pair. First element of pair will be distance from origin i.e. x^2 + y^2, and second element of the pair will be sum of x and y i.e. x+y. Then simply sort the vector and add second element(x+y) of all first K pairs.

EXPLANATION:

This is the simplest and straight forward solution for this problem using some STLs.
First take input of T i.e. Number of testcases
For each testcase, take input of N and K, number of coordinates and number of points to be found respectively.
Now define a vector of pair.
By applying a loop that runs N times, take input of the coordinates i.e x and y and make a pair with first element of pair as the distance from origin(distance from origin is calculated as root(x^2 + y^2)) and second element as the sum of x and y (x+y). Now push this pair in the vector.
After pushing all pairs into the vector, sort the vector.
Now using a loop calculate sum of second element of the pair of first K pairs in the vector.
print the sum

SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
#define fi(asgduyas,n) for(int i=asgduyas;i<n;i++)
#define fj(asgduyas,n) for(int j=asgduyas;j<n;j++)
#define isEven(n) (!(n & 1))
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define pi vector<int,int>
#define all(a) (a).begin(),(a).end()
#define mod  1000000007
#define pmod 998244353
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll l,r,t,n,m;
string s;
cin>>t;
while(t--)
{
	ll ans=0;
	cin>>n>>m;
	
	vector<pair<ll,ll>> v;
	
	fi(0,n)
	{
		cin>>l>>r;
		v.pb(mp((pow(l,2) + pow(r,2)), l+r) );
		
	}
	ll c=0, f=0;
	sort(all(v));
	for(int i=0; i<m; i++)ans+= v[i].second;

	cout<<ans<<"\n";
}
}
Tester's Solution
for _ in range(int(input())):
    n,k=map(int,input().split())
    l=[]
    for _ in range(n):
	    x,y=map(int,input().split())
	    l.append(((x*x+y*y)**.5,x+y))
    l.sort()
    print(sum(map(lambda x:x[1],l[:k])))
1 Like