PROBLEM LINK:
Setter: Alei Reyes
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Game-Theory, Proofs.
PROBLEM:
Tweedledee and Tweedledum are playing a complicated graph game on a fully connected graph with N nodes. Each node has a beauty value attached to it, given by B array.
Refer to the problem statement for details on the way the game is played.
QUICK EXPLANATION
- We can prove that wherever Tweedledee may place the token, he cannot win, so he aims to make game last longest and then maximizing the beauty value of game while Tweedledum aims to win the game as quickly as possible and then maximize the value of the game.
- When both players play optimally, the game lasts exactly 2*(n-2)+1 moves and the beauty of game is given by m1*m2+(m1+m2)*(sum-m1-m2) where sum = \sum_{i = 1}^N B_i, m1 is the maximum beauty of any node and m2 is the second maximum beauty of any node.
EXPLANATION
This editorial has two parts, first proving that Tweedledum always wins, and secondly, finding the maximum value.
First of all, let us assume the token is initially placed at node u and in the first move, Tweedledum moves it to node v.
Now, let us build a bipartite graph with node u and node v in the first partition and remaining nodes in the second partition. We can see, that all edges in the first partition are already removed, so every move from the first partition shall be to the second partition.
Now, Tweedledee has to move and he has to move from the current node it to any node in the second partition. Tweedledum can always move it back to the first partition. If the current node before Tweedledee’s move was u, he moves it to v and vice versa. This strategy guarantee that one by one, all N-2 nodes in the second partition would become unreachable from both u and v and Tweedledee won’t be able to move, thus losing the game.
Hence, Tweedledee can never win, so Tweedledee aims to make the game last longest possible and then maximizing the beauty value, while Tweedledum aims to end the game as quickly as possible and maximizing the beauty value.
Since in above strategy, all the moves made by Tweedledee were forced, Tweedledum can always ensure that the game ends in 2*(N-2)+1 moves, and this is the best he can do since Tweedledee also plays optimally. Hence, game cannot last more than 2*(N-2)+1 moves. But can it be even shorter?
No, it cannot be, since whenever the first player is to move, he can always go to an unvisited node in the second partition, and since he wants to maximize the number of moves, he always moves to an unvisited node.
Tweedledum trying another strategy
Let us consider the case whether the game proceeds as follows.
Tweedledee place token on u, Tweedledum moves it to v, Tweedledee moves it to w. At this point, the above strategy suggests moving token back to u. Let us see what happens if Tweedledum decides to move it to some node in the first partition, say x.
Now, If N = 4, then Tweedledee can actually win this game by moving token to v.
If N \neq 4, then Tweedledum can save the day by moving from v to an unvisited vertex, say y. This way, Tweedledum got an inferior position, still might win, but taking more number of moves to trap Tweedledee than the first strategy.
The game would proceed as y -> w -> u -> x -> y -> u. At this point, Tweedledum got trapped, as now all edges among first five nodes got exhausted and we can apply the first strategy with players reversed, these five nodes as first partition, now Tweedledum forced to move vertex from the first partition to second partition, and Tweedledee moving it back to the first partition, thus winning the game.
Hence, Both of them now want to maximize the beauty and Tweedledum will win the game.
Calculating the beauty of game
Suppose X is the beauty of node u and Y is the beauty of node v in the above simulation, and S is the sum of beauty of nodes in the second partition.
The beauty of game is X*Y+S*(X+Y) since first, the edge between node u and v is traversed, and then all edges connecting node u and node v with all nodes in the second partition are traversed.
What now matters is the choice of nodes to maximize value. It is easy to prove that choosing two nodes with maximum and second maximum values shall maximize the value of the game, and the value can also be computed using the above expression, thus computing the beauty of game.
Bonus: What if the losing player (Tweedledee) wants to minimize the value of the game?
TIME COMPLEXITY
Time complexity is O(N) per test case. (O(N*log(N)) if sorting is used.)
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long int uli;
typedef long long int ll;
int rint(char nxt){
char ch=getchar();
int v=0;
int sgn=1;
if(ch=='-')sgn=-1;
else{
assert('0'<=ch&&ch<='9');
v=ch-'0';
}
while(true){
ch=getchar();
if('0'<=ch && ch<='9')v=v*10+ch-'0';
else{
assert(ch==nxt);
break;
}
}
return v*sgn;
}
const ll is_query = -(1LL<<62);
struct Line {
ll m, b;
mutable function<const Line*()> succ;
bool operator<(const Line& rhs) const {
if (rhs.b != is_query) return m < rhs.m;
const Line* s = succ();
if (!s) return 0;
ll x = rhs.m;
return b - s->b < (s->m - m) * x;
}
};
struct HullDynamic : public multiset<Line> { // will maintain upper hull for maximum
bool bad(iterator y) {
auto z = next(y);
if (y == begin()) {
if (z == end()) return 0;
return y->m == z->m && y->b <= z->b;
}
auto x = prev(y);
if (z == end()) return y->m == x->m && y->b <= x->b;
return (x->b - y->b)*(z->m - y->m) >= (y->b - z->b)*(y->m - x->m);
}
void insert_line(ll m, ll b) {
auto y = insert({ m, b });
y->succ = [=] { return next(y) == end() ? 0 : &*next(y); };
if (bad(y)) { erase(y); return; }
while (next(y) != end() && bad(next(y))) erase(next(y));
while (y != begin() && bad(prev(y))) erase(prev(y));
}
ll eval(ll x) {
auto l = *lower_bound((Line) { x, is_query });
return l.m * x + l.b;
}
};
const int mx=1e5+10;
uli b[mx];
int main(){
// freopen("secret/1.in","r",stdin);
// freopen("secret/1.out","w",stdout);
int t=rint('\n');
int sn=0;
while(t--){
int n=rint(' ');
assert(3<=n && n<=1e5);
sn+=n;
assert(sn<=5e5);
uli s=0;
for(int i=0;i<n;i++){
b[i]=rint(i==n-1?'\n':' ');
assert(1<=b[i]&&b[i]<=1e3);
s+=b[i];
}
HullDynamic din;
uli ans=0;
for(int i=0;i<n;i++){
uli ti=b[i]*(s-b[i]);
if(i!=0){
uli bet=ti+din.eval(b[i]);
ans=max(ans,bet);
}
din.insert_line(-b[i],ti);
}
printf("%lld\n",ans);
}
assert(getchar()==EOF);
return 0;
}
Tester's Solution
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill - cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout)
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// find_by_order() // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
ll b[123456];
int main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int i;
rep(i,n){
cin>>b[i];
}
sort(b,b+n);
ll ans=b[n-1]*b[n-2];
ll sumi=0;
rep(i,n-2){
sumi+=b[i];
}
ans+=sumi*(b[n-1]+b[n-2]);
cout<<ans<<endl;
}
return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
public class Main{
//SOLUTION BEGIN
//Into the Hardware Mode
long mod = (long)1e9+7;
void pre() throws Exception{}
void solve(int TC)throws Exception{
int n = ni();
long[] b= new long[n];
for(int i = 0; i< n; i++)b[i] = nl();
Arrays.sort(b);
long ans = 0;
for(int i = 0; i< n-2; i++)ans += b[i]*(b[n-2]+b[n-1]);
ans += b[n-1]*b[n-2];
pn(ans);
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
void exit(boolean b){if(!b)System.exit(0);}
long IINF = (long)1e18;
final int INF = (int)1e9, MX = (int)2e6+5;
DecimalFormat df = new DecimalFormat("0.00");
double PI = 3.141592653589793238462643383279502884197169399, eps = 1e-7;
static boolean multipleTC = true, memory = false, fileIO = false;
FastReader in;PrintWriter out;
void run() throws Exception{
if(fileIO){
in = new FastReader("C:/users/user/desktop/inp.in");
out = new PrintWriter("C:/users/user/desktop/out.out");
}else {
in = new FastReader();
out = new PrintWriter(System.out);
}
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();
for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
if(memory)new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
else new Main().run();
}
int find(int[] set, int u){return set[u] = (set[u] == u?u:find(set, set[u]));}
int digit(long s){int ans = 0;while(s>0){s/=10;ans++;}return ans;}
long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to share your approach. Suggestions are welcomed as always. 