I'm getting WA #12 in this problem, what I do is take to points that are consecutive in the convex hull, then order all the other (N-2) points according to the measure of the angle we get of joining this point with the other two I chose at the beginning.

#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

struct point{
    long long x,y;
    long double ang;
    
    point(){}
    
    bool operator < (point X) const{
        return ang < X.ang;
    }
}P[5000];

bool ccw(point &A, point &B, point &C){
    return (A.x * B.y + B.x * C.y + C.x * A.y - A.y * B.x - B.y * C.x - C.y * A.x) >= 0;
}

long double dist(point &A, point &B){
    return sqrt((long double)(A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}

int main(){
    int N;
    
    cin >> N;
    
    for(int i = 0;i < N;++i)
        cin >> P[i].x >> P[i].y;
    
    for(int i = 1;i < N;++i)
        if(P[i].x < P[0].x)
            swap(P[0],P[i]);
    
    for(int i = 2;i < N;++i)
        if(ccw(P[0],P[1],P[i]))
            swap(P[1],P[i]);
    
    long double a,b,c = dist(P[0],P[1]);
    
    for(int i = 2;i < N;++i){
        a = dist(P[i],P[0]);
        b = dist(P[i],P[1]);
        
        P[i].ang = (a*a + b*b - c*c) / (2 * a * b);
    }
    
    sort(P + 2,P + N);
    
    cout << P[0].x << " " << P[0].y << endl;
    cout << P[1].x << " " << P[1].y << endl;
    cout << P[(N + 1) / 2].x << " " << P[(N + 1) / 2].y << endl;
    
    return 0;
}

I cant't understand the following example case

4 4 2
+ 1
+ 2
- 1
- 2
+ 2
+ 1
- 2
- 1

the answer is :-(

But if the first mage does all its four actions, and after that the second mage does
all its four actions, then there would be no problem. Why isn't this possible?

Edit:

Now I'm getting WA #5, basically what I do is fix the number of moves that both mages
could have done before none of them can perform an action.

#include <iostream>
#include <cstring>

using namespace std;

int main(){
    int T,n,m,k,val1[1000],val2[1000];
    int used[1001];
    char op1[1000],op2[1000];
    
    cin >> T;
    
    while(T--){
        cin >> n >> m >> k;
        
        for(int i = 0;i < n;++i) cin >> op1[i] >> val1[i];
        for(int i = 0;i < m;++i) cin >> op2[i] >> val2[i];
        
        bool found = false;
        
        for(int i = 0;i <= n;++i){
            memset(used,0,sizeof used);
            
            for(int j = 0;j < i;++j){
                if(op1[j] == '+') ++used[ val1[j] ];
                else --used[ val1[j] ];
            }
            
            bool valid = true;
            
            for(int j = 0;j <= m;++j){
                if(j > 0){
                    if(op2[j - 1] == '+') ++used[ val2[j - 1] ];
                    else --used[ val2[j - 1] ];
                    
                    if(used[ val2[j - 1] ] == 2 || used[ val2[j - 1] ] == -2) valid = false;
                }
                
                if(!valid) break;
                
                if(i < n && j < m && op1[i] == '+' && op2[j] == '+'){
                    if(used[ val1[i] ] > 0 && used[ val2[j] ] > 0)
                        found = true;
                }
            }
        }
        
        if(found) cout << ":-(" << endl;
        else cout << ":-)" << endl;
    }
    
    return 0;
}

Edit2: Finally got AC, after adding a counter that keeps the number of indices where
abs(used[i]) == 2. The state is possible to reach only if its value is zero.

Hi, I'm trying to solve this problem using binary search and range minimum query. However I'm getting RTE on test 15 (Finally found the error, AC now).

#include <cstdio>
#include <cstring>

using namespace std;

char s[1000001];
int sum[1000001],rmq[20][1000001],ind[20][1000001];

// want = 0 : value
// want = 1 : index
int solve(int s, int e, int want){
    int log = 0;
    
    while((1 << log) <= e-s+1) ++log;
    --log;
    
    if(rmq[log][s] < rmq[log][e - (1 << log) + 1]) return (want == 0? rmq[log][s] : ind[log][s]);
    return (want == 0? rmq[log][e - (1 << log) + 1] : ind[log][e - (1 << log) + 1]);
}

int main(){
    fgets(s,1000002,stdin);
    
    int L = strlen(s); --L;
    s[L] = 0;
    
    for(int i = 0;i < L;++i)
        sum[i + 1] = sum[i] + (s[i] == '('? 1 : -1);
    
    for(int i = 0;i <= L;++i){
        rmq[0][i] = sum[i];
        ind[0][i] = i;
    }
    
    for(int i = 1;i <= L;++i){
        rmq[0][i] = rmq[0][i - 1] + (s[i - 1] == '('? 1 : -1);
        ind[0][i] = i;
    }
    
    for(int l = 1,l2 = 2,j = 1;l2 <= L + 1;l <<= 1,l2 <<= 1,++j){
        for(int i = 0;i <= L;++i){
            if(i+l <= L){
                if(rmq[j-1][i] < rmq[j-1][i+l]){
                    rmq[j][i] = rmq[j-1][i];
                    ind[j][i] = ind[j-1][i];
                }else{
                    rmq[j][i] = rmq[j-1][i+l];
                    ind[j][i] = ind[j-1][i+l];
                }
            }else{
                rmq[j][i] = rmq[j-1][i];
                ind[j][i] = ind[j-1][i];
            }
        }
    }
    
    int ans = 0,cont = 1;
    
    for(int i = 0;i+1 < L;++i){
        if(s[i] == '('){
            int lo = i+1,hi = L,mi;
            
            while(lo != hi){
                mi = (lo + hi + 1) / 2;
                
                if(solve(i+1,mi,0) < rmq[0][i]) hi = mi - 1;
                else lo = mi;
            }
            
            lo = solve(i+1,lo,1);
            
            if(lo > i+1 && rmq[0][lo] == rmq[0][i]){
                int l = lo - i;
                
                if(ans == l) ++cont;
                else if(ans < l){
                    ans = l;
                    cont = 1;
                }
            }
        }
    }
    
    printf("%d %d\n",ans,cont);
    
    return 0;
}

I'm trying to solve this problem using a trie, but I keep getting TLE. The algorithm's complexity is O(L²), so it should pass. Any suggestion about what could be going wrong?

#include <cstdio>
#include <cstring>
#include <vector>
#include <string>

using namespace std;

char s[1001];
int L,best,found[1000];
vector<int> poss;

struct node{
    int cont;
    node *link[4];
    
    node(){
        cont = 0;
        
        for(int i = 0;i < 4;++i)
            link[i] = NULL;
    }
};

struct trie{
    node *root;
    
    trie(){
        root = new node();
    }
    
    void insert(int pos){
        node *p = root;
        string aux;
        
        for(int i = pos,nxt;i < L;++i){
            aux += s[i];
            
            if(s[i] == 'A') nxt = 0;
            else if(s[i] == 'C') nxt = 1;
            else if(s[i] == 'G') nxt = 2;
            else nxt = 3;
            
            if(p->link[nxt] == NULL) p->link[nxt] = new node();
            p = p->link[nxt];
            ++p->cont;
            
            if(p->cont > 1){
                if(i-pos+1 > best){
                    poss.clear();
                    best = i-pos+1;
                }
                
                if(i-pos+1 == best){
                    poss.push_back(pos);
                    found[pos] = p->cont;
                }
            }
        }
    }
};

int main(){
    int TC;
    
    scanf("%d",&TC);
    
    while(TC--){
        scanf("%s",s);
        
        L = strlen(s);
        best = -1;
        
        trie *T;
        T = new trie();
        poss.clear();
        
        for(int i = 0;i < L;++i)
            T->insert(i);
        
        delete(T);
        
        if(best == -1) puts("No repetitions found!");
        else{
            string ans = "Z";
            int ind,sz = poss.size();
            
            for(int i = 0;i < sz;++i){
                int x = poss[i];
                string aux = string(s + x,s + (x+best));
                
                if(aux <= ans){
                    ans = aux;
                    ind = x;
                }
            }
            
            printf("%s %d\n",ans.c_str(),found[ind]);
        }
    }
    
    return 0;
}

Got AC, silly mistake =(

My approach works as follows:

I've come across the following task from z-trening (http://www.z-trening.com/tasks.php?show_task=5000000148). First I thought it would be easy with backtracking since sides where small. But I'm getting TLE in two cases, and when trying to solve a 5x5 square with all its squares empty it takes forever to solve it.

Is there a more efficient way to solve it or any useful heuristic?

This code passed 17/20 cases: http://pastie.org/2073017

This code passed 16/20 cases: http://pastie.org/2073028

AC solution: http://pastie.org/2073682

I'm trying to solve this problem with a greedy approach, first assign the number of students assigned to each classroom as to maximize the number of possible pairs. Then make sure that I have chosen a pair for each of them, and then just choose enough available pairs to complete the ones asked. However, I'm getting WA in test case 7, any idea of why this approach fails?

Now AC, my initial assignment was failing. For example: 10 3 5. Thanks to aropan.

#include <cstdio>
#include <cstring>
 
using namespace std;
 
int main(){
    int n,k,m;
    scanf("%d %d %d",&n,&k,&m);
    
    int cont[100];
    
    for(int i = 0,x = n/k;i < m;++i) cont[i] = x;
    for(int i = n % k - 1;i >= 0;--i) ++cont[i];
    
    int room[100];
    
    for(int i = 0,k = 0;i < m;++i)
        for(int j = 0;j < cont[i];++j)
            room[k++] = i;
    
    for(int i = 0;i < n;++i)
        printf("%d\n",room[i] + 1);
    
    bool M[100][100];
    memset(M,false,sizeof(M));
    
    for(int i = 0;i < n;++i)
        for(int j = i + 1;j < n;++j)
            M[i][j] = M[j][i] = (room[i] != room[j]);
    
    bool used[100];
    memset(used,false,sizeof(used));
    
    for(int i = 0;i < n;++i){
        if(!used[i]){
            for(int j = 0;j < n;++j){
                if(M[i][j] && !used[j]){
                    used[i] = true; used[j] = true;
                    M[i][j] = M[j][i] = false;
                    printf("%d %d\n",i + 1,j + 1);
                    --m;
                    break;
                }
            }
        }
        
        if(!used[i]){
            for(int j = 0;j < n;++j){
                if(M[i][j]){
                    used[i] = true;
                    M[i][j] = M[j][i] = false;
                    printf("%d %d\n",i + 1,j + 1);
                    --m;
                    break;
                }
            }
        }
    }
    
    for(int i = 0;i < n && m > 0;++i){
        for(int j = i + 1;j < n && m > 0;++j){
            if(M[i][j]){
                M[i][j] = M[j][i] = false;
                printf("%d %d\n",i + 1,j + 1);
                --m;
            }
        }
    }
    
    return 0;
}

Hope it can be useful to other people: