MarioYC's blog

By MarioYC, 13 years ago, In English
Link

This problems asks that given the indices of the resulting suffix array of a string, we must find some string which gives us this result.

I would appreciate some hint for this problem, maybe some greedy algorithm works :)

Full text and comments »

  • Vote: I like it
  • +3
  • Vote: I do not like it

By MarioYC, 13 years ago, In English
Hi, I found this contest http://judge.mipt.ru/cgi-bin/new-client?contest_id=201112 announced in the russian interface, however I'm having troubles understanding some statements. I would appreciate if someone could help me understand them.

-------

Problem count-Считалочка

Считалочка

Time limit = 1

Игра "Считалочка" заключается в следующем. N человек (мы пронумеруем их числами 1, 2, ... N) встают в круг и начинают считать с первого по кругу. Каждый M-ый выходит из круга. Один человек, который останется, считается победителем. Если N = 6, а M = 5, то будут выходить 5, 4, 6, 2, 3 и останется игрок с номером 1.

У нас N человек разбиты на две команды по K человек. Первые K принадлежат первой команде, следующие K — второй команде. Вам нужно найти такое минимальное M, что в игре "Считалочка" сначала выйдут все игроки второй команды, прежде, чем какой-либо игрок первой команды

I understand in the second paragraph that N = 2K, but I don't understand what is the condition these two groups of K people must fulfill when I choose M.

-------

Problem graph-game

Алиса и Боб играют в игру со следующими правилами. В начале есть граф без ребер на N вершинах. Каждым ходом игроки соединяют ребром две вершины, которые до сих не были соединены (т.е. кратных ребер не бывает). Игрок, после чьего хода граф становится связным проигрывает. Первым ходит Боб.

Here I don't understand if we can connect two vertices only when they are not on the same connected component or when there is not an edge between them.
-------

Full text and comments »

  • Vote: I like it
  • -1
  • Vote: I do not like it

By MarioYC, 13 years ago, In English

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;
}

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By MarioYC, 13 years ago, In English
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.

Full text and comments »

  • Vote: I like it
  • +4
  • Vote: I do not like it

By MarioYC, 13 years ago, In English
I tried to solve this problem using Binary Index Tree and Binary Search, also I used coordinate compression, keeping the positions in which I made a delete operation. Then I do Binary Search over the function

(x - (number of deleted which are less or equal than x))

the problem is that when I've deleted a number twice the function won't be motonous, hence the Binary Search fails.

Is there other way to solve it with BIT?

Full text and comments »

  • Vote: I like it
  • +2
  • Vote: I do not like it

By MarioYC, 13 years ago, In English
I was looking at solution 810236 from hpfdf and also other users, who only for every query "add l r d" do a for loop from l to r and make at most two update operations in a BIT.

Why does this work? I think something like this would do more than 109 operations.

Full text and comments »

  • Vote: I like it
  • +3
  • Vote: I do not like it

By MarioYC, 13 years ago, In English
If search for "codeforces beta round #5", I think my previous post should be found, but instead it says no results matched. Also, in the same post if I press the click the tag "codeforces beta round #5" i also get no result.

Is this not working? or maybe I'm not getting what it should do.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By MarioYC, 13 years ago, In English

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).


First, I consider '(' = +1 and ')' = -1 and calculate an array of accumulated sums, so when I want to find the longest regular sequence starting at some '(' at position s and the longest possible ending position will be e, we must have sum[i] >= sum[s] for every i such that s < i <= e+1, I find the maximum e where this is true using binary search and RMQ, since it is possible that sum[e+1] > sum[s]. I change e to the position where the minimum occurs and check that sum[e+1] = sum[s].

#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;
}

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By MarioYC, 13 years ago, In English
Any idea about how to solve http://acm.tju.edu.cn/toj/showp2463.html ?
I guess dp approach doesn't work here.

Full text and comments »

Tags lcs
  • Vote: I like it
  • 0
  • Vote: I do not like it

By MarioYC, 13 years ago, In English
I'm trying to solve this problem, however I'm getting WA on test 15. I first handle cases where a = 0 or b = 0, then solve a != 0 and b != 0 by using extended euclid algorithm to calculate k = -a^{-1}c (mod b), which replaced in the equation gives me to inequalities.

#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

struct EuclidReturn{
    long long u,v,d;
    
    EuclidReturn(long long _u, long long _v, long long _d){
        u = _u; v = _v; d = _d;
    }
};

EuclidReturn Extended_Euclid(long long a, long long b){
    if(b == 0) return EuclidReturn(1,0,a);
    EuclidReturn aux = Extended_Euclid(b,a % b);
    long long v = aux.u - (a / b) * aux.v;
    return EuclidReturn(aux.v,v,aux.d);
}

long long modular_inverse(int a, int n){
    EuclidReturn  aux = Extended_Euclid(a,n);
    return ((aux.u / aux.d) % n + n) % n;
}

long long solve(int a, int b, int c, int x1, int x2, int y1, int y2){
    if(x1 > x2 || y1 > y2) return 0;    
    
    if(a == 0 && b == 0){
        if(c == 0) return (long long)(x2 - x1 + 1) * (y2 - y1 + 1);
        return 0;
    }
    
    if(a == 0){
        if(c % b == 0 && y1 <= -c/b && -c/b <= y2) return x2 - x1 + 1;
        return 0;
    }
    
    if(b == 0){
        if(c % a == 0 && x1 <= -c/a && -c/a <= x2) return y2 - y1 + 1;
        return 0;
    }
    
    int g = __gcd(abs(a),abs(b));
    
    if(c % g != 0) return 0;
    
    a /= g; b /= g; c /= g;
    
    if(b < 0){
        a = -a;
        b = -b;
        c = -c;
    }
    
    long long k = modular_inverse((a % b + b) % b,b) * ((-c % b + b) % b) % b;
    long long k2 = (a*k + c) / b;
    long long L1 = ceil((double)(x1 - k) / b),U1 = floor((double)(x2 - k) / b),L2,U2;
    
    if(a < 0){
        L2 = ceil((double)(y1 + k2) / (-a));
        U2 = floor((double)(y2 + k2) / (-a));
    }else{
        L2 = ceil((double)(-k2 - y2) / a);
        U2 = floor((double)(-k2 - y1) / a);
    }
    
    return max(0LL,min(U1,U2) - max(L1,L2) + 1);
}

int main(){
    int a,b,c,x1,x2,y1,y2;
    
    scanf("%d %d %d %d %d %d %d",&a,&b,&c,&x1,&x2,&y1,&y2);
    printf("%lld\n",solve(a,b,c,x1,x2,y1,y2));
    
    return 0;
}


Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By MarioYC, 13 years ago, In English
A graph where the degrees of the vertices are 1 or 2, consists of only paths and cycles.

I know at least one problem where this turns out to be very useful:
Do you guys know other problems?

Full text and comments »

  • Vote: I like it
  • -14
  • Vote: I do not like it

By MarioYC, 13 years ago, In English

I'm trying to solve this problem using a trie, but I keep getting TLE. The algorithm's complexity is O(L2), 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;
}

Full text and comments »

  • Vote: I like it
  • +5
  • Vote: I do not like it

By MarioYC, 13 years ago, In English

Got AC, silly mistake =(

My approach works as follows:


  • For every operation, get all the sub-rectangles affected and save all these operations (function add)
  • Since M < 50, use grid compression
  • Count the number of 0's that there were initially in a sub-rectangle (function count), if the state of the bulbs changed add the number of 0's else add the number of 1's.
Code: http://pastie.org/2125732

Full text and comments »

  • Vote: I like it
  • +1
  • Vote: I do not like it

By MarioYC, 13 years ago, In English

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

Full text and comments »

  • Vote: I like it
  • +5
  • Vote: I do not like it

By MarioYC, 13 years ago, In English

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;
}

Full text and comments »

  • Vote: I like it
  • +1
  • Vote: I do not like it

By MarioYC, 13 years ago, In English
  • Vote: I like it
  • +12
  • Vote: I do not like it