Forming Groups (Problem F, The 2024 ICPC Asia Pacific Championship, 2024)
Time limit: 5 sec
Author: Jonathan Irvin Gunawan

# Problem Statement

There are $n$ students, numbered from $1$ to $n$, who need to form groups for the upcoming hackathon. You are student $1$, the captain of the students. Student $i$ has skill level $a_i$.

Students $2$ to $n$ are standing in a line from left to right in order. You can choose to stand in between any two students, to the left of student $2$, or to the right of student $n$. You cannot change the order of the $n - 1$ students.

You can also choose the number of groups $k$ ($k > 1$ and $k$ must be a divisor of $n$) to participate in the hackathon. The groups will be numbered from $1$ to $k$. After you have chosen your position and the value of $k$, the students will be grouped as follows:

- The first student from the left will be assigned to group $1$.
- The second student from the left will be assigned to group $2$.
- $\dots$
- The $k$-th student from the left will be assigned to group $k$.
- The $(k + 1)$-th student from the left will be assigned to group $1$.
- The $(k + 2)$-th student from the left will be assigned to group $2$.
- $\dots$
- The $n$-th student from the left will be assigned to group $k$.

Formally, for each $j$ ($1 \le j \le k$) and for each $i$ ($0 \le i < n/k$), the $(i \times k + j)$-th student from the left will be assigned to group $j$. It can be shown that each student will be assigned to exactly one group and all the groups have the same number of students.

The skill level of a group is the sum of the skill levels of the students inside the group. By choosing where you stand as well as the number of groups $k$ optimally, you want to minimize the ratio $x_{max}/x_{min}$ where

- $x_{max}$ is the skill level of the group with the largest skill level, and
- $x_{min}$ is the skill level of the group with the smallest skill level.

# Input

The first line of input contains one integer $t$ ($1 \le t \le 100\ 000$) representing the number of test cases. After that, $t$ test cases follow. Each of them is presented as follows.

The first line of a test case contains two integers $n$ and $a_1$ ($2 \le n \le 10^6;\ 1 \le a_1 \le 1000$). The next line contains $n - 1$ integers $a_2, a_3, \dots, a_n$ ($1 \le a_i \le 1000$ for all $i$).

The sum of $n$ across all test cases in one input file does not exceed $10^6$.

# Output

For each test case, output one line containing two positive integers $p$ and $q$ such that the minimum ratio is $p/q$. The fraction $p/q$ should be irreducible. In other words, $p$ and $q$ should be coprime.

# Sample Input #1
```
2
4 1
2
3
10
4 3
```
# Sample Output #1
```
1 1
10 3
```
*Explanation for the sample input/output #1*

In the first test case, by standing between students $2$ and $3$ (or between students $3$ and $4$) and choosing $k = 2$, group $1$ will have the skill level $2 + 1$ and group $2$ will have the skill level $1 + 2$, thus the ratio is $1/1$.

In the second test case, the only choice for the value of $k$ is $3$.

Sample inputs:
2
4 1
2 1 2
3 10
4 3

Sample outputs:
1 1
10 3

# Solution Analysis
Analysis author: Jonathan Irvin Gunawan

For a fixed value of $k$, we can compute the minimum ratio by initially assuming that student 1 is standing on the leftmost position. We then try to shift student 1 one position to the right each time, while keeping track of the sum of skill levels of each group, and maintaining a data structure to keep track of the minimum and maximum sum. Each shift only modifies the sum of skill levels of two groups. We can use a multiset data structure to support each shift in $O(\log n)$ time. After each shift, we compute the ratio between the maximum and minimum sum.

Trying all factors of $n$ as the value of $k$ is too slow. An optimization is to observe that for a fixed arrangement of students, having $k$ groups is better than having $2k$ groups. This is because by pairing $2k$ groups and combining each pair into $k$ groups, the maximum sum is less than doubled, while the minimum sum is more than doubled, which reduces the ratio. A similar argument can be applied for any multiples of $k$ as well.

Therefore, we can try only prime factors of $n$ as a value of $k$. For $n \leq 10^6$, there are at most 7 prime factors. Therefore, this solution runs in $7 \times O(n \log n)$ time.

Special judge (C++ scorer):
/**
 * Default validator from https://github.com/Kattis/problemtools
 * Modified (as small as possible) to tcframe format by jonathanirvings.
 */

#include <fstream>
#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cmath>
#include <cstdarg>

std::ifstream judgein, judgeans, conans;
FILE *judgemessage = NULL;
FILE *diffpos = NULL;
int judgeans_pos, con_pos;
int judgeans_line, con_line;

void ac() {
  puts("AC");
  exit(0); 
}

void wa() {
  puts("WA");
  exit(0);
}

void wrong_answer(const char *err, ...) {
  wa();
}

void judge_error(const char *err, ...) {
  va_list pvar;
  va_start(pvar, err);
  // If judgemessage hasn't been set up yet, write error to stderr
  if (!judgemessage) judgemessage = stderr;
  vfprintf(judgemessage, err, pvar);
  fprintf(judgemessage, "\n");
  assert(!"Judge Error");
}

bool isfloat(const char *s, double &val) {
  char trash[20];
  double v;
  if (sscanf(s, "%lf%10s", &v, trash) != 1) return false;
  val = v;
  return true;
}

template <typename Stream>
void openfile(Stream &stream, const char *file, const char *whoami) {
  stream.open(file);
  if (stream.fail()) {
    judge_error("%s: failed to open %s\n", whoami, file);
  }
}

FILE *openfeedback(const char *feedbackdir, const char *feedback, const char *whoami) {
  std::string path = std::string(feedbackdir) + "/" + std::string(feedback);
  FILE *res = fopen(path.c_str(), "w");
  if (!res) {
    judge_error("%s: failed to open %s for writing", whoami, path.c_str());
  }
  return res;
}

const char *USAGE = "Usage: %s judge_in judge_ans contestant_ans";

int main(int argc, char **argv) {
  if(argc < 4) {
    judge_error(USAGE, argv[0]);
  }
  openfile(judgein, argv[1], argv[0]);
  openfile(judgeans, argv[2], argv[0]);
  openfile(conans, argv[3], argv[0]);

  bool case_sensitive = false;
  bool space_change_sensitive = false;
  bool use_floats = false;
  double float_abs_tol = -1;
  double float_rel_tol = -1;

  for (int a = 4; a < argc; ++a) {
    if        (!strcmp(argv[a], "case_sensitive")) {
      case_sensitive = true;
    } else if (!strcmp(argv[a], "space_change_sensitive")) {
      space_change_sensitive = true;
    } else if (!strcmp(argv[a], "float_absolute_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_abs_tol))
        judge_error(USAGE, argv[0]);
      ++a;
    } else if (!strcmp(argv[a], "float_relative_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_rel_tol))
        judge_error(USAGE, argv[0]);
      ++a;
    } else if (!strcmp(argv[a], "float_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_rel_tol))
        judge_error(USAGE, argv[0]);
      float_abs_tol = float_rel_tol;
      ++a;
    } else {
      judge_error(USAGE, argv[0]);
    }
  }
  use_floats = float_abs_tol >= 0 || float_rel_tol >= 0;

  judgeans_pos = con_pos;
  judgeans_line = con_line = 1;
   
  std::string judge, team;
  char trash[20];
  while (true) {
    // Space!  Can't live with it, can't live without it...
    while (isspace(judgeans.peek())) {
      char c = (char)judgeans.get();
      if (space_change_sensitive) {
        int d = conans.get();
        if (c != d) {
          wrong_answer("Space change error: got %d expected %d", d, c);
        }
        if (d == '\n') ++con_line;
        ++con_pos;
      }
      if (c == '\n') ++judgeans_line;
      ++judgeans_pos;
    }
    while (isspace(conans.peek())) {
      char d = (char)conans.get();
      if (space_change_sensitive) {
        wrong_answer("Space change error: judge out of space, got %d from team", d);
      }
      if (d == '\n') ++con_line;
      ++con_pos;
    }

    if (!(judgeans >> judge))
      break;

    if (!(conans >> team)) {
      wrong_answer("User EOF while judge had more output\n(Next judge token: %s)", judge.c_str());
    }
     
    double jval, tval;
    if (use_floats && isfloat(judge.c_str(), jval)) {
      if (!isfloat(team.c_str(), tval)) {
        wrong_answer("Expected float, got: %s", team.c_str());
      }
      if(!(fabs(jval - tval) <= float_abs_tol) && 
         !(fabs(jval - tval) <= float_rel_tol*fabs(jval))) {
        wrong_answer("Too large difference.\n Judge: %s\n Team: %s\n Difference: %le\n (abs tol %le rel tol %le)", 
               judge.c_str(), team.c_str(), jval-tval, float_abs_tol, float_rel_tol);
      }
    } else if (case_sensitive) {
      if (strcmp(judge.c_str(), team.c_str()) != 0) {
        wrong_answer("String tokens mismatch\nJudge: \"%s\"\nTeam: \"%s\"", judge.c_str(), team.c_str());
      }
    } else {
      if(strcasecmp(judge.c_str(), team.c_str()) != 0) {
        wrong_answer("String tokens mismatch\nJudge: \"%s\"\nTeam: \"%s\"", judge.c_str(), team.c_str());
      }
    }
    judgeans_pos += judge.length();
    con_pos += team.length();
  }

  if (conans >> team) {
    wrong_answer("Trailing output:\n%s", team.c_str());
  }

  ac();
}