Monday, July 21, 2014

Codeforces Round #202 (Div. 1), problem: (A) Mafia solution

Codeforces Round #202 (Div. 1), problem: (A) Mafia: http://codeforces.com/problemset/problem/348/A

Codeforces Round #202 (Div. 1), problem: (A) Mafia editorial: http://codeforces.com/blog/entry/9031

Codeforces Round #202 (Div. 1), problem: (A) Mafia solution: http://ideone.com/JEoXON


#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
    long long int n, a, ma=0, cnt=0;
    scanf("%I64d", &n);
    for(int i=0; i<n; i++) {
        scanf("%I64d", &a);
        if(a>ma) ma=a;
        cnt+=a;
    }
    a=ceil((double)cnt/(n-1)), a=max(a, ma);
    printf("%I64d", a);
    return 0;
}

note, courtesy of baklazan: http://codeforces.com/blog/entry/9031#comment-147355

Let's say you're going to play x games. If someone wanted to play more than x games, he wouldn't be able to do so, so he would be unhappy. Therefore, if everyone is happy, x ≥ ai must hold for each i, so
x ≥ max(a1, a2, ..., an)
Let $b_i$ be number of games, where i-th player is supervisor and let ci be number of games, where he plays. In each game i-th player is playing, XOR supervising, so ci + bi = x. Also, he wants to play at least ai games, soai ≤ ci, thus bi ≤ ci + bi - ai, so bi ≤ x - ai.
Each game is supervised by one player, so x = b1 + b2 + ... + bn. Giving it all together:
x = b1 + b2 + ... + bn ≤ (x - a1) + (x - a2) + ... + (x - an)
Now we have two lower bounds for $x$ . Smallest x satisfying both of them is
This number of games is enough, because if first $x - a_1$ games are supervised by first player, next x - a2games are supervised by second player etc., until the x-th game, then everyone plays enough games and each game is supervised by someone.

Codeforces Round #228 (Div. 2), problem: (C) Fox and Box Accumulation solution

Codeforces Round #228 (Div. 2), problem: (C) Fox and Box Accumulation: http://codeforces.com/contest/389/problem/C

Codeforces Round #228 (Div. 2), problem: (C) Fox and Box Accumulation editorial: http://codeforces.com/blog/entry/10629

Codeforces Round #228 (Div. 2), problem: (C) Fox and Box Accumulation solution: http://ideone.com/AJ4sh5


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    int n, x[105], pl=0, cnt=0, b[105]={0};
    vector <int> v;
    scanf("%d", &n);
    for(int i=0; i<n; i++) scanf("%d", &x[i]);
    sort(x, x+n); 
    while(cnt<n) {
        pl++;
        for(int i=0; i<n; i++) if(x[i]>=v.size() && b[i]==0) v.push_back(x[i]), b[i]=1, cnt++;
        v.clear();
    }
    printf("%d", pl);
    return 0;
}


Sunday, July 20, 2014

TopCoder High School SRM 43 Level one - 250 pt - Transform Array solution

TopCoder High School SRM 43 Level one - 250 pt - Transform Array statement: http://community.topcoder.com/stat?c=problem_statement&pm=6692&rd=10792

TopCoder High School SRM 43 Level one - 250 pt - Transform Array editorial: http://community.topcoder.com/tc?module=Static&d1=hs&d2=match_editorials&d3=hs_srm43

TopCoder High School SRM 43 Level one - 250 pt - Transform Array solution: 


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class TransformArray {
    public: int doTransform(vector <int> a) {
        int cnt=0;
        sort(a.begin(), a.end());
        for(int i=1; i<a.size(); i++) cnt+=a[i-1], a[i]-=a[i-1], a[i-1]=0;
        return cnt;
    }
};

TopCoder High School SRM 42 Level one - 250 pt - Fancy GUI solution

TopCoder High School SRM 42 Level one - 250 pt - Fancy GUI statement: http://community.topcoder.com/stat?c=problem_statement&pm=7888&rd=10790

TopCoder High School SRM 42 Level one - 250 pt - Fancy GUI editorial: http://community.topcoder.com/tc?module=Static&d1=hs&d2=match_editorials&d3=hs_srm42

TopCoder High School SRM 42 Level one - 250 pt - Fancy GUI solution: 

#include <iostream>
#include <vector>

class FancyGUI{
    public: int totalDarkArea(int n, std::vector <int> x1, std::vector <int> y1, std::vector <int> x2, std::vector <int> y2) {
        int cnt=0, a[105][105]={0};
        for(int i=0; i<x1.size(); i++) for(int j=x1[i]; j<=x2[i]; j++) for(int k=y1[i]; k<=y2[i]; k++) a[j][k]++;
        for(int i=1; i<=100; i++) for(int j=1; j<=100; j++) if(a[i][j]<=n) cnt++;
        return 100*100-cnt;
    }
};

TopCoder High School SRM 41 Level one - 250 pt - Majority Element solution

TopCoder High School SRM 41 Level one - 250 pt - Majority Element statement: http://community.topcoder.com/stat?c=problem_statement&pm=8137&rd=10788

TopCoder High School SRM 41 Level one - 250 pt - Majority Element editorial: http://community.topcoder.com/tc?module=Static&d1=hs&d2=match_editorials&d3=hs_srm41

TopCoder High School SRM 41 Level one - 250 pt - Majority Element solution: 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class MajorityElement {
    public: int findMajorityElement(vector <int> a) {
        int cnt=1, idx=0;
        sort(a.begin(), a.end());
        for(int i=1; i<a.size(); i++) {
            if(a[i]==a[i-1]) {
                cnt++; 
                if(cnt>a.size()/2) { idx=i; break; }
            }
            else cnt=1, idx=0;
        }
        if(idx==0 && a.size()>1) return -1;
        else return a[idx];
    }
};


TopCoder High School SRM 40 Level one - 250 pt - Secretary solution and C++ vector reverse

TopCoder High School SRM 40 Level one - 250 pt - Secretary statement: http://community.topcoder.com/stat?c=problem_statement&pm=8055&rd=10784

TopCoder High School SRM 40 Level one - 250 pt - Secretary editorial: http://community.topcoder.com/tc?module=Static&d1=hs&d2=match_editorials&d3=hs_srm40

TopCoder High School SRM 40 Level one - 250 pt - Secretary solution: 


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Secretary {
    public: string wrongOrdering(vector <string> f) {
        string s;
        for(int i=0; i<f.size(); i++) reverse(f[i].begin(), f[i].end()); 
        sort(f.begin(), f.end());
        reverse(f[0].begin(), f[0].end());
        s=f[0];
        return s;
    }
};

C++ vector reverse: http://www.cplusplus.com/reference/algorithm/reverse/


Codeforces Round #257 (Div. 2), problem: (B) Jzzhu and Sequences solution

Codeforces Round #257 (Div. 2), problem: (B) Jzzhu and Sequences: http://codeforces.com/contest/450/problem/B

Codeforces Round #257 (Div. 2), problem: (B) Jzzhu and Sequences editorial: http://codeforces.com/blog/entry/13112

Codeforces Round #257 (Div. 2), problem: (B) Jzzhu and Sequences solution: http://ideone.com/Eh6hpS


#include <iostream>
#include <cstdio>
using namespace std;

int main() {
    long long int x, y, z, n, tmp, a[7]={0}, ans;
    const int md=1e9+7;
    scanf("%I64d%I64d", &x, &y);
    scanf("%I64d", &n);
    z=y-x, a[1]=x, a[2]=y;
    for(int i=3; i<=6; i++) {
        tmp=x, x=y, y=z, z=y-x, a[i%6]=y;
    }
    if(a[n%6]>=0) printf("%I64d", a[n%6]%md);
    else printf("%I64d", (md+a[n%6]%md)%md);
    return 0;
}

note: to learn about mod operation on negative numbers: http://math.stackexchange.com/questions/519845/modulo-of-a-negative-number