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:  }