Coding Challenge Alpha (by AlgoRave DTU) Editorial

Given $$$n$$$ chocolates and $$$m$$$ students:

1. If $$$n$$$ is less than $$$m$$$, then there aren't enough chocolates for every student, so we will print $$$-1$$$.
2. If $$$n$$$ is equal to or greater than $$$m$$$, then every student will receive one chocolate each and the remainder will be returned to the school. The number of chocolates to be returned will be $$$n - m$$$.

#include<stdio.h>
 
using namespace std;
 
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    if(n<m) {
        printf("-1\n");
    }else {
        printf("%d\n",n-m);
    }
    
    return 0;
}

Let us first solve the problem assuming that only one of the two robots can move. To solve this subproblem, it is important to note that diagonal moves are possible. For example, if the robot has to move 5 steps to the left and 6 steps downwards, then it is optimal to move 5 steps diagonally (down and left) and one step down. Thus, it is clear that the total number of moves can be broken up into two parts: The diagonal moves and the non diagonal moves. Let X be the horizontal distance between the two robots, and Y be the vertical distance. Thus, the total number of steps that a robot has to move to reach the other robot will be: min(X, Y) + (max(X, Y) — min(X, Y)). Here, the first term corresponds to the diagonal moves, and the remaining terms corresponds to the non-diagonal moves. This simplifies to be max(X, Y). Now coming back to the orginal problem, where both robots can move. The number of steps will simply be max(X, Y) / 2 if max(X, Y) is even, or max(X, Y) / 2 + 1 if max(X, Y) is odd. This can be simply expressed as (max(X, Y) + 1) / 2.

int main() {
    int n, m, r1, c1, r2, c2;
    cin >> n >> m >> r1 >> c1 >> r2 >> c2;
    int dist = max(abs(r1 - r2), abs(c1 - c2));
    cout << (dist + 1) / 2;
}

While the problem may appear complex at first glance, it can be efficiently solved using a straightforward greedy method.

Both gangs have a common objective: maximizing their power. The key to achieving this lies in acquiring weapons with the highest strength. To do this, we simply sort the weapons based on their strength in descending order. As we iterate through the sorted weapons list, we allocate them to the nearest gang that still has available members. It's worth noting that if one gang is closer to a weapon but has exhausted its members, the other gang can rightfully claim it. The complexity is $$$n*m$$$ $$$log(n*m)$$$.

import java.util.*;

public class Solution{
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n = sc.nextInt(); int m = sc.nextInt();

        ArrayList<int []> weapons= new ArrayList<>();
        for (int i=0; i<n; i++){
            for (int j=0; j<m; j++){
                weapons.add(new int[] {sc.nextInt(), i, j});
            }
        }

        Collections.sort(weapons, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return Integer.compare(o2[0], o1[0]);
            }
        });

        int x1= sc.nextInt(); int y1= sc.nextInt();

        int x2= sc.nextInt(); int y2= sc.nextInt();

        int k1= sc.nextInt(); int k2= sc.nextInt();

        long ans=0;
        for (int i=0; i<n*m && (k1>0 || k2>0); i++){
            int arr[]=weapons.get(i);
            int dist1= Math.abs(arr[1]-x1)+Math.abs(arr[2]-y1);
            int dist2= Math.abs(arr[1]-x2)+Math.abs(arr[2]-y2);
            if (k1!=0 && (k2==0 || dist1<dist2)){
                ans+=arr[0];
                k1--;
            }
            else {
                ans-=arr[0];
                k2--;
            }
        }

        if (ans>0) System.out.println(1);
        else if (ans<0) System.out.println(2);
        else System.out.println(0);
    }
} 

When we are looking at the bookshelf from the right hand side we will never see a book if a book of greater or equal size is already there in the right subarray. Consider 'l' to be the length of the increasing subsequence of heights, then we can break the problem into 2 cases: 1. When the subseqence does'nt end at the 0th index, then he can add books of greater height than the last book of the subsequence and the answer will be (l+k) books. 2. When the subsequence ends at the 0th index 2.1. When the sum of books that can be inserted between consecutive books of the subsequence is >=k, the answer is (l+k) books 2.2 When the sum of books that can be inserted between consecutive books of the subsequence is <k, then he can sacrifice the last book of the subsequence and add books of height greater than the 2nd largest book of the subsequence, the answer is (l+k-1) books.

import java.util.*;
import java.lang.*;
import java.io.*;
 
public class Solution
{
	public static void main (String[] args) throws java.lang.Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        
        int t = Integer.parseInt(line.split(" ")[0]);
        while(t>0){
            t--;
            String line1 = br.readLine();
            
            int n = Integer.parseInt(line1.split(" ")[0]);
            long k = Long.parseLong(line1.split(" ")[1]);
 
            int[] arr = new int[n];
            String str = br.readLine();
            String[] items = str.split(" ");
 
            for(int j = 0; j < n; j++){
                arr[j]=Integer.parseInt(items[j]);
            }
            
            if(n==1){
                System.out.println(1);
                continue;
            }
 
            int prevGreatest=arr[n-1];
            long len=1;
            long totaldifferences=0;
 
            for(int i=n-2;i>=0;i--){
                if(arr[i]>prevGreatest){
                    totaldifferences+=(long)(arr[i]-prevGreatest-1);
                    prevGreatest=arr[i];
                    len++;
                }
            }
 
            boolean flag=true;
 
            for(int i=1;i<n;i++){
                if(arr[i]==prevGreatest){
                    flag=false;
                    break;
                }
            }
 
            if(!flag){
                len+=k;
            }else{
                if(totaldifferences>=k){
                    len+=k;
                }else{
                    len+=k-1;
                }
            }
 
            System.out.println(len);
            
            
        }
	}
}

It is obvious that there are $$$n^2$$$ possible points available i.e., all $$$(x_i, y_j)$$$ pairs. And, we can observe that with the increase in radius, the number of points will either increase or remain the same, so the function (number of points inside) is monotonous with the radius. Hence, we can do a binary search on the radius.

Now, we just have to calculate the amount of points inside the circle for a given radius. Let's observe the function: $$$x^2 + y^2 = r^2$$$. In this, as $$$x$$$ increases, $$$y$$$ decreases. So, if we sort the arrays by squared values, then we can use two pointers to calculate the count, which takes linear time.

Hence the complexity: $$$\mathcal{O}(n \cdot \log{R})$$$

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

template <typename T> using pbds = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define int int64_t
#define endl '\n'
#define sz(v) ((int) v.size())
#define all(v) v.begin(), v.end()
#define vi vector<int>
#define pii pair<int, int>
#define inf 2e18
#define ld long double

int max(int x, int y) { return x > y ? x : y; }
int min(int x, int y) { return x < y ? x : y; }

const int N = 1e6 + 7;
int x[N], y[N];

void solve() {
  int n, k;
  cin >> n >> k;
  for(int i = 0; i < n; i++) {
    cin >> x[i];
  }
  for(int i = 0; i < n; i++) {
    cin >> y[i];
  }
  sort(x, x + n, [&](auto& x, auto& y) {
    return abs(x) < abs(y);
  });
  sort(y, y + n, [&](auto& x, auto& y) {
    return abs(x) < abs(y);
  });
  ld low = 0, high = 2e9, eps = 1e-9;
  auto check = [&](ld r) {
    int j = n - 1, ans = 0;
    for(int i = 0; i < n; i++) {
      while(j >= 0 && r * r - x[i] * x[i] - y[j] * y[j] < eps * eps) {
        j--;
      }
      ans += j + 1;
    }
    return ans >= k;
  };
  while(high - low > eps) {
    ld mid = (high + low) / 2;
    if(check(mid)) high = mid;
    else low = mid;
  }
  ld ans = check(low) ? low : high;
  cout << fixed << setprecision(9) << ans;
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  #ifdef VRINTLE
    freopen("./tests/test_0.txt", "r", stdin);
    freopen("./out.txt", "w", stdout);
    freopen("./err.txt", "w", stderr);
  #endif
  int t = 1;
  cin >> t;
  while(t--) {
    solve();
    cout << endl;
  }
  return 0;
}