I solved 4 problems, and got "time limit exceed" on problem E.
After the contest, I looked at codes of other contestants who passed problem E, and realized they used the same algorithm that I used.
It was how I implemented my algorithm that made me fail problem E.
People who passed used (in C++)
1. scanf to read input
2. printf to write output
3. Used arrays to hold data
I used (also in C++)
1. cin to read input
2. cout to write read output
3. vector to hold data.
I googled, and found out that
1. cin and cout are slower than scanf and printf
Because cin and cout use streams (note that we have to include #<iostream> to use them. iostream = input/output stream), they are slower than scanf and printf, which are plain standard input/output (#include <cstdio>).
In real life, safety is important and therefore streams are preferred,
but during algorithm contest where speed is crucial, scanf and printf are better choices.
2. vector can be slower than array
Certain methods of vector in STL are AMORTIZED O(1), meaning they are not O(1) in certain cases.
For example, push_back method is O(n) when the current vector hits its capacity limit and resizing should happen.
So if you know the maximum size of input, it is better to initialize your array to the maximum length instead of making an empty vector and dynamically change its length.
Maybe these facts are old news, but me being a newbie and still fairly new to algorithm contests, these were surprising to me. After experimenting with my code, I found out that using arrays instead of vectors could have made my code pass problem E.
I linked each problem title to its problem statement (e.g. clicking Problem E - Zebra Tower will lead you to its problem statement).
Problem E - Zebra Tower
Approach
We want to build maximum-height tower that meets following criteria.
1. Towers are made by stacking cubes, and only two colors of cubes are allowed in a tower. "
2. Colors of cube should be alternating.
The problem stated that "It is guaranteed that there are at least two cubes of different colors" , which means there is always an answer.
Before we try to figure out a way to find an answer, let's think about how an answer will look like first.
Terms & Definitions
Opt = an optimal answer, or a tower with the maximum-height (as the problem statement said, it is possible that there is more than one optimal answer).
bestA = collection of cubes of the same color that make Opt.
A = color of cubes in bestA
bestB = collection of cubes of the same color (, and not the same color as bestA) that make Opt.
B = color of cubes in bestB
Since colors of cubes should be alternating, 3 possible scenarios
1. bestA.size() == bestB.size()
2. bestA.size() == bestB.size() - 1
3. bestA.size() == bestB.size() + 1
In all three cases, the absolute difference of size of bestA and bestB do not exceed 1.
However, note that it is possible that there can be more cubes with color B, or color A that are not part of Opt.
For example, let's say there are 5 cubes of color A and 9 cubes of color B.Then we can only use 5 cubes of color A and 6 cubes of color B.
Let's call
A_all = number of all cubes of color A
B_all = number of all cubes of color B
For our convenience, let's assume that A_all <= B_all
This assumption is harmlessly because in case b_all > A_all, we can just swap color A and B to fit our observations.
Lemma 1. A_all = bestA .
If A_all != A.size(), it means there is Extra( = A_all - bestA.size()) number of cubes of color A that are not part of Opt. Since A_all <= B_all, it is possible to add those Extra number of A cubes. Because height of each cube is positive, this means it is possible to build a tower higher than Opt. It is a contradiction.
In other words, at least one of collection of cubes can use all of its cubes to build Opt.
Lemma 2. The E (>= 0) number of cubes of color B that are not part of B are the smallest cubes in B_all.
Assume the contrary :
B_ex = a cube with color B that is not part of Opt.
B_in = a cube with color B that is part of Opt.
And height of B_ex > height of B_in.
Let's swap B_ex and B_in : Take B_in out of Opt and put B_ex into Opt.
Than the height of Opt increase by the difference of height between B_ex and B_in, which means a tower higher than Opt exists.
This is a contradiction.
Algorithm
We will take advantage of observations we made about an optimal answer.
We will first group cubes by its color.
For each color group, we will assume that it is color group B in our assumption.
So for all possible height for the current group, we will build a tower by using all of cubes of one of other color groups.
Note.
I made some optimizations, like saving info on which color group can produce maximum height when you can use only "i" number of cubes.
I explained them in detail in my source code.
Source Code
1: #include <cstring>
2: #include <iostream>
3: #include <algorithm>
4:
5: #define maxN 100010
6: using namespace std;
7:
8: //Represents a cube
9: struct Cube
10: {
11: int color,height,idx;
12: };
13:
14: //Cubes with same color
15: struct CubeSet
16: {
17: int len;
18: int pos;
19: };
20:
21: Cube cubes[maxN];
22: CubeSet cs[maxN];
23: long long maxHeight[maxN]; //maxHeight[i] = The maximum height of a CubeSet using i cubes
24: int maxIdx[maxN]; //maxIdx[i] = The index of CubeSet that can produce maxHeight[i]
25: bool cubeSort(Cube , Cube);
26: bool colorSort(CubeSet, CubeSet);
27:
28: int main()
29: {
30: int N;
31: cin>>N;
32:
33: for(int i=0; i < N; i++)
34: {
35: cin>>cubes[i].color;
36: cin>>cubes[i].height;
37: cubes[i].idx = (i+1);
38: }
39:
40: sort(cubes, cubes + N, cubeSort);
41:
42: int colorLen = 0; //number of different cube colors
43: int j = 0;
44: int minH = maxN;
45:
46: for(int i=0; i < N; i=j)
47: {
48: //Save the position of the first cube of the current color
49: cs[colorLen].pos = i;
50:
51: for(j=i; j < N && cubes[j].color == cubes[i].color; j++)
52: cs[colorLen].len++;
53:
54: minH = min(minH, cs[colorLen].len);
55: colorLen++;
56: }
57:
58: sort(cs, cs + colorLen, colorSort);
59:
60: memset(maxHeight, 0, sizeof(maxHeight));
61: memset(maxIdx, 0, sizeof(maxIdx));
62:
63: long long ans = 0;
64: int bestA_idx, bestA_len, bestB_idx, bestB_len;
65: for(int i=0; i < colorLen; i++)
66: {
67: long long curH = 0; //total height of current color cubeses
68:
69: for(int j=0; j < minH-1; j++)
70: curH += cubes[cs[i].pos + j].height;
71:
72: for(int j = minH-1; j < cs[i].len; j++)
73: {
74: curH += cubes[cs[i].pos + j].height; //add the current cube
75:
76: //Try two possible heights
77: for(int k=j; k <= j+1; k++)
78: {
79: if(maxHeight[k] != 0 && (curH + maxHeight[k]) > ans)
80: {
81: ans = curH + maxHeight[k];
82: bestA_idx = i, bestB_idx = maxIdx[k];
83: bestA_len = j+1, bestB_len = k;
84: }
85: }
86: }
87:
88: /*
89: We are done for this color group.
90: This may be included in an optimal answer,
91: so update maxHeight and maxIdx
92: */
93: if(curH > maxHeight[cs[i].len])
94: {
95: maxHeight[cs[i].len] = curH;
96: maxIdx[cs[i].len] = i;
97: }
98: }
99:
100: cout<<ans<<endl;
101: cout<<(bestA_len + bestB_len)<<endl;
102:
103: for(int i=0; i < bestA_len; i++)
104: {
105: cout<<cubes[cs[bestA_idx].pos + i].idx;
106: if(i < bestB_len)
107: cout<<" "<<cubes[cs[bestB_idx].pos + i].idx<<" ";
108: }
109: cout<<endl;
110: }
111:
112: bool cubeSort(Cube a, Cube b)
113: {
114: //sort by color
115: if(a.color != b.color) return a.color < b.color;
116:
117: //If color is the same, sort by height in non-increasing order
118: return a.height > b.height;
119: }
120:
121: //Sort cubeSet by its length.
122: bool colorSort(CubeSet a, CubeSet b)
123: {
124: return a.len < b.len;
125: }
I will post editorials on other problems later.
No comments:
Post a Comment