It might be a while until I start blogging again. Here is my repository of problems in the meanwhile.

Despite my lack of activity in my blog for a very long time, I still get a few visitors in my blog ( wow...!?).

I started working for Yammer, Microsoft in San Francisco this March.

It might be a while until I start blogging again.

But I've been participating in programming contests and saving my solutions.  Here is the Github repository of my solutions to various contests.

If you would like me to solve problems whose solutions are not hosted in the above repo, feel free to open an issue ticket in the Github repo and I will give it a try.

Happy coding! :-)

TopCoder Open 2012 - Round 1C

Level One - PasswordXGrid


Source Code

1:  long long PasswordXGuessing::howMany(vector <string> V) {  
2:         
3:    int N = V.size();  
4:    int M = V[0].size();  
5:    int res = 0;  
6:      
7:    for(int w=0; w < M; w++)  
8:    {  
9:      for(char ch = '0'; ch <= '9'; ch++)  
10:      {  
11:        bool isValid = true;  
12:        string ans = V[0];  
13:        ans[w] = ch;  
14:          
15:        for(int i=0; isValid && i < N; i++)  
16:        {  
17:          int diff = 0;  
18:            
19:          for(int j=0; j < M; j++)  
20:            if(V[i][j] != ans[j]) diff++;  
21:            
22:          if(diff != 1) isValid = false;  
23:        }  
24:        if(isValid) res++;  
25:      }  
26:    }  
27:      
28:    return res;  
29:  }  
30:    

Level Two - PasswordXGuessing


Source Code

1:    
2:  const int maxN = 45;  
3:  int dp[maxN][maxN];  
4:  int vert[maxN][maxN];  
5:  int hori[maxN][maxN];  
6:    
7:  int PasswordXGrid::minSum(vector <string> H, vector <string> V) {  
8:    
9:    int R = H.size();  
10:    int C = H[0].size()+1;  
11:      
12:    memset(dp, 0, sizeof(dp));  
13:    memset(hori, 0, sizeof(hori));  
14:    memset(vert, 0, sizeof(vert));  
15:      
16:    for(int i=0; i < R; i++)  
17:      for(int j=0; j < C-1; j++)  
18:        hori[i][j] = H[i][j] - '0';  
19:      
20:    for(int i=0; i < R-1; i++)  
21:      for(int j=0; j < C; j++)  
22:        vert[i][j] = V[i][j] - '0';  
23:    
24:    for(int i = R-1; i >= 0; i--)  
25:      for(int j= C-1; j >= 0; j--)  
26:        dp[i][j] = max(hori[i][j] + dp[i][j+1], vert[i][j] + dp[i+1][j]);  
27:    
28:    return dp[0][0];  
29:    
30:  }  

Level One - PasswordXPalindrome


Source Code

1:  int PasswordXPalindrome::minSwaps(string pwd) {  
2:      
3:    int N = pwd.size();  
4:    int res = 0;  
5:    bool soloChk = false;  
6:    for(int i = 0; i < N/2; i++)  
7:    {  
8:      if(pwd[i] == pwd[N-1-i]) continue;  
9:      bool found = false;  
10:      for(int j=i+1; !found && j < N-1-i; j++)  
11:        if(pwd[i] == pwd[j])  
12:        {  
13:          swap(pwd[j], pwd[N-1-i]);  
14:          res++;  
15:          found = true;  
16:        }  
17:      if(!found)  
18:      {  
19:        if(N%2 == 1 && !soloChk)  
20:        {  
21:          swap(pwd[i], pwd[N/2]);  
22:          res++;  
23:          soloChk = true;  
24:          i--;  
25:        }  
26:        else if(pwd[i] != pwd[N-1-i])  
27:          return -1;  
28:      }  
29:    }  
30:       return res;  
31:  }  

TopCoder Open 2012 - Round 1B

All round 1 are held in 1:00AM  in my country.

So I have to either stay up late or sleep early and wake up to participate in the match.

In round 1A, I stayed up, and it was very tiring for me.

So this time, I decided to sleep early. How did it turn out?

When I woke up, the match was already over. OMG...

Nevertheless, I went to the practice room and tried to solve all problems.

Problems looked somewhat easier than the previous match (1A). What surprised me was that the cutoff for this match is a lot lower than 1A even though it seemed easier than the last match. I really should've participated in the match.

I solved 250 and 500 on my own, and got the correct answer.

I had trouble solving 1000, so I ended up looking at writer's solution, which was a lot simpler than I thought.

250 - FoxAndKgram

Approach

Let's turn this into a simpler problem.

Q1 : If we know the value of k (as in k-gram), is it possible to make it?

Note that we do not need to use all pencils, which means we can try the greedy approach.

Step 1) Find all pencils whose length is equal to k.

Step 2) Excluding pencils found in Step 1, find all pairs of pencils who sum is (k-1)

If number of pencils found in Step 1 and number of pairs of pencils found in Step 2 is bigger than or equal to k, it is possible.

Let N = number of pencils.

Then the above greedy approach takes O(2*N), or O(N), which is good enough considering the small constraint for N : 1 <= N <= 50

Now that we've found an efficient way to answer Q1, we can simply try all possible values of k.

Note that 1 <= k <= number of pencils. In other words, k cannot be higher than the number of pencils.

Proof : Yang takes one pencil, Yin takes two pencils, and each row has to be either Yang or Yin.

So each row needs at least one pencil, which means the maximum number of rows we can possibly create is the number of pencils.

So we basically try all possible k, and see if the current value for k is correct.

The overall running time is O(N) * O(N) = O(N^2)

Source Code

1:  bool isPossible(int);  
2:  vector<int> len;  
3:  int N;  
4:    
5:  int FoxAndKgram::maxK(vector <int> leng) {  
6:      
7:    len = leng;  
8:    N = len.size();  
9:    int res = 0;  
10:      
11:    for(int k=1; k <= N; k++)  
12:      if(isPossible(k))  
13:        res = k;  
14:      
15:    return res;  
16:  }  
17:    
18:  //return true if k is a valid k-gram value  
19:  bool isPossible(int k)  
20:  {  
21:    int res = 0;  
22:    vector<bool> used(N,false);  
23:      
24:    //find Yang  
25:    for(int i=0; i < N; i++)  
26:      if(len[i] == k)  
27:      {  
28:        used[i] = true;  
29:        res++;  
30:      }  
31:      
32:    //find Yin  
33:    for(int i=0; i < N; i++)  
34:      for(int j=i+1; j < N; j++)  
35:        if(!used[i] && !used[j] && (len[i] + len[j] + 1) == k)  
36:        {  
37:          used[i] = used[j] = true;  
38:          res++;  
39:        }  
40:      
41:    return res >= k;  
42:  }  
43:    

500 - FoxAndDoraemon

Approach

This can be solved using dynamic programming if we make a few key observations.

Observation 1 : It is optimal to start the longest work first.

Observation 2 : It is optimal to use the split hammer on all available foxes.
Explanation : This is an easy to miss observation. Note that the effect of the split hammer is instantaneous, which means it is possible to use the split hammer on multiple foxes at the same time (You can confirm this observation by looking at test case 1). We have problems when we have less foxes than we need, which means more foxes means better.

Let N = number of works.

Using Observation 1, let's sort all works in ascending order, and start by taking (N-1)th work.

Let's start doing dynamic programming.
Recurrence.
When processing (i)th job, we have two options
1) Split fox
2) Start the current job

Note that option 1) is unnecessary when you have more foxes than you need.
Als note that it is unwise to choose option 2) when you have only one fox left and there are more than moe jobs left.

State.
dp[i][j] = minimum number of time required to finish all jobs when there are [0...i) jobs left with j foxes.

Source Code

1:    
2:  const int maxN = 55;  
3:  int dp[maxN][maxN*2];  
4:  int N;  
5:  int splitC;  
6:  vector<int> workC;  
7:    
8:  int rec(int,int);  
9:  int FoxAndDoraemon::minTime(vector <int> workCost, int splitCost) {  
10:      
11:    sort(workCost.begin(), workCost.end());  
12:    N = workCost.size();  
13:    splitC = splitCost;  
14:    workC = workCost;  
15:       memset(dp, -1, sizeof(dp));  
16:      
17:    return rec(N-1, 1);  
18:  }  
19:    
20:  int rec(int jobs, int fox)  
21:  {  
22:    if(jobs == -1) return 0;  
23:      
24:    int& val = dp[jobs][fox];  
25:    if(val != -1) return val;  
26:    val = 0;  
27:      
28:    if( (jobs+1) <= fox) val = max(workC[jobs] , rec(jobs-1, fox-1));  
29:    else  
30:    {  
31:      //split fox  
32:      val = splitC + rec(jobs, fox + 1);  
33:        
34:      if( !(fox == 1 && jobs > 0) )  
35:        val = min(val, max(workC[jobs], rec(jobs-1, fox-1)));  
36:    }  
37:    return val;  
38:  }  
39:    

1000 - FoxAndPhotography

Approach

This problem can also solved using dynamic programming.
For each person in the first row, we need to determine where to put him.

Let N = number of members in heightsFront.

State
mask
= it is a bitmask representing which column has been taken care of.
= (i)th bit is 0 if (i)th column needs to be processed, and 1 if it is already processed.

dp[mask] 

= minimum number of swaps needed when the current state is mask.

Recurrence
At each state (mask, cur) where cur represents the current member of the first row we are looking at,
we need to decide where to put this guy.
Go through each member of the back row, and if the (i)th member of the back row is not processed and is taller than the current member of the first row, try putting the current guy in front of the (i)th person in the back row. Keep doing this until we assigned all members of the first row to their appropriate slots.
Now, you might be wondering below two questions.

Q1) It seems like the state consists of two variables : mask and cur. Then why are we not using "cur" in  dp, i.e. dp[mask][cur] ?
We start at mask = 0 (No front person is assigned to any position), and at each iteration, we assign one front person to a position, making one of N bits in mask 1.  Then (cur) is simply (N - number of unset bits in mask). So we really do not need to store "cur" as it is already encoded in mask.

Q2) How do we calculate how many swaps we need at each iteration?
At each iteration, the member in the first row who was originally at position (cur) is actually at the first unprocessed position of the back row. Let's take a look at test case 2.  I will color currently processed member blue, processed member red, and unprocessed member black.
Original position of the first row
140 141 142 143

Swapping process
 140 144 142 143
=> 141 140 142 143
=> 141 142 140 143
=> 141 142 143 140
=> 142 141 143 140
=> 142 143 141 140
=> 143 142 144 140
=> 143 142 144 140

So if we want to put the current member at (i)th position, the minimum number of swaps required is (number of unprocessed elements before i).

Source Code

1:    
2:  int dp[1<<16];  
3:  int N;  
4:  int INF = (15*16)/2 + 10;  
5:  vector<int> hF;  
6:  vector<int> hB;  
7:    
8:  int rec(int,int);  
9:    
10:  int FoxAndPhotography::getMinimumSwaps(vector <int> heightsFront, vector <int> heightsBack) {  
11:         
12:    hF = heightsFront;  
13:    hB = heightsBack;  
14:    N = hF.size();  
15:      
16:    memset(dp, -1, sizeof(dp));  
17:    int res = rec(0,0);  
18:    if(res >= INF) return -1;  
19:    return res;  
20:  }  
21:    
22:  int rec(int mask, int cur)  
23:  {  
24:    if(cur == N) return 0;  
25:      
26:    int& val = dp[mask];  
27:    if(val >= 0) return val;  
28:      
29:    val = INF;  
30:    int prev = 0;  
31:    for(int i=0; i < N; i++)  
32:    {  
33:      //If (i)th member in backrow is not taken care of,  
34:      //and if the person at position 'cur' at front row is  
35:      //shorter than (i)th person in backrow, try swappping.  
36:      if( (mask & (1<<i)) == 0)  
37:      {  
38:        if(hF[cur] < hB[i])  
39:          val = min(val, prev + rec( mask + (1<<i) , cur+1));  
40:        prev++;  
41:      }  
42:    }  
43:    return val;  
44:  }  

Croc Champ 2012 - Qualification Round

I am posting this before the system test ends.

I solved all 5 problems.
A,B,C, and D were easy enough to pass pretests in the first try.
However, it took me 4 wrong submissions to pass E.
Later I realized that I misunderstood the problem. Given query "a b b",
My thought : I have to find all possible sequence of a b b.
Answer : Find all element b who is the end element of the sequence a b b.

For example, given sequence <a><b><b><b></b></b></b></a>
Let's represent them a - b1 - b2 - b3
Given query a b b,
answer is  2  because b2 is the end element of (a b1 b2) and b3 is the end element of (a b1 b3 and a b2 b3)
I thought I had to output 3 because there are three possible sequence (a b1 b2, a b1 b3, a b2 b3).
After carefully reading the problem statement again, I realized the problem wanted the number of "ELEMENTS," not the number of "SEQUENCES".

Update :
Results are up. I am advancing to Round 1.
I passed A,B, and D, and failed C and E.
I was so sure about my solution to C, so I was curious why I failed system test.
I found out that I stupidly wrote
"const int maxS = 10010" even though the problem states that the maximum number of student is 10^5, or 100000.
So it should've been "maxS = 100010"
I fixed the mistake, I updated my solution to C in this blog accordingly.
I submitted my  fixed solution, but my submission is in queue for about 4 hours. Something must be wrong with codeforces server because a few others are also in queue.
My solution to C passed system test.

As for E, I received the verdict "time limit exceeded."
I am not sure what went wrong, but I will post about it as soon as I figure it out.
I solved E, and passed system test.

A. Phone Code
Approach
The constraints (2 <=n <= 3*10^4  , 1 <= length of phone number <= 20) are small enough to use simple brute force approach.

Step 1.
Let ans = the city phone code.
Let's make ans = the first phone code.

Step 2.
For each phone code, compare it to ans, and see if there is any mismatch. If there is, get rid of parts of ans that conflict with the current phone code.

Our answer is the size of ans.

Source Code

1:  int main()  
2:  {  
3:    ios_base::sync_with_stdio(false);  
4:    int N;  
5:    cin>>N;  
6:      
7:    string ans = "";  
8:    cin>>ans;  
9:      
10:    //It is guranteed that 2 <= N  
11:    for(int i=1; i < N; i++)  
12:    {  
13:      string cur;  
14:      cin>>cur;  
15:      int j = 0;  
16:      while(j < ans.size() && ans[j] == cur[j])  
17:        j++;  
18:        
19:      ans = ans.substr(0,j);  
20:    }  
21:      
22:    cout<<ans.size()<<endl;  
23:    
24:    return 0;  
25:  }  

B. Pseudorandom Sequence Period
Approach
The key to solving this problem is to notice that a cycle ends when the same value is produced twice as the result of mod operation.
So simulate the sequence until you see the same number twice. Let's call this twice-produced value C.
The answer is (the index of the second occurrence of C - the index of the first occurrence of C).
Note that M is at most 10^5, which means we will find our answer in at most 10^5 steps.

Source Code

1:  const int maxM = 100010;  
2:  int chk[maxM];  
3:    
4:  int main()  
5:  {  
6:    ios_base::sync_with_stdio(false);  
7:      
8:    int a,b,m,r0;  
9:      
10:    cin>>a>>b>>m>>r0;  
11:      
12:    memset(chk, -1, sizeof(chk));  
13:      
14:    int prev = (a*r0 + b) % m;  
15:    int idx = 1;  
16:    chk[prev] = idx;  
17:      
18:    while(true)  
19:    {  
20:      idx++;  
21:      int next = (a*prev + b) % m;  
22:      prev = next;  
23:      if(chk[next] != -1) break;  
24:      chk[next] = idx;  
25:    }  
26:    
27:    cout<<(idx - chk[prev])<<endl;  
28:    
29:    return 0;  
30:  }  

C. Bus
Approach
My first reaction when I saw this problem was "will it be okay to use plain-old simulation to solve this problem?" I did the following calculation, and found out the answer to my question is "Yes"
Let S = number of students, P = number of passengers the bus can transport.
At each "trip," bus the takes P students, so bus will make  (S/P) trips.
At each trip, I do follow operation
Step 1) Find out
F = the index of the first student to ride the bus
L = the index of the last student to ride the bus (it usually is F + P, but it can be lower if S < (F+P), in which case L   = S-1)

Step 2)
Sort all students in [F,L] by their drop-off location in ascending order.

Step 3)
Make necessary calculations according to the problem statement (refer to my source code).

Running time of each step is largely affected by Step 2, which takes O(P * logP)
So overall running time is O((S/P) * P * log(P))
The worst case will be S = 10^5, P = 1, a situation where there are maximum number of students but the bus can take only 1 person at a time.
The running time will be around 10^5.  This is small enough.

So all we have to do is simulate the problem according to the statement.
One thing to notice is that the time that although the max value of the time that a student gets dropped
is high, it barely fits into the max value of integer, 2,147,483,647. Let's think of the worst case where there are 10^5 students who all live at location 10^4 and there is a single bus. The last student will get to his home at  ( (10^5) * (10^4 * 2 + 1) + 10^5), which is around 2 * 10^9.
So it is okay to use int  to handle time. But I used long long just to be on the safe side.

Source Code

1:  struct Student  
2:  {  
3:    int time;  
4:    int loc;  
5:    int id;  
6:  };  
7:    
8:  const int maxS = 10010;   const int maxs = 100010;
9:  Student stu[maxS];  
10:  ll ans[maxS];  
11:    
12:  bool sortByLoc(Student a, Student b)  
13:  {  
14:    return a.loc < b.loc;  
15:  }  
16:    
17:  int main()  
18:  {  
19:    ios_base::sync_with_stdio(false);  
20:    
21:    int S,P;  
22:    cin>>S>>P;  
23:      
24:    for(int i=0; i < S; i++)  
25:    {  
26:      cin>>stu[i].time;  
27:      cin>>stu[i].loc;  
28:      stu[i].id = i;  
29:    }  
30:    
31:      
32:    ll curTime = 0LL;  
33:    
34:    int idx = 0;  
35:    while(idx < S)  
36:    {  
37:      int last = min(idx + P - 1, S - 1);  
38:      //The bus leaves when the last student arrives  
39:      curTime = max(curTime, ll(stu[last].time));  
40:    
41:      //The bus drops off student who lives closer to 0 first  
42:      sort(stu + idx, stu + (last + 1), sortByLoc);  
43:    
44:      int prevStop = 0;  
45:      while(idx <= last)  
46:      {  
47:        int k = 0;  
48:        int curStop = stu[idx].loc;  
49:        curTime += (curStop - prevStop);  
50:        while(idx<= last && stu[idx].loc == curStop)  
51:        {  
52:                      ans[stu[idx].id] = curTime;  
53:          idx++;  
54:          k++;  
55:        }  
56:        prevStop = curStop;  
57:        curTime += 1LL + (k/2);  
58:      }  
59:        
60:      //The bus goes back to position 0  
61:      curTime += stu[idx-1].loc;  
62:    }  
63:      
64:      
65:    cout<<ans[0];  
66:    for(int i=1; i < S; i++)  
67:      cout<<" "<<ans[i];  
68:    cout<<endl;  
69:      
70:    return 0;  
71:  }  

D. Calendar Reform
Approach
The concept of the problem is not hard to understand. The goal of this problem was to solve this as fast as possible (Notice the 4 seconds time limit).

The first thing I noticed was that we are testing consecutive values. This is a good place to start.
Notice that if X = multiple of a square number S, then all numbers (X + S*i) where ((X+ S*i) < (A + N)) are multiples of S.
Actually, if we make this observation, we are pretty much done because all we have to do is try all possible S.
Minimum S is, of course, 1.
Maximum S is a square number smaller than or equal to (A + N - 1).

In other words, 1 <= S <= (A+N-1)

Given N,
when S = 1 , we do N iterations.
when S = 4 , we do N / 4 iterations.
when S = 36, we do N / 36 iterations.
.....
when S = the biggest possible square number,  we do 1 iteration.

So running time is
N + N/4 + N/36 + ...... 1, which is around 2*N.

I ran my code against maximum inputs using Custom test, and results are following
(1, 10000000) => 480 ms
(2500000, 7500000) => 300 ms
(5000000, 5000000) => 230 ms
(7500000, 2500000) => 110 ms
(10000000, 1) => 10 ms

Looks like it would've been okay if the time limit was 2 seconds.
Either my solution is wrong, or the problem setter must have felt very generous when he set the time limit.

Note :
While reading my approach, have you kept thinking that my approach looks very familiar?
It should be because I got the idea from Sieve of Eratosthenes, a quick way to find whether each number in [1...N] is a prime or not.

Source Code

1:  const int maxN = 10000001;  
2:  ll arr[maxN];  
3:    
4:  int main()  
5:  {  
6:    ios_base::sync_with_stdio(false);  
7:      
8:    ll res = 0ll;  
9:      
10:    ll A,N;  
11:    cin>>A>>N;  
12:      
13:    for(int i=0; i < N; i++)  
14:    {  
15:      arr[i] = -1ll;  
16:    }  
17:      
18:    ll last = A+N-1ll;  
19:    ll lim = sqrt(last);  
20:    ll sq = 1ll;  
21:      
22:    while(sq <= lim)  
23:    {  
24:      ll cur = sq*sq;  
25:        
26:      ll idx = (cur * (A/cur) ) - A;  
27:            if(idx < 0) idx += cur;  
28:              
29:      while(idx < N)  
30:      {  
31:        arr[int(idx)] = cur;  
32:        idx += cur;  
33:      }  
34:      sq++;  
35:    }  
36:      
37:    for(int i=0; i < N; i++)  
38:      res += (A+i) / arr[i];  
39:      
40:    cout<<res<<endl;  
41:    return 0;  
42:  }  
43:    

E. BHTML+BCSS
Approach
We can use a tree structure to represent  "elements".
Each element will have a pointer pointing to its parent.

Every time we meet

<tag> : we make this node the child of the current node, and move to the child node.

</tag> : move to the parent of the current node.

<tag/> : make this node the child of the current node, and stay at the current node.

We can make "Dummy Root node" to have one giant tree, instead of separate disjoint trees, to avoid issue of trying to reach a parent of the actual root (there can be many root elements) when processing </tag>

To illustrate, let's represent the first sample input in tree structure.

<a><b><b></b></b></a><a><b></b><b><v/></b></a><b></b>

Once we represent the given input in a tree structure, query represents "parent - child" relationship.
So we basically need to traverse our graph to find subtree that matches the query's description.
To optimize my solution, I used an int array to save information on how many query relationships are already verified for each element.
More specifically, element i satisfies [query 0 ... query[solved[i]] ),  so child of element i needs to satisfy [query[solved[i]] ... last query].  Please look at my source for further clarification.


Note:
As dj3500 noted, using a tree structure is not the only correct approach to this problem. There is another approach that uses a stack of elements.
"... in E, it is actually not needed to create the tree data structure, it suffices to think that we are traversing the tree while parsing the input (because the input is given in the order in which we would traverse the tree anyway). We only need to maintain a current stack of tags (and, for every tag, the indexes i of the solved[i] that we will need to decrement when we close that tag).  - dj3500 "
Source Code

1:  struct Node  
2:  {  
3:    string data;  
4:    Node* parent;  
5:    int id;  
6:    Node(string d = "", Node* p = NULL, int i=-1)  
7:    {  
8:      data = d;  
9:      parent = p;  
10:      id = i;  
11:    }  
12:  };  
13:    
14:  const int maxDoc = 1e6 + 10;  
15:  const int maxNode = 3 * 1e5;  
16:  const int maxQuery = 210;  
17:  Node nodes[maxNode];  
18:  int solved[maxNode];  
19:  string query[maxQuery];  
20:  int main()  
21:  {  
22:    ios_base::sync_with_stdio(false);  
23:      
24:    string doc;  
25:    getline(cin, doc);  
26:    int idx = 1;  
27:    nodes[0] = Node("ROOT",NULL,0); //dummy root  
28:    Node* pt = &(nodes[0]);  
29:    int N = 1;//number of nodes  
30:      
31:    //process nodes  
32:    while(idx < doc.size())  
33:    {  
34:      if(doc[idx] == '/')  
35:      {  
36:        int j = idx+1;  
37:        while(doc[j] != '>')  
38:          j++;  
39:        idx = j + 2;  
40:        pt = (*pt).parent;  
41:      }  
42:      else  
43:      {  
44:        int j = idx;  
45:        while(doc[j] != '/' && doc[j] != '>')  
46:          j++;  
47:        nodes[N] = Node(doc.substr(idx, j - idx), pt, N);  
48:        if(doc[j] != '/') pt = &(nodes[N]);  
49:        else j++;  
50:            
51:        N++;  
52:        idx = j + 2;  
53:      }  
54:    }  
55:      
56:    int M;  
57:    cin>>M;  
58:    cin.ignore();  
59:    
60:    while(M--)  
61:    {  
62:      //process query  
63:      string line;  
64:      getline(cin, line);  
65:        
66:      int idx = 0;  
67:      int Q = 0; //number of queries  
68:    
69:      while(idx < line.size())  
70:      {  
71:        int j = idx;  
72:        while(j < line.size() && line[j] != ' ')  
73:          j++;  
74:        query[Q++] = line.substr(idx, j - idx);  
75:        idx = j+1;  
76:      }  
77:        
78:      int res = 0;  
79:      int solved[N];  
80:      solved[0] = 0;  
81:      //get answer  
82:      for(int i=1; i < N; i++)  
83:      {  
84:        int pos = solved[ (nodes[i].parent)->id ];  
85:        bool isMatch = (nodes[i].data == query[pos]);  
86:        if(isMatch)  
87:        {  
88:          if(pos == Q-1) res++;  
89:          else pos++;  
90:        }  
91:        solved[i] = pos;  
92:      }  
93:      cout<<res<<endl;  
94:    }  
95:    
96:    return 0;  
97:  }  

TopCoder Open 2012 - Round 1A

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:    

Codeforces #114

I participated in DIV2.
It was a disaster for me. After 14 minutes, I solved A and moved on to B.
Since then, I got stuck on problem B because I was sure of my answer but I kept failing to pass pretest 3.
After the contest, I found out that I didn't put "End of Line" character  AT THE END of the output.
It was a dumb mistake.
I looked at C, and found out it was a rather easy problem if you are familiar with "area under velocity - time  graph.'

Here are my solutions. I added explanations in comments.

A - Wizards and Demonstration
Source Code

1:  int main()  
2:  {  
3:    ios_base::sync_with_stdio(false);  
4:      
5:    int N,X,Y;  
6:    cin>>N>>X>>Y;  
7:      
8:    int up = Y*N;  
9:    if( (up % 100) > 0 )  
10:    {  
11:      up -= (up % 100);  
12:      up += 100;  
13:    }  
14:    up /= 100;  
15:    cout<< max(0, up - X) <<endl;  
16:    
17:    return 0;  
18:  }  

B - Wizards and Minimal Spell
Source Code

1:  bool isSpell(string);  
2:  void printBuf(string);  
3:    
4:  int main()  
5:  {  
6:    ios_base::sync_with_stdio(false);  
7:    string emp = "" + char(15);  
8:    string buf = emp;  
9:      
10:    string str;  
11:    while(getline(cin,str))  
12:    {  
13:      if(isSpell(str))  
14:      {  
15:        if(buf != emp) printBuf(buf);  
16:        cout<<str<<endl;  
17:        buf = emp;  
18:      }  
19:      else  
20:      {  
21:        if(buf == emp) buf = str;  
22:        else buf += str;  
23:      }  
24:    }  
25:      
26:    if(buf != emp)  
27:      printBuf(buf);  
28:    
29:    return 0;  
30:  }  
31:    
32:  bool isSpell(string str)  
33:  {  
34:    stringstream ss(str);  
35:    string test;  
36:    ss>>test;  
37:    return (test[0] == '#');  
38:  }  
39:    
40:  void printBuf(string buf)  
41:  {  
42:    stringstream ss(buf);  
43:    string cur;  
44:    while(ss>>cur)  
45:      cout<<cur;  
46:    cout<<endl;  
47:  }  
48:    

C - Wizards and Trolleybuses
Source Code

1:    
2:  int main()  
3:  {  
4:    ios_base::sync_with_stdio(false);  
5:      
6:    int N;  
7:    double A,D;  
8:    cin>>N>>A>>D;  
9:      
10:    double prev = 0.0;  
11:      
12:    cout<<fixed;  
13:    cout.precision(9);  
14:    for(int i=1; i <= N; i++)  
15:    {  
16:      double t, v;  
17:      cin>>t;  
18:      cin>>v;  
19:      double t_stop = sqrt(2.0*D/A); //time when train arrives at the destination  
20:      double t_max = v / A; //time when train reaches full allowed speed  
21:        
22:      double t_ans = t; //train starts at time t  
23:      //Arrive at the destination before reaching full speed, or not.  
24:      if(t_stop < t_max) t_ans += t_stop;  
25:      else t_ans += t_max + D/v - v/(2.0*A);  
26:        
27:      t_ans = max(prev, t_ans); //cannot arrive before the previous train  
28:      cout<<t_ans<<endl;  
29:      prev = t_ans;  
30:    }  
31:      
32:    return 0;  
33:  }  

D - Wizards and Huge Prize

Note
The problem statement was a bit confusing to me.
I initially thought that "player" cannot gain a huge prize if "the current bag size" is not big enough.
What the question really meant was that "player cannot bring "all huge prizes" if "the bag size at the end of the entire tour" is not big enough.
For example, at example 1,
the player starts with no bag, and the first and second round has huge prizes.
I thought it was impossible for him to earn any of the prizes.
However, he can earn those "huge prizes" first, and then win a bag at the third round.
So we are only interested at the bag size at the end of the entire tours.



Source Code

1:  const int maxN = 210;  
2:    
3:  /*  
4:   dp[i][j][k]  
5:   = probability of winning j tours in first i days  
6:    with bag capacity k and carrying all won prizes  
7:   */  
8:  double dp[maxN][maxN][maxN];  
9:    
10:  int main()  
11:  {  
12:    ios_base::sync_with_stdio(false);  
13:      
14:    int N,L,K;  
15:    cin>>N>>L>>K;  
16:      
17:    double p[N+1];  
18:    int a[N+1];  
19:      
20:    p[0] = 1.0;  
21:    for(int i=1; i <= N; i++)  
22:    {  
23:      cin>>p[i];  
24:      p[i] /= 100.0;  
25:    }  
26:      
27:    a[0] = K;  
28:    for(int i=1; i <= N; i++)  
29:    {  
30:      cin>>a[i];  
31:      a[i]++;  
32:    }  
33:      
34:    //base case  
35:    dp[0][0][K] = 1.0;  
36:      
37:    for(int i=0; i < N; i++)  
38:      for(int j=0; j <= i; j++)  
39:        for(int k=0; k <= 200; k++)  
40:          if(dp[i][j][k] > 0.0)  
41:          {  
42:            dp[i+1][j+1][min(200, k+a[i+1])] += dp[i][j][k] * p[i+1];  
43:            dp[i+1][j][k] += dp[i][j][k] * (1.0 - p[i+1]);  
44:          }  
45:     
46:     
47:    double ans = 0.0;  
48:    for(int j=L; j <= 200; j++)  
49:      for(int k=j; k <= 200; k++)  
50:        ans += dp[N][j][k];  
51:      
52:    cout<<fixed;  
53:    cout.precision(9);  
54:      
55:    cout<<ans<<endl;  
56:      
57:    return 0;  
58:  }  

Codeforces Round #113 (div. 2)

A - Rank List
Approach
1. Sort the given scores as described in the problem.
2. Find out the score at Kth place
3. Go through the array, count how many scores are same to the score at Kth place.

Source Code

1:  bool sortScore( pair<int,int> a, pair<int,int> b)  
2:  {  
3:    if(a.first != b.first) return a.first > b.first;  
4:    return a.second < b.second;  
5:  }  
6:    
7:  int main()  
8:  {  
9:    ios_base::sync_with_stdio(false);  
10:      
11:    int N,K;  
12:    cin>>N>>K;  
13:      
14:    vector< pair<int,int> > score(N);  
15:      
16:    REP(i,0,N)  
17:    {  
18:      int p,t;  
19:      cin>>p>>t;  
20:      score.push_back( make_pair(p,t) );  
21:    }  
22:    
23:    sort( score.begin(), score.end(), sortScore );  
24:      
25:    pair<int,int> sc = score[K-1];  
26:    int same = 0;  
27:    for(int i=0; i < N; i++)  
28:      if(score[i] == sc)  
29:        same++;  
30:      
31:    cout<<same<<endl;  
32:      
33:    return 0;  
34:  }bool sortScore( pair<int,int> a, pair<int,int> b)  
35:  {  
36:    if(a.first != b.first) return a.first > b.first;  
37:    return a.second < b.second;  
38:  }  
39:    
40:  int main()  
41:  {  
42:    ios_base::sync_with_stdio(false);  
43:      
44:    int N,K;  
45:    cin>>N>>K;  
46:      
47:    vector< pair<int,int> > score(N);  
48:      
49:    REP(i,0,N)  
50:    {  
51:      int p,t;  
52:      cin>>p>>t;  
53:      score.push_back( make_pair(p,t) );  
54:    }  
55:    
56:    sort( score.begin(), score.end(), sortScore );  
57:      
58:    pair<int,int> sc = score[K-1];  
59:    int same = 0;  
60:    for(int i=0; i < N; i++)  
61:      if(score[i] == sc)  
62:        same++;  
63:      
64:    cout<<same<<endl;  
65:      
66:    return 0;  
67:  }  

C- Median
Approach

1. Find X.
   If X does not exist, add X to the given array.

2. Sort the array.

3. Find the median.
      If the median < X, add a number to the right.
      If the median > X, add a number to the left.

4. Do number 3 until the median == X

The above step takes
O(NlogN + N) => O(NlogN)

Source Code

1:  int main()  
2:  {  
3:    ios_base::sync_with_stdio(false);  
4:      
5:    int N, X;  
6:    cin>>N>>X;  
7:      
8:    deque<int> arr(N);  
9:    REP(i,0,N)  
10:    cin>>arr[i];  
11:      
12:    int ans = 0;  
13:      
14:    if(count(arr.begin(), arr.end(), X) == 0)  
15:    {  
16:      ans++;  
17:      arr.push_front(X);  
18:    }  
19:      
20:    sort(arr.begin(), arr.end());  
21:    
22:    int mid = ((arr.size() + 1) / 2) - 1;  
23:      
24:    while(arr[mid] != X)  
25:    {  
26:      if(arr[mid] < X) arr.push_back(0);  
27:      else arr.push_front(0);  
28:      mid = ((arr.size() + 1) / 2) - 1;  
29:      ans++;  
30:    }  
31:      
32:    cout<<ans<<endl;  
33:    
34:    return 0;  
35:  }  

D - Shoes Store

Approach
There are two approaches
1) Greedy Algorithm
2) Dynamic Programming

Greedy Algorithm
 Goal : Sell as many highest priced shoes as possible.
Steps.
1. Sort shoes by size
2. For each shoe, find out which customers can buy it.
3. Sort shoes by cost
4. For each shoe, do follow
   1) See if a customer who can buy the current shoe has already bought a shoe or not.
   2) If not, sell this shoe to the current customer
   3) If yes,  let j  = the shoe that the current customer bought.
       See if any other customer can buy shoe j.
       If yes, sell the current shoe to the current customer.
       If not, move on to the next customer.

Dynamic Programming
- Coming soon

Source Code - Greedy Algorithm

1:  /*  
2:   This code belongs to Avalenche.  
3:   I only placed comments and change variable names   
4:   to help me better understand his code.  
5:   */  
6:  const int maxN = 100010;  
7:    
8:  struct obj  
9:  {  
10:    int cost, size, id;  
11:    obj(int c = -1, int sz = -1, int idx = -1): cost(c), size(sz), id(idx) {}  
12:  };  
13:    
14:  bool compSize(obj a, obj b)  
15:  {  
16:    return a.size < b.size;  
17:  }  
18:    
19:  bool compCost(obj a, obj b)  
20:  {  
21:    return a.cost > b.cost;  
22:  }  
23:    
24:    
25:  //waitList[i] = waiting list of customer ids who can buy shoe i  
26:  vector<int> waitList[maxN];  
27:    
28:  //purchase[i] = shoe id that customer i actually purchased  
29:  //It is -1 if customer i did not purchase anything  
30:  int purchase[maxN];  
31:    
32:  //sold[i] = true if shoe i is sold  
33:  bool sold[maxN];   
34:    
35:  //returns true if shoe x is successfully purchased  
36:  bool buy(int x)  
37:  {  
38:    //you cannot buy what is already sold  
39:    if(sold[x]) return false;  
40:      
41:    //Shoe is x is now being sold to...  
42:    sold[x] = true;  
43:      
44:    //Let's decide who buys this shoe  
45:    for(int i=0; i < waitList[x].size(); i++)  
46:    {  
47:      int pot = waitList[x][i]; //potential customer id  
48:        
49:      /*  
50:       If the potential customer has not made any purchases,  
51:       or if somebody else can buy what he previously bought  
52:       (there is another person who can buy he has already purchased  
53:       */  
54:      if( purchase[pot] == -1 || buy( purchase[pot] ))  
55:      {  
56:        //the current potential customer takes this shoe  
57:        purchase[pot] = x;  
58:        return true; //successful purchase  
59:      }  
60:    }  
61:    //Every already bought other shoes  
62:    return false;  
63:  }  
64:    
65:  obj shoes[maxN]; //info on shoes  
66:  obj cus[maxN]; //info on customers  
67:  ll cost[maxN];  
68:    
69:  int main()  
70:  {  
71:    ios_base::sync_with_stdio(false);  
72:    int N,M;  
73:    cin>>N;  
74:    for(int i=0; i < N; i++)  
75:    {  
76:      cin>>shoes[i].cost>>shoes[i].size;  
77:      shoes[i].id = i;  
78:      cost[i] = shoes[i].cost;  
79:    }  
80:    
81:    sort(shoes, shoes+N, compSize);  
82:      
83:    cin>>M;  
84:    for(int i=0; i < M; i++)  
85:    {  
86:      cin>>cus[i].cost>>cus[i].size;  
87:      cus[i].id = i;  
88:    }  
89:      
90:    for(int i=0; i < M; i++)  
91:    {  
92:      int idx = int(lower_bound(shoes, shoes+N, obj(-1,cus[i].size,-1), compSize) - shoes);  
93:        
94:      while( shoes[idx].size == cus[i].size || shoes[idx].size == (cus[i].size + 1) )  
95:      {  
96:        if(shoes[idx].cost <= cus[i].cost)  
97:          waitList[shoes[idx].id].push_back( cus[i].id );  
98:        idx++;  
99:      }  
100:    }  
101:      
102:    sort(shoes, shoes + N, compCost);  
103:      
104:    memset(purchase, -1, sizeof(purchase));  
105:      
106:    for(int i=0; i < N; i++)  
107:    {  
108:      memset(sold, false, sizeof(sold));  
109:      buy( shoes[i].id );  
110:    }  
111:      
112:    ll total = 0LL;  
113:    vector< pair<int,int> >ans;  
114:      
115:    for(int i=0; i < M; i++)  
116:    {  
117:      if(purchase[i] == -1)  
118:        continue;  
119:        
120:      total += cost[ purchase[i] ];  
121:      ans.push_back( make_pair( i+1, purchase[i] + 1) );  
122:    }  
123:      
124:    cout<<total<<endl;  
125:    cout<<ans.size()<<endl;  
126:      
127:    for(int i=0; i < ans.size(); i++)  
128:      cout<<ans[i].first<<" "<<ans[i].second<<endl;  
129:      
130:    return 0;  
131:  }  

E - Tetrahedron
Approach
We need to find how many ways an ant can go from D to D without staying at one vertice for more than one turn.

 Fix first and last vertice as D.

 There are 4 vertex : A,B,C and D

 Then at each step, we have 3 vertex (our ant cannot stay at the current vertice) to move to.

 So there are 3^(N-2) possible routes from first vertex to last vertex.

 Note that at the (last - 1) step, the vertice cannot be D because our ant cannot stay at D.

 So we need to eliminate cases where (last-1) step ends at vertice D.

 Let ans(i) = answer to the question when (n == i).

 Then ans(i) = 3^(N-2) - ans(i-1)

Source Code

1:  int mod = 1000000007ll;  
2:    
3:  int main() {  
4:       int N;  
5:       cin >> N;  
6:    
7:       ll ans = 0;  
8:       if (N == 1) {  
9:            cout << 0;  
10:            return 0;  
11:       }  
12:      
13:       ll threes = 1;  
14:       ll prev = 0;  
15:       ll cur = 0;  
16:       for (int i = 2; i <= N; i++) {  
17:            threes = 3ll*threes;  
18:            cur = threes - prev;  
19:            if (cur < 0) cur +=mod;  
20:            threes %= mod;  
21:            cur %= mod;  
22:            prev = cur;  
23:       }  
24:         
25:       cout << cur;  
26:       return 0;  
27:  }