I did okay - I passed 250 and failed 500.
After the system test, I found out why I failed 500, and solved it in a practice room.
DIV1
250 - EvenRoute
Approach
I will update this shortly.
Source Code
1: class EvenRoute {
2: public:
3: string isItPossible(vector <int>, vector <int>, int);
4: };
5: string EvenRoute::isItPossible(vector <int> x, vector <int> y, int pa) {
6: bool hasEven = false, hasOdd = false;
7: for(int i=0; i < x.size(); i++)
8: if( (abs(x[i]) + abs(y[i])) % 2 == 0) hasEven = true;
9: else hasOdd = true;
10: if( (pa == 0 && hasEven) || (pa == 1 && hasOdd) ) return "CAN";
11: return "CANNOT";
12: }
500 - TurtleSpy
Approach
It is a simple math problem that needs a bit of observation.
Lemma 1. It is always optimal to use forward vectors in the same direction.
Proof.
We want to maximize the euclidian distance (E.D).
Let sumF = sum of all forward vectors.
If we use forward vectors as a straight line, we get sumF for the E.D.
However, if we change our direction while connecting forward vectors, we will make the total shape of vectors slight bent. And the E.D for the bent vector will be smaller than the straight line.
Now, we established Lemma 1, and note that the same logic applies to backward vectors.
We can now make one more observation.
Lemma 2. It is optimal to turn as close to 180 degrees possible after finishing using forwarding vectors.
Proof.
backward vectors are essentially (Turn 180 degrees + forward vectors), or negative forward vectors.
Let sumB = sum of all backward vectors.
If we turn 180 degrees, the final E.D is sumF + sumB, and the more we turn away from 180 degrees,
our E.D. will get smaller and smaller.
Let's define
OPT = optimal degree possible we can gain using given "degree" vectors. (left X and right X).
F = sum of all forward vectors.
B = sum of all backward vectors.
Then our answer is
sqrt( (F - B * cos(OPT))^2 + (B * sin(OPT))^2 )
= sqrt ( F^2 - 2*F*B*cos(OPT) + (B*cos(OPT))^2 + (B*sin(OPT))^2
= sqrt( F^2 + B^2*(cos^2(OPT) + sin^2(OPT)) - 2*F*B*cos(OPT))
= sqrt(F^2 + B^2 - 2*F*B*cos(OPT))
So all we have to do is find OPT.
Note that there are 360 possible degrees, and at most 50 degree vectors.
We can try them all, and it will take only 360*50 operations at most.
Source Code
1: double TurtleSpy::maxDistance(vector <string> commands) {
2: int F = 0;
3: int B = 0;
4: double PI = acos(-1);
5: vector<bool> deg(361, false);
6: deg[0] = true;
7: for(int i=0; i < commands.size(); i++)
8: {
9: stringstream ss(commands[i]);
10: string cmd;
11: int X;
12: ss>>cmd>>X;
13:
14: if(cmd[0] == 'f') F+=X;
15: else if(cmd[0] == 'b') B+=X;
16: else
17: {
18: vector<bool> temp = deg;
19: if(cmd[0] == 'r')
20: {
21: for(int i=0; i < 360; i++)
22: if(temp[i])
23: deg[ (i+X) % 360 ] = true;
24: }
25: else //cmd[0] == 'L'
26: {
27: for(int i=0; i < 360; i++)
28: if(temp[i])
29: deg[ (i-X + 360) % 360 ] = true;
30: }
31: }
32: }
33:
34: double opt = 0.0;
35: int away = 0;
36: while(away <= 180 && opt == 0.0)
37: {
38: if(deg[180 - away] || deg[180 + away])
39: opt = (180.0 - away);
40: away++;
41: }
42: double df = double(F);
43: double db = double(B);
44: return sqrt(df*df - 2.0*df*db*cos(opt * PI / 180.0) + db*db);
45: }
46:
DIV2
250 - LeftOrRight
Source Code
1: class LeftOrRight {
2: public:
3: int maxDistance(string);
4: };
5:
6: int LeftOrRight::maxDistance(string program) {
7:
8: //? = left
9: int left = 0, right = 0;
10: int ans = 0;
11: for(int i=0; i < program.size(); i++)
12: {
13: if(program[i] == 'L')
14: {
15: left++;
16: right--;
17: }
18: else if(program[i] == 'R')
19: {
20: left--;
21: right++;
22: }
23: else
24: {
25: left++;
26: right++;
27: }
28: ans = max(ans, max(left, right));
29: }
30: return ans;
31: }
32:
500 - EvenRoute => same as div 1 250
1000 - skewedPerspectives
Source Code
1: class SkewedPerspectives {
2: public:
3: vector <string> areTheyPossible(vector <int>, int, int, vector <string>);
4: };
5:
6: vector <string> SkewedPerspectives::areTheyPossible(vector <int> cubes, int B, int w, vector <string> views) {
7:
8: vector<string> ans;
9: for(int v=0; v < views.size(); v++)
10: {
11: //basic test
12: if( (views[v].size() == 1 && views[v][0] == 'b') || (views[v].size() > 1 && views[v][0] == 'b' && views[v][1] != 'b') )
13: {
14: ans.push_back("invalid");
15: continue;
16: }
17:
18: string curView = 'x' + views[v];
19: vector<int> curCubes = cubes;
20: vector<int> extra;
21: bool valid = true;
22: int curB = B;
23:
24: int h = curView.size() - 1;
25:
26:
27: while(h >= 1)
28: {
29: if(curView[h] != 'b')
30: {
31: curCubes[ curView[h] - '0' ]--;
32: h--;
33: }
34: else
35: {
36: int low = h;
37: while(curView[low] == 'b')
38: low--;
39: int oldH = h;
40: h = low;
41:
42: if( (oldH-low) % 2 == 0)
43: {
44: curB -= (oldH-low)/2;
45: }
46: else
47: {
48: curB -= (oldH - low + 1) / 2;
49:
50: if(low == 0) extra.push_back(1);
51: else extra.push_back(low-1);
52: }
53: }
54: }
55:
56: int ones = 0;
57: for(int i=0; i < curCubes.size(); i++)
58: {
59: if(curCubes[i] < 0)
60: {
61: valid = false;
62: break;
63: }
64: ones += curCubes[i];
65: }
66:
67: if(!valid || curB < 0 || (extra.size() + 1) > w)
68: {
69: ans.push_back("invalid");
70: continue;
71: }
72:
73: for(int i=0; i < extra.size(); i++)
74: {
75: while( curB > 0 && (extra[i] - 2 >= 0) )
76: {
77: curB--;
78: extra[i]-=2;
79:
80: }
81:
82: while( ones > 0 && (extra[i] - 1 >= 0) )
83: {
84: ones--;
85: extra[i]--;
86: }
87:
88: if(extra[i] > 0)
89: {
90: valid = false;
91: ans.push_back("invalid");
92: break;
93: }
94: }
95:
96: if(valid)
97: ans.push_back("valid");
98: }
99: return ans;
100: }
No comments:
Post a Comment