Link
- Codeforces Round #368 Div. 2 (Contest 707)
A. Brain’s Photos
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;
}
B. Bakery
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;
}
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;
}
C. Pythagorean Triples
Consider some cases to get answer.
If n>=3, there exists answer. And we can show one representative answer.
/*
*
*/
#include <cstdio>
#include <iostream>
typedef long long ll;
using namespace std;
int main(){
#ifndef ONLINE_JUDGE
freopen("c.in", "r", stdin);
#endif
ll n;
cin >> n;
if (n==1 || n==2) {
cout << -1 << endl;
return 0;
} else {
ll scale = 1;
while ((n&1)==0){
// even
if (n==4) {
cout << 3 * scale << " " << 5 * scale << endl;
return 0;
}
n >>= 1;
scale <<= 1;
}
// odd
ll b, c;
ll n2 = (n * n);
b = (n2 - 1) / 2;
c = (n2 + 1) / 2;
cout << b * scale << " " << c * scale << endl;
}
return 0;
}
D. Persistent Bookcase
- DFS with forward&backward operation
- Problem
This problem focuses how to make persistent data structures. I imagine the data management of git (branch) also works in similar way.
We cannot have all the time of book shelf state in the memory, so how to achive the operation 4 is the problem. We can do it by using Depth First Search, and after dfs we need to “rollback” the operation to get previous shelf state.
/*
* Ref: http://codeforces.com/submissions/ksun48 707D
* Use DFS
* forward & backward
*
* Use scanf, printf instead of cin, cout
* d2.cpp cin & cout: 717 ms 11500 KB
* d4.cpp 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;
}
Here I decided to use C scanf() and printf() function instead of C++ cin/cout function. Because I noticed there is quite a big difference in the speed. See below post for detail.