NWERC 2017 Solutions

I tried solving the problems from NWERC 2017 to practice.

A. Ascending Photo

When given an array of numbers, we want to cut it into some pieces, then rearrange the pieces so that the numbers are increasing. We want to find the minimum number of cuts needed to achieve this.

To start off, compress all unique heights to a range of $[1, m]$ . After that, remove all parts where the same height appears continuously, and just put one of that height, as it is obvious we don’t have to cut them. Then, a sequence like $[3 6 12 7 7 7 7 8 10 5 5]$ will become $[1 3 7 5 4 6 2]$

If all numbers are unique, we must cut whenever $a_{i + 1} - a_{i} \neq 1$ . However, this is not the case, and thus we need a better solution.

Let $d p_{i}$ be the number of non-cuts in front of $i$ after rearranging the array. We can find the $d p$ values like the following:

If $a_{i}$ is unique, then for all $j$ where $a_{j} = a_{i} - 1$ $d p_{i} = max (d p_{i}, d p_{j} + 1)$ if $j = i - 1$ and $d p_{i} = max (d p_{i}, d p_{j})$ if otherwise. This is because if a unique value is next to a value 1 lower than itself, its possible to just put them together without cutting.

The case where $a_{i}$ is not unique is a bit more complicated. Again, we look at all $j$ where $a_{j} = a_{i} - 1$ . If $a_{j + 1} = a_{i}$ and $j + 1 \neq i$ then $d p_{i} = max (d p_{i}, d p_{j} + 1)$ , and $d p_{i} = max (d p_{i}, d p_{j})$ if otherwise. If a value is not unique, we might have to make a cut even if the values are consecutive. However, if there is a consecutive part somewhere else, we can put them together and put the current number behind it, making an additional non-cut.

Finding all $d p$ values naively will take $O (N^{2})$ time. However, for some value $k$ , we can just keep track of the total maximum $d p_{i}$ where $a_{i} = k$ , and the maximum( $m x$ ) and second largest( $m x 2$ ) of $d p_{i}$ where $a_{i} = a_{j} - 1$ . Then, if a value is unique we simply check the previous index. Otherwise, we first make $d p_{i}$ the total maximum of the previous value. If $a_{i - 1} = a_{i} - 1$ and $d p_{i - 1} = m x$ then $d p_{i} = max (d p_{i}, m x 2 + 1)$ , if $d p_{i - 1} \neq m x$ then $d p_{i} = max (d p_{i}, m x + 1)$ . This allows us to solve the entire problem in $O (N l o g N)$ time.

code

  
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
typedef complex<double> cpx;
#define fastio cin.tie(0)->sync_with_stdio(0); cout.tie(0);
#define all(x) x.begin(),x.end()
#define compress(x) x.erase(unique(all(x)),x.end())
#define ff first
#define ss second

ll n,a[1000010],b[1000010],cnt[1000010];
ll dp[1000010],yes[1000010];

int main(){
    fastio;
    cin >> n;
    vector<ll> cp;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        cp.push_back(a[i]);
    }
    sort(all(cp));
    compress(cp);
    for(int i=1;i<=n;i++){
        a[i] = lower_bound(all(cp),a[i])-cp.begin()+1;
    }
    ll t = 1;
    for(int i=1;i<=n;i++){
        if(a[i]!=a[i-1]) b[t++] = a[i];
    }
    n = t-1;
    vector<pll> v;
    for(int i=1;i<=n;i++){
        cnt[b[i]]++;
        v.push_back({b[i],i});
        if(b[i-1]+1==b[i]) yes[b[i]]++;
    }
    sort(all(v));
    ll mt = 0, mx1 = 0, mx2 = 0, pr = 1;
    ll tm = 0, tm1 = 0, tm2 = 0;
    for(auto i:v){
        if(i.ff!=pr){
            mt = tm;
            mx1 = tm1;
            mx2 = tm2;
            tm = 0; tm1 = 0; tm2 = 0;
        }
        if(i.ff==1){
            dp[i.ss] = 0;
        }
        else{
            if(cnt[i.ff]==1){
                if(b[i.ss-1]==i.ff-1) dp[i.ss] = max(dp[i.ss],dp[i.ss-1]+1);
                dp[i.ss] = max(dp[i.ss],mt);
                ll k = dp[i.ss];
                tm = max(tm,k);
                if(b[i.ss+1]==i.ff+1){
                    if(tm1<k){
                        tm2 = tm1;
                        tm1 = k;
                    }
                    else if(tm2<k){
                        tm2 = k;
                    }
                }
            }
            else{
                dp[i.ss] = max(dp[i.ss],mt);
                if(b[i.ss-1]==i.ff-1&&dp[i.ss-1]==mx1){
                    if(yes[i.ff]>1) dp[i.ss] = max(dp[i.ss],mx2+1);
                }
                else if(b[i.ss-1]==i.ff-1){
                    if(yes[i.ff]>1) dp[i.ss] = max(dp[i.ss],mx1+1);
                }
                else{
                    if(yes[i.ff]>0) dp[i.ss] = max(dp[i.ss],mx1+1);
                }
                ll k = dp[i.ss];
                tm = max(tm,k);
                if(b[i.ss+1]==i.ff+1){
                    if(tm1<k){
                        tm2 = tm1;
                        tm1 = k;
                    }
                    else if(tm2<k){
                        tm2 = k;
                    }
                }
            }
        }
        pr = i.ff;
    }
    // for(int i=1;i<=n;i++){
    //     cout << dp[i] << " ";
    // }
    // cout << "\n";
    cout << n-1-tm << "\n";
}

B. Boss Battle

Problem Link

We blow up a bomb which destroys three consecutive pillars. After that, the boss moves to an adjacent pillar. We need to find the minimum number of bombs to defeat the boss in the worst case scenario.

We blow up a bomb. 3 consecutive pillars are destroyed. It is possible for the boss to move to the 2 pillars at each end, meaning we know for sure the boss is not in the middle destroyed pillar. Blow up 3 again, and this time there are 4 destroyed pillars. The boss can move to the 2 pillars at the end, meaning that the boss is definitely not in the middle 2. Continuing we know that every time we blow up a bomb we can increase 1 pillar where the boss is definitely not in. When 3 pillars are left, we can kill boss. Therefore the answer is $max (1, n - 2)$ .

code

  
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
typedef complex<double> cpx;
#define fastio cin.tie(0)->sync_with_stdio(0); cout.tie(0);
#define all(x) x.begin(),x.end()
#define compress(x) x.erase(unique(all(x)),x.end())
#define ff first
#define ss second

int main(){
    fastio;
    ll n; cin >> n;
    cout << max(1LL,n-2) << "\n";
}

C. Connect the Dots

Problem Link

Did not solve yet.

D. Dunglish

Problem Link

Given a sentence and a list of correct and incorrect translations for each word, find the number of correct and incorrect translations possible. If only one possible translation exists, output that translation.

For a word $i$ let the number of correct translations be $c_{i}$ and incorrect translations be $n_{i}$ . Then the total number of translations is the product of $(c_{i} + n_{i})$ , the number of correct translations is the product of $c_{i}$ , and the number of incorrect translations can be obtained by subtracting the two.

In case the number of translations is 1, just save all the translations in any way, and output it.

code

  
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
typedef complex<double> cpx;
#define fastio cin.tie(0)->sync_with_stdio(0); cout.tie(0);
#define all(x) x.begin(),x.end()
#define compress(x) x.erase(unique(all(x)),x.end())
#define ff first
#define ss second

ll n,m;
string st[30];
map<string,ll> cr,icr;
map<string,string> mst;

int main(){
    fastio;
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> st[i];
    }
    cin >> m;
    for(int i=0;i<m;i++){
        string x,y,z; cin >> x >> y >> z;
        mst[x] = y;
        if(z=="correct") cr[x]++;
        else icr[x]++;
    }
    ll cnt = 1, cor = 1;
    for(int i=1;i<=n;i++){
        cnt *= (cr[st[i]]+icr[st[i]]);
        cor *= cr[st[i]];
    }
    if(cnt>1){
        cout << cor << " correct\n";
        cout << cnt-cor << " incorrect";
    }
    else{
        ll f = 1;
        for(int i=1;i<=n;i++){
            cout << mst[st[i]] << " ";
            if(icr[st[i]]) f = 0;
        }
        cout << "\n";
        if(f) cout << "correct";
        else cout << "incorrect";
    }
}

E. English Restaurant

Problem Link

Did not solve yet.

F. Factor-Free Tree

Problem Link

Given an array, find a binary tree where a number is written on each node, and the preorder of the binary tree results in the given array. In addition, the number written on a node must be coprime with the numbers written on all of its ancestors.

A subtree represents some consecutive subarray. Also, the root of the tree must be coprime to all of the nodes. Therefore, given a range $[l, r]$ , if we find an index $i$ so that $a_{i}$ is coprime with all other numbers in the range, then $i$ can become the root of the subtree representing $[l, r]$ . If there are many possible $i$ , then it doesn’t matter which one we choose.

Factorize all numbers. Then by looking at each factor, we can quickly find some $l_{i}$ and $r_{i}$ such that $a_{l_{i}}$ is the the closest number on the left of $i$ that is not coprime with $a_{i}$ , and visa versa via binary search. Then, given some range $[l, r]$ , we only need to check whether $l_{i} < l$ and $r < r_{i}$ for each $i$ to know if $i$ can be a root.

However, simply looping through $l$ to $r$ will result in a $O (N^{2})$ worst case complexity, like of that in quick sort. It turns out that searching bidirectionally (starting from both $l$ and $r$ ) is enough to make the time complexity to $O (N l o g N)$ . Intuitively, if the $i$ we’re looking for is on the end of a range, we’ll find it quickly, otherwise it take some time to find, but the resulting tree will be balanced.

code

  
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
typedef complex<double> cpx;
#define fastio cin.tie(0)->sync_with_stdio(0); cout.tie(0);
#define all(x) x.begin(),x.end()
#define compress(x) x.erase(unique(all(x)),x.end())
#define ff first
#define ss second

const int MAX = 1e7+1;

int c[10000001];
vector<int> id[10000000];

int n,a[1000001];
int ans[1000001];

int chk(int k, int l, int r){
    int li = -1, ri = 1e9;
    for(int j=a[k];j>1;){
        int p = c[j];
        int idx = lower_bound(all(id[p]),k) - id[p].begin();
        if(idx>0) li = max(li,id[p][idx-1]);
        if(idx<(int)id[p].size()-1) ri = min(ri,id[p][idx+1]);
        while(j%p==0) j /= p;
    }
    if(li<l&&ri>r) return 1;
    else return 0;
}

int solve(int s, int e, int p = 0){
    if(s>n||s<1||e>n||e<1||s>e) return 1;
    int ret = 0;
    for(int i=s,j=e;i<=j;i++,j--){
        if(chk(i,s,e)){
            ret = i;
            break;
        }
        if(chk(j,s,e)){
            ret = j;
            break;
        }
    }
    if(!ret) return 0;
    ans[ret] = p;
    return solve(s,ret-1,ret)&&solve(ret+1,e,ret);
}

int main(){
    fastio;
    iota(c,c+MAX,0);
    for(int i=2;i<MAX;i++){
        if(c[i]==i){
            for(int j=i+i;j<MAX;j+=i){
                c[j] = min(c[j],i);
            }
        }
    }
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        for(int j=a[i];j>1;){
            int k = c[j];
            id[k].push_back(i);
            while(j%k==0) j /= k;
        }
    }
    int k = solve(1,n);
    if(!k) cout << "impossible";
    else{
        for(int i=1;i<=n;i++){
            cout << ans[i] << " ";
        }
    }
}

G. Glyph Recognition

Problem Link

For a given set of points find the regular polygon that results in the highest score.

It is possible to binary search. For each regular polygon, binary search for the side length $a$ . Count the number of points contained inside the polygon(doesn’t matter if this is done in $O (N)$ in each step. Do this twice to find the smallest $a$ such that the polygon contains all points, and the largest $a$ such that the polygon doesn’t contain any points. The area of the polygon can be calculated with $n a^{2} \sin (\frac{2 π}{n})$ where $n$ is the number of edges.

code

  
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
typedef complex<double> cpx;
#define fastio cin.tie(0)->sync_with_stdio(0); cout.tie(0);
#define all(x) x.begin(),x.end()
#define compress(x) x.erase(unique(all(x)),x.end())
#define ff first
#define ss second

const double PI = atan2(0,-1);

ll n;
vector<pll> v;

double ccw(pdd a, pdd b, pdd c){
    double k = (b.ff-a.ff)*(c.ss-a.ss)-(b.ss-a.ss)*(c.ff-a.ff);
    if(k>1e-6) return 1;
    else if(k<-1e-6) return -1;
    else return 0;
}

ll cnt(double r, ll x){
    vector<pdd> pol;
    double ang = 0;
    for(int i=0;i<x;i++){
        pol.push_back({r*cos(ang),r*sin(ang)});
        ang += 2*PI/x;
    }
    ll ret = 0;
    for(auto i:v){
        ll f = 1;
        for(int j=0;j<x;j++){
            ll k = ccw(i,pol[j],pol[(j+1)%x]);
            if(k<0) f = 0;
        }
        ret += f;
    }
    return ret;
}

double score(ll x){
    double r1 = 0;
    double lo = 0, hi = 1e7;
    while(hi-lo>1e-7){
        double m = (lo+hi)/2;
        ll tmp = cnt(m,x);
        if(tmp>0){
            hi = m;
        }
        else{
            r1 = max(r1,lo);
            lo = m;
        }
    }
    double r2 = 1e10;
    lo = 0, hi = 1e7;
    while(hi-lo>1e-7){
        double m = (lo+hi)/2;
        ll tmp = cnt(m,x);
        if(tmp==n){
            r2 = min(r2,hi);
            hi = m;
        }
        else{
            lo = m;
        }
    }
    //cout << r1 << " " << r2 << "\n";
    double a1 = x*r1*r1*sin(2*PI/x);
    double a2 = x*r2*r2*sin(2*PI/x);
    return a1/a2;
}

int main(){
    fastio;
    cin >> n;
    for(int i=0;i<n;i++){
        ll x,y; cin >> x >> y;
        v.push_back({x,y});
    }
    double ns = -1;
    ll ans = -1;
    for(int i=3;i<=8;i++){
        double k = score(i);
        if(k>ns){
            ns = k;
            ans = i;
        }
    }
    cout << setprecision(10);
    cout << fixed << ans << " " << ns;
}

H. High Score

Problem Link

Given $a, b, c, d$ , find the maximum possible value of $a^{2} + b^{2} + c^{2} - 7 \cdot min (a, b, c)$ by distributing $d$ to $a, b, c$ .

If the minimum is large enough, it’s best to just add everything to the maximum. Otherwise, brute force by making the minimum into some number, then adding all leftovers to the maximum.

code

  
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
typedef complex<double> cpx;
#define fastio cin.tie(0)->sync_with_stdio(0); cout.tie(0);
#define all(x) x.begin(),x.end()
#define compress(x) x.erase(unique(all(x)),x.end())
#define ff first
#define ss second

ll n;

void solve(){
    vector<ll> v;
    for(int i=0;i<3;i++){
        ll x; cin >> x;
        v.push_back(x);
    }
    ll t; cin >> t;
    sort(all(v));
    if(v[0]>(ll)1e6){
        cout << v[0]*v[0]+v[1]*v[1]+(v[2]+t)*(v[2]+t)+7*v[0] << "\n";
    }
    else{
        ll ans = v[0]*v[0]+v[1]*v[1]+(v[2]+t)*(v[2]+t)+7*v[0];
        for(int i=1;i<=(ll)1e7;i++){
            if(v[0]>i) continue;
            ll tmp = 0, tv[3] = {v[0],v[1],v[2]};
            if(v[0]<i) tv[0] = i, tmp += i-v[0];
            if(v[1]<i) tv[1] = i, tmp += i-v[1];
            if(v[2]<i) tv[2] = i, tmp += i-v[2];
            if(tmp>t) break;
            ll k = t-tmp;
            //cout << v[0] << " " << v[1] << " " << v[2] << "\n";
            ans = max(ans,tv[0]*tv[0]+tv[1]*tv[1]+(tv[2]+k)*(tv[2]+k)+7*i);
        }
        cout << ans << "\n";
    }
}

int main(){
    fastio;
    cin >> n;
    for(int i=0;i<n;i++){
        solve();
    }
}

I. Installing Apps

Problem Link

To download an app you need $a_{i}$ storage available. After downloading, it takes up $b_{i}$ storage. Find the maximum number of apps you can install and a sequence on what order to download them.

Sort the apps in order of $b_{i} - a_{i}$ . If it is not possible to download apps in this order, it is always impossible. After this, the problem is just a standard knapsack problem, where $d p_{i, j}$ is the maximum number apps installable up to the $i$ ’th app with $j$ storage. Finding the actual sequence can be done by keeping a table of indices where $d p_{i, j}$ updated from.

code

  
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
typedef complex<double> cpx;
#define fastio cin.tie(0)->sync_with_stdio(0); cout.tie(0);
#define all(x) x.begin(),x.end()
#define compress(x) x.erase(unique(all(x)),x.end())
#define ff first
#define ss second

struct Data{
    ll ff,ss,i;
};

ll n,m,dp[510][10010],mp[510];
Data a[510];
pll tr[510][10010];

int main(){
    fastio;
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        cin >> a[i].ff >> a[i].ss;
        a[i].i = i;
    }
    sort(a+1,a+1+n,[&](Data x, Data y){
        return x.ss-x.ff<y.ss-y.ff;
    });
    for(int i=1;i<=n;i++){
        mp[i] = a[i].i;
    }
    for(int i=1;i<=n;i++){
        for(int j=m;j>=0;j--){
            dp[i][j] = dp[i-1][j];
            tr[i][j] = {i-1,j};
            if(j<a[i].ss) continue;
            if(a[i].ff>a[i].ss&&m-(j-a[i].ss)>=a[i].ff){
                ll k = dp[i-1][j-a[i].ss]+1;
                if(k>dp[i][j]){
                    dp[i][j] = k;
                    tr[i][j] = {i-1,j-a[i].ss};
                }
            }
            else if(a[i].ff<=a[i].ss){
                ll k = dp[i-1][j-a[i].ss]+1;
                if(k>dp[i][j]){
                    dp[i][j] = k;
                    tr[i][j] = {i-1,j-a[i].ss};
                }
            }
        }
    }
    ll ri = n, rj = 0, ans = -1;
    for(int i=0;i<=m;i++){
        if(dp[n][i]>ans){
            ans = dp[n][i];
            rj = i;
        }
    }
    cout << ans << "\n";
    vector<ll> ret;
    while(ri!=0||rj!=0){
        ll ni = tr[ri][rj].ff;
        ll nj = tr[ri][rj].ss;
        if(nj!=rj){
            ret.push_back(ri);
        }
        ri = ni; rj = nj;
    }
    reverse(all(ret));
    for(auto i:ret){
        cout << mp[i] << " ";
    }
}

J. Juggling Troupe

Problem Link

Given an array consisting of values of $0, 1, 2$ , find the final state after following the rules stated in the problem.

Think of the problem when there is only one $2$ at index $i$ . Let $l_{i}$ and $r_{i}$ be the indices of the closest $0$ on the left and the closest $0$ on the right. Then, at the end of the show, the value at indices $l_{i}$ and $r_{i}$ change to $1$ , the value at $i$ changes to $1$ as well, and the value at $r_{i} + l_{i} - i$ becomes $0$ .

It is possible to see that we can look at all $2$ independently. Keep the indices of $0$ ’s in a BST. Also put -1 and $n$ and remember to never remove these two. For each $2$ , change it’s current value to 1, find $l_{i}$ and $r_{i}$ via binary search, remove them (if they are not -1 or $n$ ), and if the value at $r_{i} + l_{i} - i$ is not equal to 2, put it in the BST.

Finally, for each index from $0$ to $n - 1$ , if it is in the BST output 0, otherwise output 1.

K. Knockout Tournament

Problem Link

Find the maximum probability which the first player can win by ordering the players in some way.

Lets say there are some dummy players with rating 0 so that the number of players is a power of 2. It is obvious that it is best to order the players in order of their rating (so that the highest 2 goes together and so on) and put player 1 at the end (with the lowest rating) to maximize the probability of winning.

Let $p_{i, j}$ be the probability of $i$ winning the $j$ ’th round. Then by definition $p_{i, 0} = \frac{a_{i}}{a_{i} + a_{k}}$ where $k$ is the opponent of $i$ . When $j \geq 1$ , $p_{i, j} = p_{i . j - 1} \cdot \sum_{k} p_{k, j - 1} \cdot \frac{a_{i}}{a_{i} + a_{k}}$ for all $k$ that $i$ can meet as an opponent on the $j$ ’th round. The range for $k$ should be easy to calculate. Now we simply calculate all $p$ values.

code

  
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
typedef complex<double> cpx;
#define fastio cin.tie(0)->sync_with_stdio(0); cout.tie(0);
#define all(x) x.begin(),x.end()
#define compress(x) x.erase(unique(all(x)),x.end())
#define ff first
#define ss second

ll n,a[5010],b[5010];
double p[5010][20];

int main(){
    fastio;
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    sort(a+1,a+n);
    ll tmp = 1, cnt = 0;
    while(tmp<n){
        tmp *= 2;
        cnt += 1;
    }
    ll r = tmp-n;
    for(int i=0;i<r;i++){
        b[2*i] = a[i];
        b[2*i+1] = 0;
    }
    ll t = 2*r;
    for(int i=r;i<n;i++){
        b[t] = a[i];
        t++;
    }
    for(int i=0;i<tmp;i++){
        ll t = i/2;
        p[i][1] = 1.0*b[2*t+i%2]/(b[2*t]+b[2*t+1]);
    }
    ll tr = 2;
    for(int i=2;i<=cnt;i++){
        tr *= 2;
        for(int j=0;j<tmp;j++){
            if(b[j]==0) continue;
            double pr = 0;
            ll gr = j/tr;
            for(int k=gr*tr;k<(gr+1)*tr;k++){
                if(k/(tr/2)==j/(tr/2)) continue;
                pr += p[k][i-1]*b[j]/(b[j]+b[k]);
            }
            p[j][i] = pr*p[j][i-1];
        }
    }
    // for(int i=0;i<tmp;i++){
    //     for(int j=1;j<=cnt;j++){
    //         cout << p[i][j] << " ";
    //     }
    //     cout << "\n";
    // }
    cout << setprecision(10);
    cout << fixed << p[0][cnt];
}

NWERC 2017 Solutions

A. Ascending Photo

B. Boss Battle

C. Connect the Dots

D. Dunglish

E. English Restaurant

F. Factor-Free Tree

G. Glyph Recognition

H. High Score

I. Installing Apps

J. Juggling Troupe

K. Knockout Tournament

Further Reading

Persistent Segment Tree

Polygon Triangulation

Linear Programming and Duality