Thanks for participating, hope you enjoyed the problems! Implementations for the problems are chosen randomly among testers, and I made some changes to their codes (for example, deleted meaningless comment lines). Please do not hesitate to provide feedback in the comments, so I can improve in setting problems next time.

**UPD**: Sorry but there is a checker bug in problem E. All submissions of problem E will be rejudged soon.

**UPD2:** Rejudge done, the round remains rated.

**Statistics**

Number of FST for rated participants:

Problem A: $$$29$$$

Problem B: $$$90$$$

Problem C: $$$12$$$

Problem D1: $$$4$$$

Problem D2: $$$0$$$

Problem E: $$$6$$$

Number of AK: $$$22$$$

Number of clarifications: $$$85$$$

**Hint**

When is the lexicographically smallest permutation of $$$S$$$ (i.e. the sorted string) not the answer?

**Solution**

If there are no occurrences of `a`

, `b`

or `c`

in $$$S$$$, sort $$$S$$$ and output it.

Else, if $$$T \ne$$$ `abc`

, sort $$$S$$$ and output it.

Else, output all `a`

, then all `c`

, then all `b`

, then the rest of the string sorted.

**Implementation (C++, I_Love_YrNameCouldBeHere)**

```
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
int main() {
int T;
cin >> T;
while(T--) {
string s, t;
cin >> s >> t;
sort(all(s));
vector<int> cnt(26, 0);
for(auto x: s)cnt[x - 'a']++;
if(t != "abc" || !cnt[0] || !cnt[1] || !cnt[2])cout << s << "\n";
else{
while(cnt[0]--)cout<<"a";
while(cnt[2]--)cout<<"c";
while(cnt[1]--)cout<<"b";
for(int i = 3;i < 26; ++i){
while(cnt[i]--)cout<<char('a' + i);
}
cout << "\n";
}
}
}
```

**Fun fact**

Originally, the author and two testers' solutions are all wrong, but we didn't notice until the third tester submitted the real correct solution.

**Hint**

There must exist a solution for $$$c=1$$$ under the given constraints.

**Solution**

Key observation: there always exists a solution with $$$c = 1$$$ under the given constraints. We set $$$n \ge 10$$$ because there is no solution when $$$1 \le n \le 5$$$ or $$$n = 7$$$.

Solution 1: Brute force from $$$a = 2, 3, 4, \dots$$$ and calculate the value of $$$b$$$ ($$$b = n - a - 1$$$), then check whether $$$gcd(a, b) = 1$$$. It works, because you will find a prime number $$$p \le 29$$$ such that $$$n-1$$$ does not divide $$$p$$$.

Solution 2: Randomly choose $$$a$$$ and calculate $$$b$$$ ($$$b = n - a - 1$$$). Repeating that for enough times will eventually get you a pair of ($$$a, b$$$) such that $$$gcd(a, b) = 1$$$.

Solution 3: Constructive solution.

When $$$n \equiv 0 \pmod 2$$$, output ($$$n-3, 2, 1$$$).

When $$$n \equiv 1 \pmod 4$$$, output ($$$\left \lfloor \frac{n}{2} \right \rfloor -1, \left \lfloor \frac{n}{2} \right \rfloor +1, 1$$$).

When $$$n \equiv 3 \pmod 4$$$, output ($$$\left \lfloor \frac{n}{2} \right \rfloor -2, \left \lfloor \frac{n}{2} \right \rfloor +2, 1$$$).

**Implementation (Solution 1, Java, SecondThread)**

```
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
import java.util.Scanner;
public class B {
public static void main(String[] args) {
Scanner fs = new Scanner(System.in);
int T=fs.nextInt();
for (int tt=0; tt<T; tt++) {
int n=fs.nextInt();
for (int target=2; true; target++) {
if (gcd(n-1-target, target)!=1)
continue;
System.out.println(n-1-target+" "+target+" "+1);
if (n-1-target<=1) throw null;
break;
}
}
}
static int gcd(int a, int b) {
return b==0?a:gcd(b, a%b);
}
static void sort(int[] a) {
ArrayList<Integer> l=new ArrayList<>();
for (int i:a) l.add(i);
Collections.sort(l);
for (int i=0; i<a.length; i++) a[i]=l.get(i);
}
}
```

**Implementation (Solution 2, C++, dbsic211)**

```
#include <bits/stdc++.h>
using namespace std;
mt19937 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
void solve(int tc) {
int n;
cin >> n;
while(1) {
int k = uniform_int_distribution<int>(2, n-2)(rng);
int l = n-k-1;
if(k != l && k != 1 && l != 1 && gcd(k, l) == 1) {
cout << k << ' ' << l << ' ' << 1 << endl;
break;
}
}
}
int main() {
int t;
cin >> t;
for(int i=1; i<=t; i++) {
solve(i);
}
}
```

**Implementation (Solution 3, C++, anthony123)**

```
#include <bits/stdc++.h>
using namespace std;
void solve(){
int n;
cin>>n;
if (n%2==0) cout<<"2 "<<(n-1)-2<<" 1\n";
else {
int cur=(n-1)/2;
if (cur%2==0) cout<<cur-1<<" "<<cur+1<<" "<<1<<endl;
else cout<<cur-2<<" "<<cur+2<<" "<<1<<endl;
}
}
signed main(){
int t;
cin>>t;
while (t--) solve();
}
```

1617C - Paprika and Permutation

**Hint 1**

For any two positive integers $$$x$$$, $$$y$$$ that satisfy $$$x \ge y$$$, what is the maximum value of $$$x \bmod y$$$?

**Hint 2**

Consider the following input: $$$n = 4$$$, $$$a = [3, 3, 10, 10]$$$. Sometimes, we don't need to do anything to some $$$a_i$$$. When do we have to make operations, and when do we not have to?

**Solution**

Key observation: $$$x \bmod y < \frac{x}{2}$$$ if $$$x \ge y$$$, and $$$x \bmod y = x$$$ if $$$x < y$$$.

Notice that the bigger the $$$x$$$, the bigger the range of values that can be obtained after one $$$\bmod$$$ operation. So, intuitively, we want to assign smaller $$$a_i$$$ to smaller numbers in the resulting permutation.

However, if $$$a_i$$$ satisfies $$$1 \le a_i \le n$$$, we can just leave it there and use it in the resulting permutation (if multiple $$$a_i$$$ satisfy $$$1 \le a_i \le n$$$ and have the same value, just choose one). Let's suppose in the optimal solution, we change $$$x$$$ to $$$y$$$ and change $$$z$$$ to $$$x$$$ for some $$$z > x > y$$$ ($$$x$$$, $$$y$$$, $$$z$$$ are values, not indices). Then changing $$$x$$$ to $$$x$$$ (i.e. doing nothing) and changing $$$z$$$ to $$$y$$$ uses $$$1$$$ less operation. And, if it is possible to change $$$z$$$ to $$$x$$$, then it must be possible to change $$$z$$$ to $$$y$$$. However, if it is not possible to change $$$z$$$ to $$$x$$$, it might still be possible to change $$$z$$$ to $$$y$$$.

Therefore, the solution is as follows: Sort the array. For each element $$$i$$$ in the sorted array:

If $$$1 \le a_i \le n$$$ and it is the first occurrence of element with value $$$a_i$$$, leave it there.

Else, let the current least unassigned value in the resulting permutation be $$$m$$$, if $$$m < \frac{a_i}{2}$$$, we can assign the current element to value $$$m$$$ and add the number of operations by $$$1$$$. Else, output $$$-1$$$ directly.

The solution works in $$$O(n \log n)$$$.

**Implementation (C++, physics0523)**

```
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while(t>0){
t--;
int n;
cin >> n;
set<int> st;
for(int i=1;i<=n;i++){st.insert(i);}
vector<int> rem;
for(int i=0;i<n;i++){
int v;
cin >> v;
if(st.find(v)!=st.end()){st.erase(v);}
else{rem.push_back(v);}
}
sort(rem.begin(),rem.end());
reverse(rem.begin(),rem.end());
int pt=0;
bool err=false;
for(auto &nx : rem){
auto it=st.end();
it--;
int ctg=(*it);
if(ctg>(nx-1)/2){err=true;break;}
st.erase(it);
}
if(err){cout << "-1\n";}
else{cout << rem.size() << '\n';}
}
return 0;
}
```

1617D1 - Too Many Impostors (easy version)

**Hint 1**

The weird constraint, $$$\frac{n}{3} < k < \frac{2n}{3}$$$, is crucial.

**Hint 2**

If you know the index of one crewmate and one impostor, how to find the roles of other $$$n-2$$$ players in exactly $$$n-2$$$ queries?

**Hint 3**

Query players ($$$1, 2, 3$$$), ($$$2, 3, 4$$$), $$$\dots$$$, ($$$n-1, n, 1$$$), ($$$n, 1, 2$$$). After that, you can surely find out the index of one crewmate and one impostor. Try to find out how.

**Solution**

Key observation: if result of query ($$$a, b, c$$$) $$$\ne$$$ result of query ($$$b, c, d$$$), since $$$b$$$ and $$$c$$$ are common, players $$$a$$$ and $$$d$$$ have different roles. Additionally, if result of query ($$$a, b, c$$$) = $$$1$$$ then player $$$a$$$ is a crewmate (and player $$$d$$$ is an impostor), vice versa.

The first step is to query players ($$$1, 2, 3$$$), ($$$2, 3, 4$$$), $$$\dots$$$, ($$$n-1, n, 1$$$), ($$$n, 1, 2$$$).

If the results of any two adjacent queries (or queries ($$$1, 2, 3$$$) and ($$$n, 1, 2$$$)) are different, we instantly know the roles of the two players that are only included in one query — one is a crewmate, one is an impostor. Since the number of impostors $$$k$$$ and crewmates $$$n-k$$$ satisfy $$$k > \frac{n}{3}$$$ and $$$n - k > \frac{n}{3}$$$, there must be one pair of adjacent queries that are different.

After we know one crewmate and one impostor (let's call them $$$a$$$, $$$d$$$), we can query these two players with each one of the rest of the players. If a query ($$$a, d, x$$$) ($$$1 \le x \le n$$$, $$$x \ne a$$$ and $$$x \ne d$$$) returns $$$0$$$, player $$$x$$$ is an impostor, else player $$$x$$$ is a crewmate.

In total, $$$2n-2$$$ queries are used.

**Implementation (C++, dbsic211)**

```
#include <bits/stdc++.h>
using namespace std;
void solve() {
int N;
cin >> N;
int res[N];
for(int i=0; i<N; i++) {
cout << "? " << i + 1 << " " << (i+1) % N + 1 << " " << (i+2) % N + 1 << endl;
cin >> res[i];
}
vector<int> imp;
for(int i=0; i<N; i++) {
if(res[i] != res[(i+1) % N]) {
if(res[i] == 0) imp.push_back(i + 1);
else imp.push_back((i+3) % N + 1);
for(int j=0; j<N; j++) {
if(j != i && j != (i+3) % N) {
cout << "? " << i + 1 << " " << (i+3) % N + 1 << " " << j + 1 << endl;
int r;
cin >> r;
if(r == 0) imp.push_back(j + 1);
}
}
break;
}
}
cout << "! " << imp.size();
for(int x : imp) cout << " " << x;
cout << endl;
}
int main() {
int T;
cin >> T;
for(int i=1; i<=T; i++) {
solve();
}
}
```

1617D2 - Too Many Impostors (hard version)

Thanks must be given to arvindf232 and generic_placeholder_name for the solution.

**Hint 1**

Aim to find an impostor and a crewmate's index in $$$\frac{n}{3} + c$$$ queries, with $$$c$$$ being a small constant.

**Hint 2**

Consider splitting the $$$n$$$ players into groups of $$$3$$$ (and query each group) in order to reach the goal in Hint 1. What is special about the results of the $$$\frac{n}{3}$$$ queries?

**Solution (Step 1)**

Firstly query ($$$1, 2, 3$$$), ($$$4, 5, 6$$$), $$$\dots$$$, ($$$n-2, n-1, n$$$). Due to the constraint $$$\frac{n}{3} < k < \frac{2n}{3}$$$, among the results of these $$$\frac{n}{3}$$$ queries, there must be at least one $$$0$$$ and one $$$1$$$. Now, let's call a tuple ($$$a, b, c$$$) that returns $$$0$$$ a $$$0$$$-majority tuple, and vice versa.

From the easy version, notice that finding one crewmate and one impostor is very helpful in determining the roles of the remaining players. Let's make use of the above observation, and pick one adjacent $$$0$$$-majority tuple and $$$1$$$-majority tuple.

Let's say we picked ($$$i, i+1, i+2$$$) and ($$$i+3, i+4, i+5$$$). Then, we query ($$$i+1, i+2, i+3$$$) and ($$$i+2, i+3, i+4$$$). Among the four queries ($$$i, i+1, i+2$$$), ($$$i+1, i+2, i+3$$$), ($$$i+2, i+3, i+4$$$), ($$$i+3, i+4, i+5$$$), there must be a pair of adjacent queries with different results. From the easy version, we can directly find the index of an impostor and a crewmate.

In all the above cases, we end up knowing an impostor and a crewmate using $$$\frac{n}{3} + 2$$$ queries, including the first step.

**Hint 3**

You have the index of an impostor and a crewmate now, and around $$$\frac{2n}{3}$$$ queries left.

Consider using at most $$$2$$$ queries to find out roles of each player in each group of $$$3$$$ from Step 1, which should add up to $$$\frac{2n}{3}$$$ queries.

Make use of the information you know about each group (whether it is $$$0$$$-majority or $$$1$$$-majority).

**Hint 4**

Assume a tuple (group of $$$3$$$) is $$$0$$$-majority. There are $$$4$$$ possibilities of roles of the $$$3$$$ players in the tuple, which are:

impostor, impostor, impostor

crewmate, impostor, impostor (and its permutations)

In each query, reduce half of the possibilities.

**Solution (Step 2)**

It remains to figure out how we can find the roles of the remaining players using $$$\frac{2n}{3}$$$ queries. For each tuple ($$$i, i+1, i+2$$$) queried in the first step, let's assume the tuple is $$$0$$$-majority (because the other case can be solved similarly). Then, there are only four possibilities:

All players $$$i$$$, $$$i+1$$$, $$$i+2$$$ are impostors.

Player $$$i$$$ is a crewmate, players $$$i+1$$$, $$$i+2$$$ are impostors.

Player $$$i+1$$$ is a crewmate, players $$$i$$$, $$$i+2$$$ are impostors.

Player $$$i+2$$$ is a crewmate, players $$$i$$$, $$$i+1$$$ are impostors.

Earlier, we found the index of a crewmate and an impostor, let the index of the crewmate be $$$a$$$ and the impostor be $$$b$$$.

If the tuple ($$$i, i+1, a$$$) is $$$1$$$-majority, either player $$$i$$$ or player $$$i+1$$$ is a crewmate. So, we reduced the number of possibilities to $$$2$$$. To check which player is the crewmate, query it with $$$a$$$ and $$$b$$$ like we did in the easy version.

Else, either there are no crewmates or player $$$i+2$$$ is a crewmate. So, we reduced the number of possibilities to $$$2$$$. To check the role of player $$$i+2$$$, query it with $$$a$$$ and $$$b$$$ like we did in the easy version.

In both cases, we use $$$2$$$ queries for each initial tuple ($$$i, i+1, i+2$$$). So, we used $$$n + 2$$$ queries in total, but we gave you a bit more, in case you used some more queries to find a crewmate and an impostor.

There is one corner case we should handle: if the tuple ($$$i, i+1, i+2$$$) contains $$$a$$$ or $$$b$$$, we can just naively query for each unknown role in the tuple, since we won't use more than $$$2$$$ queries anyway.

**Implementation (C++, dbsic211)**

```
#include <bits/stdc++.h>
using namespace std;
int query(int a, int b, int c) {
cout << "? " << a << ' ' << b << ' ' << c << endl;
int r; cin >> r;
return r;
}
void solve(int tc) {
int n; cin >> n;
int a[n+1], role[n+1];
for(int i=1; i+2<=n; i+=3) a[i] = query(i, i+1, i+2);
int imp, crew;
for(int i=1; i<=n; i++) role[i] = -1;
for(int i=1; i+5<=n; i+=3) {
if(a[i] != a[i+3]) {
a[i+1] = query(i+1, i+2, i+3), a[i+2] = query(i+2, i+3, i+4);
for(int j=i; j<i+3; j++) {
if(a[j] != a[j+1]) {
if(a[j] == 0) {
imp = j, crew = j+3;
role[j] = 0, role[j+3] = 1;
}
else {
imp = j+3, crew = j;
role[j+3] = 0, role[j] = 1;
}
}
}
break;
}
}
for(int i=1; i+2<=n; i+=3) {
if(i == imp || i+1 == imp || i+2 == imp || i == crew || i+1 == crew || i+2 == crew) {
for(int j=i; j<i+3; j++) {
if(role[j] == -1) {
role[j] = query(imp, crew, j);
}
}
}
else if(a[i] == 0) {
if(query(i, i+1, crew) == 1) {
if(query(i, imp, crew) == 0) role[i] = 0, role[i+1] = 1;
else role[i] = 1, role[i+1] = 0;
role[i+2] = 0;
}
else {
role[i] = role[i+1] = 0;
role[i+2] = query(i+2, imp, crew);
}
}
else {
if(query(i, i+1, imp) == 0) {
if(query(i, imp, crew) == 0) role[i] = 0, role[i+1] = 1;
else role[i] = 1, role[i+1] = 0;
role[i+2] = 1;
}
else {
role[i] = role[i+1] = 1;
role[i+2] = query(i+2, imp, crew);
}
}
}
cout << "! ";
queue<int> q;
for(int i=1; i<=n; i++) if(role[i] == 0) q.push(i);
cout << q.size();
while(q.size()) {
cout << " " << q.front();
q.pop();
}
cout << endl;
}
int main() {
int T; cin >> T;
for(int i=1; i<=T; i++) solve(i);
}
```

**Hint 1**

Translate the problem into a graph problem. What feature of the graph is it asking about?

**Hint 2**

Draw out the graph, for $$$a_i \le 10$$$. What special property does the graph have?

**Hint 3**

Any specific algorithm to solve the problem (in Hint 1)?

**Solution (Step 1)**

In graph terms, the problem is as follows: in a graph with infinite nodes, two nodes $$$x$$$ and $$$y$$$ are connected if $$$x + y = 2^k$$$ for some $$$k \ge 0$$$. Among $$$n$$$ special nodes, find the pair of nodes ($$$i, j$$$) with maximum shortest distance.

Here comes the key observation: For any $$$i \ge 1$$$, there exists only one $$$j$$$ ($$$0 \le j < i$$$) such that $$$i + j = 2^k$$$ for some $$$k \ge 0$$$.

The proof is as follows: let's say that $$$0 \le j_1, j_2 < i$$$, $$$j_1 \ge j_2$$$, $$$i + j_1 = 2^{k_1}$$$, $$$i + j_2 = 2^{k_2}$$$. Then, $$$j_1 - j_2 = 2^{k_2} \cdot (2^{k_1-k_2} - 1)$$$. So, $$$j_1 \equiv j_2 \pmod {2^{k_2}}$$$. Since $$$i \le 2^{k_2}$$$, $$$j_1 = j_2$$$.

Then, we realize we can build a graph as follows: add an edge between $$$x$$$ and $$$y$$$ ($$$x, y \ge 0$$$) if $$$x + y = 2^k$$$ for some $$$k \ge 0$$$. Because of the first key observation, the graph must be **a tree**. We can root the tree at node $$$0$$$.

Our problem is equivalent to finding the pair of nodes which have maximum distance in a tree, which can be solved using the diameter of tree algorithm.

**Hint 4**

We can't build the entire tree as it has $$$10^9 + 1$$$ nodes. Try to notice something about the depth of the tree, then think of how this could help us solve the problem (by building the tree, or otherwise).

**Solution (Step 2)**

Since $$$0 \le a_i \le 10^9$$$, it is impossible to build the entire tree. A final observation is that: Consider any node $$$v$$$ with degree $$$\ge 2$$$ in the tree, then $$$v > p_v$$$ and $$$p_v > p_{p_v}$$$, therefore $$$v + p_v > p_v + p_{p_v}$$$ ($$$p_x$$$ denotes the parent of node $$$x$$$ in the tree).

Hence the depth of the tree is $$$\lceil \log(max(a_i)) \rceil = 30$$$, since there are only $$$\lceil \log(max(a_i)) \rceil$$$ possible $$$k$$$ ($$$0 \le k < 30$$$) for the sum of two nodes connected by an edge.

So, there are two ways to do it: the first way is to build parts of the tree: only the $$$n$$$ given nodes and the ancestors of the $$$n$$$ nodes. There will be at most $$$O(n \log max(a_i))$$$ nodes, which should fit into the memory limit. The second way is to not build the tree at all, and calculate the LCA (Lowest Common Ancestor) of two nodes to find their distance. Since the depth of the tree is $$$30$$$, LCA of two nodes can be computed by simply checking every ancestor of both nodes.

In both ways, the time complexity is $$$O(n \log max(a_i))$$$.

**Implementation (C++, physics0523)**

```
#include<bits/stdc++.h>
using namespace std;
int f(int x){
for(int i=0;;i++){
if((1<<i)>=x){
return (1<<i)-x;
}
}
}
using pi=pair<int,int>;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
map<int,pair<pi,pi>> mp;
priority_queue<int> pq;
for(int i=0;i<n;i++){
int v;
cin >> v;
pq.push(v);
mp[v].first=make_pair(0,i+1);
}
while(!pq.empty()){
int od=pq.top();pq.pop();
if((!pq.empty()) && od==pq.top()){continue;}
if(od!=1){
int nx=f(od);
pq.push(nx);
pi send=mp[od].first;
send.first++;
if(mp[nx].first<send){
mp[nx].second=mp[nx].first;
mp[nx].first=send;
}
else if(mp[nx].second<send){mp[nx].second=send;}
}
}
int ra=0,rb=0,rc=-1;
for(auto &nx : mp){
pair<pi,pi> tg=nx.second;
if(tg.first.second==0 || tg.second.second==0){continue;}
if(rc<tg.first.first+tg.second.first){
rc=tg.first.first+tg.second.first;
ra=tg.first.second;
rb=tg.second.second;
}
}
cout << ra << ' ' << rb << ' ' << rc << '\n';
return 0;
}
```

ooh fast editorial :)

dbsic211 orz

Wow it's amazingly fast editorial :D.

anthony123 orz

wow so superfast editorial!

thanks

omg fast editorial

As lck, I am offended by your template :(

Bad Kevin, I will throw you into River Cam when u arrive at Cambridge

omg kevinxiehk orz

Problems were really good.

Today B screwed me.

It was easy but very observational, if you can observe quick it's pretty easy otherwise it screws.

There must exist a solution for c=1 under the given constraints.

I still don't exactly see why that is the case....

Assume $$$c = 1$$$, you are left with $$$n - 1$$$ which must be divided in two groups, $$$a$$$ and $$$b$$$.

Dividing by $$$2$$$ will either equally distribute the amount or it won't.

In the second case, one value will always be $$$+1$$$ than the other and $$$gcd$$$ of two consecutive numbers is $$$1$$$.

In the first case, both numbers will either be odd or even. If both numbers are even then simply subtract $$$1$$$ from one value and add it to the second value, by doing this both numbers will be odd now with a difference of $$$2$$$, hence $$$gcd = 1$$$. If both numbers are odd, subtract $$$2$$$ from one value and add it to the other value. By doing this you will have two odd numbers with a difference of $$$4$$$, hence $$$gcd = 1$$$

Maybe this is a complicated way to think about it but that's how I did it

god

I thought this exactly same as well, so not a strange way i suppose

How to prove two odd numbers are mutually prime with a difference of 4 between them ?

if the difference between the two numbers is 4,their gcd cannot be greater than 4.now since the numbers are odd 2 and 4 won't divide them.so now we are left with 1 and 3.let's say the gcd is 3 so it divides the smaller number x the next numbers it will divide will be x+3,x+6 but our second number is x+4. so 1 is their gcd.

gcd(x+4, x) = gcd(x+4-x, x) = gcd(4, x) but x is odd => gcd(4, x) = 1

Awesome,thanks

Thanks!!

thanks!

Nice, thanks for the explanation!

When it comes to proving that there exists a pair $$$(a, b)$$$ for $$$c=1$$$ which solves the problem one can use Goldbach's conjecture (which was shown to work for numbers $$$\leq 10^{18}$$$). If $$$n-1$$$ is odd then it's easy to see that we can choose $$$a=x$$$ and $$$b=x+1$$$ where $$$x=\frac{n}{2}-1$$$, but when $$$n-1$$$ is even GC gives us that there exist 2 primes $$$p, q$$$ such that $$$p+q=n-1$$$.

Thanks your explanation was lucid and simple .I was able to frame the solution and am sure it will be helpful in upcoming problems. May God bless you with more ratings

Great contest! I especially enjoyed solving problem D, thanks :)

In D1, the difference between "<=,>=" and "<,>" changes everything...

Great contest! Great problems! Great editorial! Sad orange can’t play._.

Lightening fast editorial :)

Time complexity of editorial: O(1)

More like O(-1)

These editorials are faster than chinese's problem-solving.

In the solution of problem C, the observation will be $$$x$$$ $$$mod$$$ $$$y$$$ $$$< \lceil \frac{x}{2} \rceil$$$ if $$$x$$$ $$$>=$$$ $$$y$$$

why do you get this observation? any proof?

Problems were good and so the quality of the editorial. All editorials should have hint spoilers.

I like how the author split the editorial into hints, solutions, and code snippets, and had them spoilered separately, which would be helpful for beginners who are learning cp;) (But it’s also extra effort, so I wouldn’t go as far as to ask for having this in particular, rather, I’ll just treat it as a bonus)

As a tester, I have some fun facts about problem D:

Originally, D had only one version, which is the current D1. Then I tested D and came up with a $$$\frac{4n}{3} + O(1)$$$ query solution. (Actually, originally, $$$n \bmod 3 = 0$$$ wasn't a thing, and the lower bound was $$$4$$$, so getting that to AC was a lot of pain :v) That solution became D2 — except that later, arvindf232 came up with the $$$n + 2$$$ query solution. Then we had a problem, which was that we couldn't decide which of $$$2n$$$, $$$\frac{4n}{3}$$$, or $$$n$$$ should be the official D1/D2. In the end we decided that $$$2n$$$ for D1 and $$$n + O(1)$$$ for D2 would be best for balance.

We (or at least I) thought that D2 was more difficult than it ended up being. We had the idea of changing the distribution to 1750-1250-2500, but it never came to pass. In my opinion, the original distribution turned out to be better. :v

I'm curious, how many participants actually proved their solution of B?

EDIT: I'm not looking for proofs of this solution or that solution. I'm more interested in the ratio of "guessed/hoped" vs "solved". Actually in some sense it's more interesting to hear from people who didn't prove their solution.

Ya, i have prrof for my solution. By choosing c = 1, the problem can be proved by checking even or odd of number and its half. submission: https://codeforces.com/contest/1617/submission/139495888

The 3-case people probably proved their solution, but probably most other solutions didn't :v My "proof" was a vague understanding of probability and a heavy dose of inshallah :)

Me. I used the approach of finding the first prime that does not divide n — 1, which must exist within the first 10 primes since n is at most 1e9.

I did the same, although I think you meant (n — 1 — prime) mod prime != 0 instead of (n — 1) mod prime != 0

So the solution would be:

where p is the first prime such that (n — 1 — p) mod p != 0

if n-1 is odd then answer is some consecutive number but if it is even, by goldbach's conjecture it follows that it can be written as a sum of two primes.

I proved it but I think it's hackable. Solution Link

I did the same thing.

You can check it here

Ummm Yes, I can prove my solution

It took me 44 mins on B just to prove that a brute force soln works and in the end i coded the entire proof lol .When i was a newbie i used to solve these type of questions pretty fast but as my experience increased i started proving things haha.Anyways i liked the contest very much

Isn't this called Goldbach's conjecture that you can represent any number as sum of 2 primes so you can make n-1 with sum of 2 primes. As far as i know no one proved it until now

This is how I did (proof):

I always use a number line for such problems and this is my go-to. In this problem, I always considered c to be 1, and the rest of my solution went up from there.

If we give a look at the number line, then the gcd of any two numbers will never exceed their difference.

Case 1: n is even and say n=82; --> Taking c=1 leaves us with 81 --> 40.5 is what we get if we divide it by 2 (You know why we divide) --> Distribute the 0.5 (40.5+0.5 + 40.5-0.5 gives us 41 + 40) --> In the number line adjacent numbers will always have a gcd of 1. So gcd is 1.

Case 2a: n is odd and say n=81; --> Taking c=1 leaves us with 80 --> 40 is what we get if we divide it by 2 (You know why we divide) --> Move the two numbers to the nearest odd numbers (40-1 + 40+1 gives us 39 and 41) --> In the number line their difference is 2 and no way you can divide those numbers with an odd number which is greater than 1. So gcd is 1. (max diff is 2)

Case 2b: n is odd and say n=83; --> Taking c=1 leaves us with 82 --> 41 is what we get if we divide it by 2 (You know why we divide) --> Move the two numbers to the nearest odd numbers (41-2 + 41+2 gives us 39 + 43) --> In the number line their difference is 4 and no way you can divide those numbers together with an odd number other than 1. So gcd is 1(max diff is 4 and you can't jump from 39 to 43 using 3 steps)

So, it's proved that in all the 3 the cases their gcd will always be 1 for the given constraint while maintaining their summation.

i assumed the gcd is 1 because otherwise the complexity would be exponential then i made a program that told me how many numbers can be obtained from x%y with 1<=y<x and those were all from 1 to (x-1)/2 so i kind of proved it

139546379 I don't know why I get TLE on D2, I think my time complexity is $$$O(n)$$$.

Edit: I know where was wrong. I didn't handle the case when query return -1

Thank you so much!!!

Can we do D2 in $$$\leq n$$$ queries?

It can be done is $$$n + 1$$$ by reducing $$$1$$$ query from the editorial's solution using the fact that the two people between the impostor and crewmate we detected, are of opposite type, so we can just ask for one of them.

I don’t think $$$< n$$$ is possible, but exactly $$$n$$$ queries is possible (tho idk how)

There are around $$$2^n$$$ possible answers, and each queries gives a binary answer. So the theoretical lower bound is $$$\log_2(2^n)=n$$$ queries.

(nevermind, I was wrong here.)

I don't think this works in all cases. If the different 3-tuples occur somewhere in between, we will need $$$n+1$$$ queries still.

Yes, with this way it is mathematically impossible to get exactly $$$n$$$ queries. If there is a $$$n$$$ query solution it won't be this one.

Nice problems great editorial with hints. overall great contest!!! Well done dbsic211.

Thank you for the fast editorial :)

Was totally confused at C. Luckily understood the meaning of k range to solve D1 and that saved my rating for this contest or else whoooooosh it would have gone

Please explain me solution of problem C in easy language !

First see how many numbers from 1-n are not visited and how many numbers from array are left(numbers which are >n or are more than required for eg 3 2's so 2 are left unused).1st observation if a number is odd it can be change from 1 to number/2.Eg 7 --> 1 to 3,and if it is odd than it can be changed to number/2 — 1.Eg 10 --> 1 — 4.So now just iterate over the numbers left and the numbers not visited and if a left number can't be changed ans is false. You can refer to my solution

Thanks

Problem D in n+1 queries: 139550123

Can you explain your solution :)

How to think the solution of problem B during the contest....

While, There are no generalized ways to think about any problem.

How i though of problems like this contest's B is by observing the pattern by first writing a brute force solution (which in this case is 3 nested loop for a, b, and c), and then run it for small cases like n <= 50, and made the formula out of the observation. which turned out to be the 3rd solution of editorial.

Hope this helps :)

Actually, first observation is gcd(a,b)=c so a=cx and b=cy where x and y are mutually prime. So the given equation becomes c*(x+y+1)=n . so c is a factor of n. Now you think that if n is a prime number, then it's only factors are 1 and the number itself. if c=the prime number itself, then x+y+1=1 ===> x+y=0 which is not possible according to the given problem. So c=1 for prime numbers. On the other hand the equation will be holding for composite numbers as well so, you can proceed with c=1. therefore the equation becomes x+y+1=n or x+y=n-1. Now, we have already said that x and y are mutually prime. So the immediate thing that should come to mind is that two consecutive numbers are equal . if n-1 is odd, then you should know that an odd number can be written always as a sum of two consecutive numbers (if x is odd, then x=x/2+x/2+1 ...x unrelated to the explanation above) . otherwise,n-1 is even, so a possibility is x=(n-1)/2 and y=(n-1)/2 . But x and y are coprime, so probably, we can go one step forward for y and one step backward for x .Then x=(n-1)/2 -1 and y=(n-1)/2+1 .Now if originally x and y were even numbers, then the new x and y must be odd numbers. These two odd numbers with a difference of one will always be coprime. Otherwise,if both new x and y are even, then decrease x one more time and increase y one more time .Again we end up with two odd numbers and these two with a difference of 4 will always be mutually prime .

Great problems, fast editorial with hints, I hope more of these contests will be held :)

Thanks dbsic211

Great Questions! The contest was not good for me , wasn't able to solve any of them! Just another bad day.

Well done dbsic211 !

Superfast editorial!

What's more, with hints!

I enjoy the contest very much, the problems are fabulous, thank you!

orz

For anyone looking for video editorial you can check mine out

It's only up to D1 tho

Problems were nice, although I could try only up to D1.

Hoping to see you in another round :)

borked checker rejudge time

In B if the number is odd then there exists a solution for c = 1 by Goldbach's conjecture!(A famous conjecture). Although it isn't proven yet however has been verified for very large numbers well outside given limit. A nice trivia :)

However as Goldbach's conjecture is about primes, I wasn't able to construct solution where a and b are prime, within given time limits. So had to settle for them just being coprime.

Can anyone tell me, for problem D1 why I am getting the

wrong answer verdicton Test Case 1?Any help would be appreciable. Thank you :)

Submission

You are only printing the elements of ans. You also need to print the size of ans before you print it's elements.

Thanks, buddy! Now my code is asking too many queries so can you or anyone tell me any optimal way to solve this question.

I spent too many queries just to find one crewmate and one imposter to get the answer so is there is any optimal way to find them?

You can read the editorial. It tells you how to find one crewmate and one imposter in exactly n queries.

SIUUU!

In problem B , why Brute force solution is working

Because there are only limited divisors of $$$n - 1$$$, which means that

eventuallythere are going to be two coprime numbers. There's some math that proves this, but ehh, nobody cares enough to prove it.But that would be true if we were iterating "a" and checking gcd(a,n-1) but we are checking gcd(a ,n-1-a), here both the numbers are changing how can we comment if the gcd would be 1.

Edit

Sorry for my mistake. gcd(a,n-1-a) is equal as gcd(a,n-1)

because the gap of two prime number at most 300 in the range 10^12. so,when you picked up a big prime ,the other side is lower than prime.so there gcd is 1. for example, n=34,if we pick a prime 29,then the other side is (34-29)-1=4 so a=29,b=4 and gcd(29,4)=1.

My more complicated, less elegant solution to D1:

So in the worse path, we use (2n/3-1) + (n/3-1) + 2 + (n-4) = 2n queries.

Very nice trick to solve D2

can anyone help me with this code :

139558441

a lot of thanks to anyone who can help me

Try this test case:

Expected output is

`2`

, while your code produces`-1`

.my code produces 2 not -1

pic...

It's because you're not handling multiple test cases correctly. Just wrap this testcase with another one, and you can spot the error.

For example, on the input

your code produces

`-1 -1`

while the intended output is`-1 2`

.I understand now what's wrong with my code

SpoilerThanks a lot for the help

Thank you very much, I realized I just needed to change

`if(x>n ||(x == n && a[n] == true) )`

to`if(x>n ||(a[x] == true) )`

.can someone please tell why this is giving me RTE on the first test case? it is working fine on my compiler https://codeforces.com/contest/1617/submission/139558421

I like the A question which made me an orgasm

can anyone please explain this? in problem B solution 3

`if (n%2==0) cout<<"2 "<<(n-1)-2<<" 1\n";`

It's just $$$a = 2, b = n-3, c = 1$$$. $$$n$$$ is even, so $$$n-3$$$ is odd, so it's coprime with $$$2$$$.

ohh got it

If you are interested in video solutions, here are the solutions for the first

4problems.my code for problem C is giving right output in vs code but it is giving wrong output in codeforces for test 2 .Can someone say why it is happening so and how can be it corrected ? My submission link : https://codeforces.com/contest/1617/submission/139565621

Whyyyyy.... your mistake on E checker cost me 140 rating :(

-1000 social rating bad very bad :((((

.

5%4==1 5%3==2 9%6==3 14%10==4 5 is already left thus we can make a permutation in 4 moves. Hope this helps

I tried to hack my solution but I got "Unexpected verdict". Is there a problem with the solution to that problem?

The test is

2

7 9

The particular thing about that test is that the diameter of the tree shouldn’t consider the node 0, (just nodes 7 and 9 in this case) my solution didn’t consider that and that is the reason of the wrong answer. This happens when all the nodes in the input lie in the same path from the root to the farthest node. Please consider adding a similar test.

I've implemented the idea of D2 on D1(6 queries), but wasn't aware that same way I can solve D2. And i also missed the simple idea of D1!!

Nice Contest dbsic211

Fast editorial! Thanks!

Can someone please tell the prerequisites of problem E? I am in a dilemma whether to upsolve it or not. Also I think editorial should contain prerequisite section as we see in codechef :)

Problem E is really nice, good job!

dbsic211 , I think the condition in key observation in Problem C holds if y > (x/2) along with (x >= y)

i.e.`x mod y < x/2 if (x >= y) and (y > x/2)`

I think you have just missed

`(y > x/2)`

in writing in the key observation. Please review and update if necessary.Given:`x >= y > (x/2)`

Claim:`x mod y < x/2`

Proof:Is there anyone can solve D2 in n queries? I can just solve it in (n+1) queries!

I think c was a lot easier than b maybe I am weak in number theory

Couldn't solve even A, and submitted B with TLE, lol I'm too noob

So like the adaptive stuff about jury is just bs? that was a very weird addition for me but then the solution was kinda straight forward for D1 so Im thinking thats why they added it.

I used Trie to solve E. Submission link

(I know it's overkill but the logic is somewhat different from the one in editorial)

Hey! Can you please explain what is the idea behind your solution?

for Problem D1,why we need query $$$(n-1,n,1)$$$ and $$$(n,1,2)$$$ ?

It seems that query $$$(1,2,3)$$$ to $$$(n-2,n-1,n)$$$ can find one pair of crewmate and impostor.

can give me a counter-example？= ^ =

Not needed, I coded without that query.

Can you help me see why my code got WA?139605367

Your code seems to count imposters twice.

Like this

15

0 1 0 1 0 1 0 1 0 1 0 1 0 1 0

I understand now what's wrong with my code

Thanks a lot for the help！

I don't really know how my n^3 solution for Problem A didn't get FST. https://codeforces.com/contest/1617/submission/139485745

Could someone please tell me whats wrong with my d2 solution? I am getting the same output as testcase 1, but its showing "Incorrect set of impostors"?

Here's my code

`Since the number of impostors k and crewmates n-k satisfy k>n/3 and n−k>n/3, there must be one pair of adjacent queries that are different.`

Can someone explain why?

You know that n is divisible by 3. So you can split it into x intervals of 3 each, such that x*3=n. So assume x=n/3.

Now, k>n/3 =>k>x and k<2*x. so k belongs to [x+1,2*x).

Applying pigeon hole principle, you have x intervals and a minimum of x+1 impostors to fill, so at least one interval will have 2(or more) impostors.

With this, it wont be difficult to see that ~~~~~ for any n and k, that satisfy the constraints, the number of impostors k and crewmates n-k satisfy k>n/3 and n−k>n/3, there must be one pair of adjacent queries that are different. ~~~~~

According to the pigeon hole principle, As long as one adjacent 0-majority tuple and 1-majority tuple exists, there is exactly 4 cases of one kind of tuple.

0-major -> {0, 0, 0}, {0, 0, 1}, {0, 1, 0}, {1, 0, 0}; 1-major -> {1, 1, 1}, {1, 1, 0}, {1, 0, 1}, {0, 1, 1}.

for the {0-major} + {1-major} and {1-major} + {0-major} cases, brutally select each tuple, pair them up, try all 2 * (4 * 4) = 32 cases, we can see there will always be at least one 4-consecutive indices {id, id + 1, id + 2, id + 3} from all 6 places for each case, for which query {id, id + 1, id + 2} and query{id + 1, id + 2, id + 3} differs.

For example check 2 tuples {0 1 1} + {0 0 0}, start with the second index, {1 1 0 0} meets our need.

The method may be kind of tedious, I wonder if other elegant proofs exist.

Need help in understanding WA for C. https://codeforces.com/contest/1617/submission/139618376 My submission, I have implemented a code similar to the one described in the editorial (I think). I get WA on a 2000 elements array so I'm not able to identify the test case which defeats my solution. Any help will be appreciated.

InputExpected Output-1

Your Output0

In problem D, I wonder what "The jury is adaptive" means. Why there are still feedbacks of "wrong set of impostors"?

Problem D is pretty amazing. Loved to upsolve it.

Can anyone explain me the meaning of "FST","AK"?

failed on system test

solve all the problems in a contest

I have a solution to problem E which does not involve graphs in any way.

At the beginning, our array values fit in range $$$[0, 2^{30}]$$$. Let's now divide the array into two parts $$$L$$$ and $$$R$$$, where $$$L$$$ will contain all values $$$\le 2^{29}$$$ and $$$R$$$ will contain all larger values.

Now suppose $$$(x, y)$$$ is the optimal pair we are searching for. Here comes a crucial observation. If both $$$(x, y)$$$ are in $$$R$$$ they are both larger than $$$2^{29}$$$ so we cannot use any $$$k \le 29$$$ operation on them. The only way to continue is to use $$$k = 30$$$ and make them both less than $$$2^{29}$$$.

Also suppose $$$x \le 2^{29}$$$ and $$$y > 2^{29}$$$. In this case we have to transfer one value to the other side by using $$$k = 30$$$, but transferring $$$x$$$ is never optimal. Let's prove it.

Case $$$x = 2^{29}$$$ is trivial. Otherwise $$$x < 2^{29}$$$ so $$$2^{30} - x > 2^{29}$$$ and since also $$$y > 2^{29}$$$ we arrive at the previous state when we are forced to decrease both of them using $$$k = 30$$$. This means that it is always better to do an operation on $$$y$$$, again reducing it to some value $$$< 2^{29}$$$ and continue from there.

All the reasoning above means that all values $$$R$$$ have to be reduced in one operation to become less than $$$2^{29}$$$ and after that we can merge those values with $$$L$$$ and repeat our algorithm again with a threshold $$$2^{29}$$$.

We can repeat this process until we arrive at a simple case when all values are in range $$$[0, 1]$$$. Here we can just consider a transition $$$0 \rightarrow 1$$$ and we are done.

This solution can be implemented in various ways. One I can think of is to store $$$L$$$ and $$$R$$$ as sorted vectors and merge them using two pointers. But I personally think that maps are the most simple and elegant way. Maps introduce an additional $$$\log n$$$ factor, resulting in a $$$O(n \log n \log 10^9)$$$ solution overall which is still fast enough considering a very generous time limit.

Here is my submission: https://codeforces.com/contest/1617/submission/139683868

Can someone find what's wrong? I am getting wrong number of impostors verdict in Test 1 itself in D2 while upsolving. I think it maybe something related to interactive problems. Link to submission

Since the number of impostors k and crewmates n−k satisfy k>n/3 and n−k>n/3, there must be one pair of adjacent queries that are different.

Can someone please provide a proof of this line from the editorial of problem D1?

[My Submission](https://codeforces.com/contest/1617/submission/139840155

Can someone tell me why my code to Problem D1 is getting Idleness limit exceeded even though I flushed wherever required. Thanks in advance.

You are flushing after cin , flush after cout. Tip : Use endl.

Sorry if it's obvious, but why is the graph formed in E connected? I see that there are no cycles but how do we know that we can get from any $$$x$$$ to any $$$y$$$?

Any number can reach 0, and 0 can reach any number.

Can someone help me with this submission of problem D2? On my system it is working fine for test 1, but it is failing here.. Maybe some thing related to interative problems... Thanks in advance!

https://codeforces.com/contest/1617/submission/140571766

I think this is not the intended solution for 1617B - GCD Problem...

Link : 141021665

In problem 1617B :GCD problema/c to question we have to find a , b ,c such that a + b + c=n and gcd(a ,b)=c. so for example: n=18 a=1,b=16,c=1 since gcd(1 ,16)=1 and 1+16+1=18. Is it considered as a correct soln??? if yes then can we apply this for all value of n.

can someone tell me why i am getting WA on testcase 2 in this solution : https://codeforces.com/contest/1617/submission/141883310

Can anyone tell me what's wrong with my code? I've coded differently, but the approach is same as given for problem C.

142936588

Solution with TC O(N):142954118

Can anyone tell me why my solution is not working for Problem C

https://codeforces.com/contest/1617/submission/146021818

In Problem C, According to Editorial Solution I found

-1as output when I providearray = {1, 2, 7, 8}as Input. But here the output should be2. Like forarray[3] = 7we can choosex = 3and7 % 3i.e. 4lies in[1, n],similarly forarray[4] = 8we can choosex = 5and8 % 5 i.e. 3 lies in [1, n].hence we can obtain the permutation as{1, 2, 4, 3}which should be acceptable. May be I am wrong if anyone found the proper solution please reply ASAP.$$$7 \% 3$$$ is $$$1$$$ not $$$4$$$, since the remainder when $$$7$$$ is divided by $$$3$$$ is $$$1$$$.

Really, Great Editorial :)