I submitted my solution for 250 and 1000.
Only my 250 survived the system test.
I figured out how to solve 500 after the contest by looking at other people's codes.
Getting a score of 203.56, I got 831st place. I failed.
250 - EllysJuice
Apporoach
We need to look at this problem by dividing it into two cases.
Let N = number of different names.
case 1) N = 1, or there is only one player.
They this player always wins.
case 2) N >= 2, or there is at least two different players.
Note that we are only interested in the amount of juice we drink, not whether it is an apple or orange.
So, focusing on the amount, playing the first turn gives you 0.5 juice, and playing the second turn give you another 0.5 juice.
Let Ci = number of turns that player i plays.
If Ci = 1, then player i can drink at most 0.5 juice.
Since N>=2, at least one other player can drink 0.5 juice by playing the second turn.
So if Ci = 1, player i CANNOT win because there is least one player who can drink more than or equal amount of juice.
If Ci >=2, player i can play the first turn AND the second turn, which gives player i a chance to drink 1.0 juice. Notice that even if a single player plays infinite turns after 2nd turn, there is no way he can drink exactly 1.0 juice because the player drinks half of what is left every turn, never quite drinking the entire juice left. In other words, once a player plays first and second turn, the player is guaranteed to win.
So here are basic steps
1. Count how many players there are
2. If there is a single player, return his name.
3. If there are more than one player, count how many turns each player gets to play.
4. Return all the names of players who play at least 2 turns.
Source Code
1:
2: bool sortNames(string, string);
3:
4: vector <string> EllysJuice::getWinners(vector <string> players) {
5:
6: vector<string> res;
7:
8: set<string> names;
9: map<string, int> ct;
10:
11: for(int i=0; i < players.size(); i++)
12: {
13: if(names.count(players[i]) == 0)
14: {
15: names.insert(players[i]);
16: ct[players[i]] = 1;
17: }
18: else
19: ct[players[i]]++;
20: }
21:
22: int A = names.size();
23:
24: if(A == 1) return vector<string>(names.begin(), names.end());
25:
26: set<string>::iterator itr;
27: for(itr = names.begin(); itr != names.end(); itr++)
28: if(ct[(*itr)] >= 2) res.push_back(*itr);
29:
30: sort(res.begin(), res.end(), sortNames);
31: return res;
32: }
33:
34: bool sortNames(string a, string b)
35: {
36: for(int i=0; i < min(a.size(),b.size()); i++)
37: return a[i] < b[i];
38:
39: return a.size() < b.size();
40:
41: }
42:
500 - EllysFractions
Apporoach
Main Algorithm
: Given factorial number NF, How many irreducible fractions have the form (A/B) that satisfy (A*B = NF) ?
Let's revisit the definition of factorial number.
Factorial number F! = 1*2*3*4*5*...*(F-1)*F
We have to divide factors of (I) into two groups so that one goes to group A, and the other goes to group B.
Notice that we want A/B to be IRREDUCIBLE.
If you think about it, you will realize that diving factors of F is actually diving PRIME factors of F because if two numbers that share a common prime number goes to different groups, their common prime number will be canceled out, resulting in A * B != F!
For example,
Let F = 1*2*3*4*5 , or 5!
2 and 4 share a common prime number , which is 2.
Let's put them in a different group, Say A = 1*2*3 and B = 4*5
Then A/B = (1*2*3) / (4*5) = (1*3)/(2*5) , and A*B != F because we cancelled out 2 from A and B to make A/B irreducible.
There is one more condition to match
: A has to be smaller than B, or A < B.
Keeping the condition in mind, our answer to the main algorithm is
(number of ways to divide primes in [1 from F (inclusive)] into two groups) / 2
We divide by 2 because for each unique group pair (A,B) only A/B is allowed, not B/A.
More formally,
let P = number of primes in [1 .. F]
ans = (2^P) / 2
The problem statement asks us to find group A/B such that A*B = one of the factorial numbers from 1! to N!
Now that we know how to find number of A/B such that A*B = a given factorial number,
all we need to do is ask the question from 1 to N, inclusive.
Source Code
1:
2: const int MAX = 300;
3: bool isPrime[MAX];
4:
5: long long EllysFractions::getCount(int N) {
6:
7: memset(isPrime, true, sizeof(isPrime));
8:
9: ll res = 0;
10: ll cur = 1ll;
11: for(int i=2; i <= N; i++)
12: {
13: if(isPrime[i])
14: {
15: for(int j= i+i; j <= N; j+=i)
16: isPrime[j] = false;
17: cur *= 2ll;
18: }
19: res += (cur/2ll);
20: }
21:
22: return res;
23:
24: }
1000 - EllysLights
You need to tackle this problem after making careful observations.
During the contest, I noticed the problem could be turned into bitmask problem.
To illustrate, bulb sequence "NYYNN" can be turned into "01100",
and a switch "NNYYN" can be turned into ""00110".
Using a switch has the same effect as doing xor operation between a switch and bulb sequence.
For example, if we use the switch from the above example,
result will be (01100 ^ 00110) = 01010 , or "NYNYN"
The above observation is correct, but one should look a little bit further to solve this problem.
Unfortunately, this is how far I got during the contest.
Out of desperation, I used Breadth First Search with memorization to try every possible combination of sequences. My approach is okay for N <= 35~40. However, the problem states that N <= 50.
Consequently I failed the system test.
After the contest, I went to the practice room and read rng_58's solution to this problem.
I soon realized I failed to make a key observation that was crucial to solving this problem.
Following approach and source code was obtained by carefully reading rng_58's code (i.e. this is not my original idea)
Apporoach
In my opinion, reading the problem statement carefully was key to solving this problem.
The key sentence was "
A BULB IS CONNECTED TO AT MOST TWO SWITCHES."
Let's call this sentence THE SWITCH RULE.
From
the switch rule, we can categorize each switch X as follow
Case 1) Switch X is the only switch that controls (i)th bulb.
sub 1) If (i)th bulb is on, we MUST USE switch X.
sub 2) If (i)th bulb is off, we MUST NOT USE switch X.
Case 2) It is one of two switches that control (i)th bulb.
sub 3) If (i)th bulb is on, only one of the two switches should be used.
sub 4) If (i)th bulb is off, either use both switches or do not use any of them at all.
Now it is time to apply our observations to the problem.
Step 1)
For each switch X that MUST BE USED (
sub 1), turn switch X on, and turn other switches that need to be turned on with switch X(
sub 3). Note theses two facts
1) Each switch can control to multiple bulbs.
2) Turn switch Y on because of switch X may result in other switches that are not related to X but related to Y.
So we need to turn on all switches that are related to switch X and all other switches that are either related to switch X or switches that are related to X.
Also do not forget that we have to turn off all switches that belong to
sub 4
We can use
depth first search to do this.
Step 2)
For each switch X that MUST NOT BE USED(
sub 2), turn switch X off, and
turn off switches belonging to
sub 3, and
turn on switches belonging to
sub 4.
Step 3)
It is possible that switches that have no relationship to switches in Step 1 and Step 2 exist. In other words, we can be still uncertain what to do with some switches after doing Step 1 and Step 2. Sample case 0 represents this situation.
For all these switches, figure out relationships among them.
Step 4)
Now that we figured out what to do with all switches, check if our conclusion conforms to our initial observations (
sub 1,
sub 2,
sub 3, and
sub 4). If it does not, return -1.
Step 5)
Our answer is (number of switches that are turned on in Step 1 and Step 2) + (minimum number of switches that should be turned in Step 3).
Count these switches, and return them.
I will post two source codes. The first one is a successful code that implements what I explained so far. The second one is what I wrote during the contest. I am posting my failed code hoping that somebody may come up with a clever way to improve my solution enough to pass system test.
Source Code - Successful
1: const int maxN = 50;
2: int N;
3: bool on[maxN];
4: bool off[maxN];
5: bool same[maxN][maxN];
6: bool diff[maxN][maxN];
7: int groupNum[maxN];
8: int groupCnt[maxN*2];
9:
10: void dfs(int, int);
11:
12: int EllysLights::getMinimum(string bulb, vector <string> S) {
13:
14: memset(groupNum, -1, sizeof(groupNum));
15: memset(groupCnt, 0, sizeof(groupCnt));
16: N = S.size();
17:
18: for(int i=0; i < bulb.size(); i++)
19: {
20: int X = -1; //First switch that controls (i)th bulb
21: int Y = -1; //Second switch that controls (i)th bulb
22: for(int j=0; j < N; j++)
23: if(S[j][i] == 'Y')
24: {
25: if(X == -1) X = j;
26: else Y = j;
27: }
28:
29: if(bulb[i] == 'Y')
30: {
31: if(X != -1)
32: {
33: if(Y != -1) diff[X][Y] = diff[Y][X] = true;
34: else on[X] = true;
35: }
36: else
37: {
38: //No switch controls this bulb, but this bulb
39: //needs to be turned off. It is impossible.
40: return -1;
41: }
42: }
43: else //bulb[i] == 'N'
44: {
45: if(X != -1)
46: {
47: if(Y != -1) same[X][Y] = same[Y][X] = true;
48: else off[X] = true;
49: }
50: }
51: }
52:
53: for(int i=0; i < N; i++)
54: {
55: if(on[i]) dfs(i, 1); //Step 1
56: if(off[i]) dfs(i, 0); //Step 2
57: }
58:
59: //step 3
60: int extra = 2;
61: for(int i=0; i < N; i++)
62: if(groupNum[i] == -1)
63: {
64: dfs(i, extra);
65: extra+=2;
66: }
67:
68: //step 4
69: for(int x=0; x < N; x++)
70: {
71: if(on[x] && groupNum[x] != 1) return -1;
72: if(off[x] && groupNum[x] != 0) return -1;
73: for(int y=0; y < N; y++)
74: {
75: if(same[x][y] && groupNum[x] != groupNum[y]) return -1;
76: if(diff[x][y] && groupNum[x] == groupNum[y]) return -1;
77:
78: }
79: }
80:
81: //step 5
82: for(int i=0; i < N; i++)
83: groupCnt[groupNum[i]]++;
84:
85: int ans = groupCnt[1];
86: for(int i=2; i< extra; i+=2)
87: ans += min(groupCnt[i], groupCnt[i+1]);
88:
89: return ans;
90: }
91:
92: void dfs(int X, int id)
93: {
94: if(groupNum[X] != -1) return;
95: groupNum[X] = id;
96:
97: for(int i=0; i < N; i++)
98: {
99: if(same[X][i]) dfs(i, id);
100: if(diff[X][i]) dfs(i, id^1);
101: }
102:
103: }
Source Code - Failed
1: ll getVal(string);
2:
3: ll initVal;
4: vector<ll> swit;
5: set<ll> chk; //memoization
6:
7: int EllysLights::getMinimum(string initial, vector <string> switches) {
8:
9: int N = switches.size();
10: initVal = getVal(initial);
11: for(int i=0; i < N; i++)
12: swit.push_back(getVal(switches[i]));
13:
14: if(initVal == 0) return 0;
15:
16: int ans = 55;
17:
18: queue<ll> Q;
19:
20: for(int i=0; i < N; i++)
21: {
22: chk.insert(swit[i]);
23: Q.push(swit[i]);
24: Q.push(1ll<<i);
25: Q.push(1);
26: }
27:
28: //check validity
29: for(int i=0; i < initial.size(); i++)
30: {
31: if(initial[i] == 'Y')
32: {
33: bool hasY = false;
34: for(int j=0; j < N; j++)
35: {
36: if(switches[j][i] == 'Y')
37: {
38: hasY = true;
39: break;
40: }
41: }
42: if(!hasY) return -1;
43: }
44: }
45:
46: //BFS
47: while(!Q.empty())
48: {
49: ll val = Q.front(); Q.pop();
50: ll condi = Q.front(); Q.pop();
51: ll turn = Q.front(); Q.pop();
52:
53: if(val == initVal)
54: {
55: ans = turn;
56: break;
57: }
58:
59: for(int i=0; i < N; i++)
60: {
61: if( (condi & (1ll<<i)) == 0 )
62: {
63: ll next = val ^ swit[i];
64: if(chk.count(next) == 1) continue;
65: chk.insert(next);
66: Q.push(next);
67: Q.push(condi |= (1ll<<i) );
68: Q.push(turn + 1);
69:
70: }
71: }
72: }
73:
74: if(ans == 55) return -1;
75: return ans;
76: }
77:
78: ll getVal(string str)
79: {
80: ll res = 0ll;
81: ll two = 1ll;
82: for(int i=str.size()-1; i >= 0; i--)
83: {
84: if(str[i] == 'Y') res += two;
85: two *= 2ll;
86: }
87: return res;
88: }
89:
