Codeforces Round #373 Div. 2 review

Updated on September 26, 2016 by corochann · Leave a comment

Link Codeforces Round #373 Div. 2 (Contest 719) A. Vitya in the Countryside Problem Basically, check last 2 character to determine its direction is “UP” or “DOWN”. Special case comes when the last number is 0 or 15, in that case the direction changes and you can determine the direction without looking second last character.

#include <cstdio>
#include <iostream>

using namespace std;

int a[100];

int main(){
#ifndef ONLINE_JUDGE
    freopen("a3.in", "r", stdin);
#endif
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }
    if (n >= 2) {
        if (a[n-1] == 15) {
            printf("DOWN\n");
        } else if (a[n-1] == 0) {
            printf("UP\n");
        } else {
            if (a[n-1] > a[n-2]) {
                printf("UP\n");
            } else {
                printf("DOWN\n");
            }
        }
    } else if (n == 1) {
        if (a[n-1] == 15) {
            printf("DOWN\n");
        } else if (a[n-1] == 0) {
            printf("UP\n");
        } else {
            printf("-1\n");
        }
    }
    return 0;
}

#include <cstdio>

#include <iostream>

using namespace std;

int a[100];

int main(){

#ifndef ONLINE_JUDGE

freopen("a3.in", "r", stdin);

#endif

int n;

scanf("%d", &n);

for (int i = 0; i < n; ++i) {

scanf("%d", &a[i]);

}

if (n >= 2) {

if (a[n-1] == 15) {

printf("DOWN\n");

} else if (a[n-1] == 0) {

printf("UP\n");

} else {

if (a[n-1] > a[n-2]) {

printf("UP\n");

} else {

printf("DOWN\n");

}

} else if (n == 1) {

if (a[n-1] == 15) {

printf("DOWN\n");

} else if (a[n-1] == 0) {

printf("UP\n");

} else {

printf("-1\n");

}

return 0;

}

B. Anatoly and Cockroaches Problem We can consider 2 patterns for final alignment. Pattern 0 is to align “rbrbrb…” and pattern 1 is to align “brbrbr…”. We will compare the original alignment and final alignment. For each position i, we need to change the color to… Case A: r to b Case B: b to r If […]

Continue reading →

Codeforces Round #368 Div. 2 review

Updated on September 2, 2016 by corochann · Leave a comment

Link Codeforces Round #368 Div. 2 (Contest 707) A. Brain’s Photos Problem Just need to check if color (Cyan, Magenta or Yellow) exists or not in the photo.

#include <cstdio>
#include <iostream>

using namespace std;

int main(){
#ifndef ONLINE_JUDGE
    freopen("a3.in", "r", stdin);
#endif
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            char c;
            cin >> c;
            if (c == 'C' || c == 'M' || c == 'Y') {
                cout << "#Color" << endl;
                return 0;
            }
        }
    }
    cout << "#Black&White" << endl;
    return 0;
}

#include <cstdio>

#include <iostream>

using namespace std;

int main(){

#ifndef ONLINE_JUDGE

freopen("a3.in", "r", stdin);

#endif

int n, m;

cin >> n >> m;

for (int i = 0; i < n; ++i) {

for (int j = 0; j < m; ++j) {

char c;

cin >> c;

if (c == 'C' || c == 'M' || c == 'Y') {

cout << "#Color" << endl;

return 0;

}

cout << "#Black&White" << endl;

return 0;

}

B. Bakery Problem The problem sentence looks long, but after summarize, you just need to find the path between flour storage city and non flour storage city with minimum distance. But to find out these city path, I was using vector which is not fast enough and I got TLE during contest.

/*
 *
 */
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>

#define INF (1e9+5)
using namespace std;

int u[100005];
int v[100005];
int l[100005];
vector<int> s;

// ---> TLE, find takes O(N) time, too long.
bool contain(vector<int> s, int a) {
    return find(s.begin(), s.end(), a) != s.end();
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("b3.in", "r", stdin);
#endif
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 0; i < m; ++i) {
        cin >> u[i] >> v[i] >> l[i];
    }
    for (int i = 0; i < k; ++i) {
        int si;
        cin >> si;
        s.push_back(si);
    }

    int ans = INF;
    for (int i = 0; i < m; ++i) {
        if ((contain(s, u[i]) && !contain(s, v[i]))
            || (!contain(s, u[i]) && contain(s, v[i]))){
            ans = min(ans, l[i]);
        }
    }

    if (ans == INF) {
        cout << -1 << endl;
    } else {
        cout << ans << endl;
    }
    return 0;
}

#include <cstdio>

#include <iostream>

#include <vector>

#include <algorithm>

#define INF (1e9+5)

using namespace std;

int u[100005];

int v[100005];

int l[100005];

vector<int> s;

// ---> TLE, find takes O(N) time, too long.

bool contain(vector<int> s, int a) {

return find(s.begin(), s.end(), a) != s.end();

}

int main(){

#ifndef ONLINE_JUDGE

freopen("b3.in", "r", stdin);

#endif

int n, m, k;

cin >> n >> m >> k;

for (int i = 0; i < m; ++i) {

cin >> u[i] >> v[i] >> l[i];

}

for (int i = 0; i < k; ++i) {

int si;

cin >> si;

s.push_back(si);

}

int ans = INF;

for (int i = 0; i < m; ++i) {

if ((contain(s, u[i]) && !contain(s, v[i]))

|| (!contain(s, u[i]) && contain(s, v[i]))){

ans = min(ans, l[i]);

}

if (ans == INF) {

cout << -1 << endl;

} else {

cout << ans << endl;

}

return 0;

}

We can make search fast, in constant time by using Array to set a type of city.

/*
 * Previously, citytype was checked by vector, it takes O(n) to check i-th city type.
 * Now, use citytype Array to check the city type. this is O(1).
 */
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>

#define INF (1e9+5)
using namespace std;

int u[100005];
int v[100005];
int l[100005];
int citytype[100005];  // 0: no storage, 1: storage

int main(){
#ifndef ONLINE_JUDGE
    freopen("b.in", "r", stdin);
#endif
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 0; i < m; ++i) {
        cin >> u[i] >> v[i] >> l[i];
    }
    for (int i = 0; i < k; ++i) {
        int si;
        cin >> si;
        citytype[si] = 1;
    }

    int ans = INF;
    for (int i = 0; i < m; ++i) {
        if (citytype[u[i]] != citytype[v[i]]){ // <--- Use array, O(1).
            ans = min(ans, l[i]);
        }
    }

    if (ans == INF) {
        cout << -1 << endl;
    } else {
        cout << ans << endl;
    }
    return 0;
}

* Previously, citytype was checked by vector, it takes O(n) to check i-th city type.

* Now, use citytype Array to check the city type. this is O(1).

#include <cstdio>

#include <iostream>

#include <vector>

#include <algorithm>

#define INF (1e9+5)

using namespace std;

int u[100005];

int v[100005];

int l[100005];

int citytype[100005]; // 0: no storage, 1: storage

int main(){

#ifndef ONLINE_JUDGE

freopen("b.in", "r", stdin);

#endif

int n, m, k;

cin >> n >> m >> k;

for (int i = 0; i < m; ++i) {

cin >> u[i] >> v[i] >> l[i];

}

for (int i = 0; i < k; ++i) {

int si;

cin >> si;

citytype[si] = 1;

}

int ans = INF;

for (int i = 0; i < m; ++i) {

if (citytype[u[i]] != citytype[v[i]]){ // <--- Use array, O(1).

ans = min(ans, l[i]);

}

if (ans == INF) {

cout << -1 << endl;

} else {

cout << ans << endl;

}

return 0;

}

C. Pythagorean Triples Problem Consider some cases to […]

Continue reading →

scanf and printf are much faster than cin and cout

Updated on September 2, 2016 by corochann · 1 Comment

When I’m solving the Codeforces problem, 707D. Persistent Bookcase, I made some comparison for the performance of I/O function. scanf() and printf() cin >> and cout << Test Let’s start from C++ common way, below code uses cin >> and cout <<

/*
 * Ref: http://codeforces.com/submissions/ksun48 707D
 * Use DFS
 * forward & backward
 *
 * Accepted	748 ms	11500 KB
 */
#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

int n, m;
int a[100005], b[100005], c[100005];
int ans[100005];

bool shelf[1005][1005];
int count_shelf[1005];
int total_count = 0;

vector<int> children[100005]; // children[i] : child of i-th operation = next operation

void dfs(int q) { // now at q-th operation
    ans[q] = total_count;
    //cout << "debug q = " << q << ", ans[q] = " << ans[q] << endl;

    for (int i = 0; i < children[q].size(); ++i) {
        int curq = children[q][i];

        /* Forward, Apply q-th operation */
        bool changed = false;
        switch (a[curq]) {
            case 1:
                if (!shelf[b[curq]][c[curq]]) {
                    count_shelf[b[curq]]++;
                    total_count++;
                    shelf[b[curq]][c[curq]] = true;
                    changed = true;
                }
                break;
            case 2:
                if (shelf[b[curq]][c[curq]]) {
                    count_shelf[b[curq]]--;
                    total_count--;
                    shelf[b[curq]][c[curq]] = false;
                    changed = true;
                }
                break;
            case 3:
                for (int j = 0; j < m; ++j) {
                    shelf[b[curq]][j] = !shelf[b[curq]][j];
                }
                total_count += m - 2 * count_shelf[b[curq]];
                count_shelf[b[curq]] = m - count_shelf[b[curq]];
                break;
            case 4:
                // jumped from q to curq, do nothing
                break;
        }

        dfs(curq);

        /* Backward Rollback q-th operation.
         * changed flag, set at forward operation, is used.  */
        switch (a[curq]) {
            case 1:
                if (changed) {
                    count_shelf[b[curq]]--;
                    total_count--;
                    shelf[b[curq]][c[curq]] = false;
                }
                break;
            case 2:
                if (changed) {
                    count_shelf[b[curq]]++;
                    total_count++;
                    shelf[b[curq]][c[curq]] = true;
                }
                break;
            case 3:
                for (int j = 0; j < m; ++j) {
                    shelf[b[curq]][j] = !shelf[b[curq]][j];
                }
                total_count += m - 2 * count_shelf[b[curq]];
                count_shelf[b[curq]] = m - count_shelf[b[curq]];
                break;
            case 4:
                // do nothing and go back from curq to q
                break;
        }
        //cout << "debug after rollback q = " << q << ", ans[q] = " << ans[q] << endl;
    }
}


int main(){
#ifndef ONLINE_JUDGE
    freopen("d4.in", "r", stdin);
#endif
    //vector<int> v;
    int q;
    cin >> n >> m >> q;
    for (int i = 1; i <= q; ++i) {
        cin >> a[i];
        if (a[i]==1 || a[i]==2) {
            cin >> b[i] >> c[i];
            b[i]--;
            c[i]--;
        } else {
            cin >> b[i];
            if (a[i]==3) {
                b[i]--;
            }
        }

        /* Create DFS tree */
        if (a[i]==4) {
            // i-th operation is 4
            children[b[i]].push_back(i);
        } else {
            children[i-1].push_back(i);
        }
    }

    dfs(0);

    for (int i = 1; i <= q; ++i) {
        cout << ans[i] << endl;
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

* Ref: http://codeforces.com/submissions/ksun48 707D

* Use DFS

* forward & backward

* Accepted 748 ms 11500 KB

#include <cstdio>

#include <iostream>

#include <cstring>

#include <vector>

using namespace std;

int n, m;

int a[100005], b[100005], c[100005];

int ans[100005];

bool shelf[1005][1005];

int count_shelf[1005];

int total_count = 0;

vector<int> children[100005]; // children[i] : child of i-th operation = next operation

void dfs(int q) { // now at q-th operation

ans[q] = total_count;

//cout << "debug q = " << q << ", ans[q] = " << ans[q] << endl;

for (int i = 0; i < children[q].size(); ++i) {

int curq = children[q][i];

/* Forward, Apply q-th operation */

bool changed = false;

switch (a[curq]) {

case 1:

if (!shelf[b[curq]][c[curq]]) {

count_shelf[b[curq]]++;

total_count++;

shelf[b[curq]][c[curq]] = true;

changed = true;

}

break;

case 2:

if (shelf[b[curq]][c[curq]]) {

count_shelf[b[curq]]--;

total_count--;

shelf[b[curq]][c[curq]] = false;

changed = true;

}

break;

case 3:

for (int j = 0; j < m; ++j) {

shelf[b[curq]][j] = !shelf[b[curq]][j];

}

total_count += m - 2 * count_shelf[b[curq]];

count_shelf[b[curq]] = m - count_shelf[b[curq]];

break;

case 4:

// jumped from q to curq, do nothing

break;

}

dfs(curq);

/* Backward Rollback q-th operation.

* changed flag, set at forward operation, is used. */

switch (a[curq]) {

case 1:

if (changed) {

count_shelf[b[curq]]--;

total_count--;

shelf[b[curq]][c[curq]] = false;

}

break;

case 2:

if (changed) {

count_shelf[b[curq]]++;

total_count++;

shelf[b[curq]][c[curq]] = true;

}

break;

case 3:

for (int j = 0; j < m; ++j) {

shelf[b[curq]][j] = !shelf[b[curq]][j];

}

total_count += m - 2 * count_shelf[b[curq]];

count_shelf[b[curq]] = m - count_shelf[b[curq]];

break;

case 4:

// do nothing and go back from curq to q

break;

}

//cout << "debug after rollback q = " << q << ", ans[q] = " << ans[q] << endl;

}

int main(){

#ifndef ONLINE_JUDGE

freopen("d4.in", "r", stdin);

#endif

//vector<int> v;

int q;

cin >> n >> m >> q;

for (int i = 1; i <= q; ++i) {

cin >> a[i];

if (a[i]==1 || a[i]==2) {

cin >> b[i] >> c[i];

b[i]--;

c[i]--;

} else {

cin >> b[i];

if (a[i]==3) {

b[i]--;

}

/* Create DFS tree */

if (a[i]==4) {

// i-th operation is 4

children[b[i]].push_back(i);

} else {

children[i-1].push_back(i);

}

dfs(0);

for (int i = 1; i <= q; ++i) {

cout << ans[i] << endl;

}

return 0;

}

It took 748 ms. Next, (old-school,) C way of implementation using scanf() and printf()

/*
 * Ref: http://codeforces.com/submissions/ksun48 707D
 * Use DFS
 * forward & backward
 *
 * Use scanf, printf instead of cin, cout
 * scanf & printf: 171 ms	11500 KB --> The difference is super huge. Use scanf & printf.
 */
#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

int n, m;
int a[100005], b[100005], c[100005];
int ans[100005];

bool shelf[1005][1005];
int count_shelf[1005];
int total_count = 0;

vector<int> children[100005]; // children[i] : child of i-th operation = next operation

void dfs(int q) { // now at q-th operation
    ans[q] = total_count;
    //cout << "debug q = " << q << ", ans[q] = " << ans[q] << endl;

    for (int i = 0; i < children[q].size(); ++i) {
        int curq = children[q][i];

        /* Forward, Apply q-th operation */
        bool changed = false;
        switch (a[curq]) {
            case 1:
                if (!shelf[b[curq]][c[curq]]) {
                    count_shelf[b[curq]]++;
                    total_count++;
                    shelf[b[curq]][c[curq]] = true;
                    changed = true;
                }
                break;
            case 2:
                if (shelf[b[curq]][c[curq]]) {
                    count_shelf[b[curq]]--;
                    total_count--;
                    shelf[b[curq]][c[curq]] = false;
                    changed = true;
                }
                break;
            case 3:
                for (int j = 0; j < m; ++j) {
                    shelf[b[curq]][j] = !shelf[b[curq]][j];
                }
                total_count += m - 2 * count_shelf[b[curq]];
                count_shelf[b[curq]] = m - count_shelf[b[curq]];
                break;
            case 4:
                // jumped from q to curq, do nothing
                break;
        }

        dfs(curq);

        /* Backward Rollback q-th operation.
         * changed flag, set at forward operation, is used.  */
        switch (a[curq]) {
            case 1:
                if (changed) {
                    count_shelf[b[curq]]--;
                    total_count--;
                    shelf[b[curq]][c[curq]] = false;
                }
                break;
            case 2:
                if (changed) {
                    count_shelf[b[curq]]++;
                    total_count++;
                    shelf[b[curq]][c[curq]] = true;
                }
                break;
            case 3:
                for (int j = 0; j < m; ++j) {
                    shelf[b[curq]][j] = !shelf[b[curq]][j];
                }
                total_count += m - 2 * count_shelf[b[curq]];
                count_shelf[b[curq]] = m - count_shelf[b[curq]];
                break;
            case 4:
                // do nothing and go back from curq to q
                break;
        }
        //cout << "debug after rollback q = " << q << ", ans[q] = " << ans[q] << endl;
    }
}


int main(){
#ifndef ONLINE_JUDGE
    freopen("d4.in", "r", stdin);
#endif
    //vector<int> v;
    int q;
    scanf("%d %d %d", &n, &m, &q);
    for (int i = 1; i <= q; ++i) {
        scanf("%d", &a[i]);
        if (a[i]==1 || a[i]==2) {
            scanf("%d %d", &b[i], &c[i]);
            b[i]--;
            c[i]--;
        } else {
            scanf("%d", &b[i]);
            if (a[i]==3) {
                b[i]--;
            }
        }

        /* Create DFS tree */
        if (a[i]==4) {
            // i-th operation is 4
            children[b[i]].push_back(i);
        } else {
            children[i-1].push_back(i);
        }
    }

    dfs(0);

    for (int i = 1; i <= q; ++i) {
        printf("%d\n", ans[i]);
        //cout << ans[i] << endl;
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

* Ref: http://codeforces.com/submissions/ksun48 707D

* Use DFS

* forward & backward

* Use scanf, printf instead of cin, cout

* scanf & printf: 171 ms 11500 KB --> The difference is super huge. Use scanf & printf.

#include <cstdio>

#include <iostream>

#include <cstring>

#include <vector>

using namespace std;

int n, m;

int a[100005], b[100005], c[100005];

int ans[100005];

bool shelf[1005][1005];

int count_shelf[1005];

int total_count = 0;

vector<int> children[100005]; // children[i] : child of i-th operation = next operation

void dfs(int q) { // now at q-th operation

ans[q] = total_count;

//cout << "debug q = " << q << ", ans[q] = " << ans[q] << endl;

for (int i = 0; i < children[q].size(); ++i) {

int curq = children[q][i];

/* Forward, Apply q-th operation */

bool changed = false;

switch (a[curq]) {

case 1:

if (!shelf[b[curq]][c[curq]]) {

count_shelf[b[curq]]++;

total_count++;

shelf[b[curq]][c[curq]] = true;

changed = true;

}

break;

case 2:

if (shelf[b[curq]][c[curq]]) {

count_shelf[b[curq]]--;

total_count--;

shelf[b[curq]][c[curq]] = false;

changed = true;

}

break;

case 3:

for (int j = 0; j < m; ++j) {

shelf[b[curq]][j] = !shelf[b[curq]][j];

}

total_count += m - 2 * count_shelf[b[curq]];

count_shelf[b[curq]] = m - count_shelf[b[curq]];

break;

case 4:

// jumped from q to curq, do nothing

break;

}

dfs(curq);

/* Backward Rollback q-th operation.

* changed flag, set at forward operation, is used. */

switch (a[curq]) {

case 1:

if (changed) {

count_shelf[b[curq]]--;

total_count--;

shelf[b[curq]][c[curq]] = false;

}

break;

case 2:

if (changed) {

count_shelf[b[curq]]++;

total_count++;

shelf[b[curq]][c[curq]] = true;

}

break;

case 3:

for (int j = 0; j < m; ++j) {

shelf[b[curq]][j] = !shelf[b[curq]][j];

}

total_count += m - 2 * count_shelf[b[curq]];

count_shelf[b[curq]] = m - count_shelf[b[curq]];

break;

case 4:

// do nothing and go back from curq to q

break;

}

//cout << "debug after rollback q = " << q << ", ans[q] = " << ans[q] << endl;

}

int main(){

#ifndef ONLINE_JUDGE

freopen("d4.in", "r", stdin);

#endif

//vector<int> v;

int q;

scanf("%d %d %d", &n, &m, &q);

for (int i = 1; i <= q; ++i) {

scanf("%d", &a[i]);

if (a[i]==1 || a[i]==2) {

scanf("%d %d", &b[i], &c[i]);

b[i]--;

c[i]--;

} else {

scanf("%d", &b[i]);

if (a[i]==3) {

b[i]--;

}

/* Create DFS tree */

if (a[i]==4) {

// i-th operation is 4

children[b[i]].push_back(i);

} else {

children[i-1].push_back(i);

}

dfs(0);

for (int i = 1; i <= q; ++i) {

printf("%d\n", ans[i]);

//cout << ans[i] << endl;

}

return 0;

}

It took only 171 ms. Result function time scanf() and printf() 171 ms cin >> and cout << 748 ms In this experiment, it appears that the speed of cin and cout is much much slower than scanf() and printf(), the difference is indeed quite huge. The overhead of cin and cout took more than 500 ms! You might get a […]

Continue reading →

corochannNote

Month: September 2016

Codeforces Round #373 Div. 2 review

Codeforces Round #368 Div. 2 review

scanf and printf are much faster than cin and cout