### pratikmoona's blog

By pratikmoona, 12 years ago,
Here I am sharing how I approached and solved the problems of the recently held Round 55 (DIV 2)

A. Word
This was an extremely simple problem. Simply count the number of upper case latin letters. If that is strictly greater than number of lower case letters convert the word to upper case other wise convert it to lower case.
Complexity: O(wordlength)

B. Fortune Telling
For this problem all you need to do is store the smallest odd number of petals and also the sum of all the petals. It is quite obvious that only if the number of petals is odd the result would be "Loves". So if the sum is even print sum - smallest odd, otherwise print the sum.
Complexity: O(n).

C. Title
This was a very nice problem. My approach was to first flag all the letters which have already appeared. Notice, that we have to output the lexicographically smallest palindrome. So, start from the middle of the letter and iterate one side...
If you get a '?' stop and check if the corresponding position on the other side also has a '?'. If yes, then fill both with the lexicographically biggest letter which hasn't appeared yet in the word and also flag that letter.
Once you have exhausted all the letters and there are still '?' left then simply fill them with 'a'.

Now simply iterate over the word again and see if there are any question marks left, if yes copy the values in the corresponding block on the other side. At the same time check if at any time the two opposite values match or not. If they do throughout then it is a valid plaindrome which is also the lexicographically smallest palindrome.

Here is a slightly messy implementation of the same: http://codepad.org/Fr7NYqYT
Complexity: O(wordlength + k)

D. Team Arrangement
This was in my opinion was the toughest problem. However once you get the logic, its pretty obvious. However, it was a slightly challenging implementation for me as the structure of the data to be stored was sort of complex.

The basic idea was simply that if we have to find the preference list of a number 'p' then two things might happen:
Case 1: p is the most skilled in his team and thus he chose the team. In this case we know that all the members of the teams coming after p's team are less preferred than p's team mates. Let p's team mates be 'm' and 'n' such that m > n.

To get the lexicographically smallest preference list, we will divide all the programmers into two lists. The first list will contain all members (ai) from teams which were chosen before p's team such that ai < m. It will also contain m and n.

The second list will contain all the left over members.

The separation can be done in O(n) time. Now all we need to do is sort the first list, print it, sort the second list, print it!

Complexity: O(nlogn)... It can be reduced to O(n) also but the constant will be pretty high and will give almost the same result as O(nlogn).

Case 2: p is not the leader of the team. Then you just have to output all number except 'p' from 1 to 3 * n.

As for the last problem, I do not have a solution. I do not have much experienced with implementing graphs unfortunately.

Please point out any optimizations to the above or mistakes which I might have made in the above.

• +12

 12 years ago, # | ← Rev. 5 →   +3 For problem D, you didn't state the second case:Case 2: p is not the leader of any team. Then his preference is totally useless to the whole team selection process, so we just output the set {1, 2, ... p-1, p+1, ... 3N}For Problem E: Simply a shortest path algorithm would do, you just need to maintain state dxy such that this contains the shortest distance from vertex 1 to vertex y so that the path looks like this:and inside the path there's no three consecutive vertices that are in the banned list.Hence the transition is simply:with d11 = 0. For checking whether a triple is banned, I just used STL map.
•  12 years ago, # ^ |   0 Thanks! I forgot to add case 2. I edited the post.
 » 7 years ago, # | ← Rev. 2 →   0 What's test 69 problem C. I can't see test case. I don't know why :( This is my submition : http://codepad.org/ybsxToCs
•  » » 7 years ago, # ^ |   0 Check this case: k = 2 , title = "?aba?"
•  » » » 7 years ago, # ^ |   +16 He wrote it 7 months ago...
•  » » » » 7 years ago, # ^ |   +1 So you thought that my comment is "stupid enough". I wrote this 4 months ago but i didnt find the bug till now.
 » 3 years ago, # |   0 Can someone please explain problem E ? Thanks.
•  » » 3 years ago, # ^ |   0 yup can anyone explain
•  » » » 2 years ago, # ^ |   0 you should find the shortest path from 1 to n without visiting banned roads . the banned roads are three consecutive nodes can't be visited in a row. hope you understand it
»
2 years ago, # |
0

Can anyone tell me what is wrong with my code? I don't understand how this won't work

# define mp make_pair

using namespace std; int pre[3001]={-1}; int dist[3001] ={INT_MAX}; vector adj[3001];

void dijkstra(map<pair<int,int>,int> map, int src, int n){ priority_queue <pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq; pq.push(make_pair(0,src)); dist[1]=0;

while (!pq.empty()){
pair<int,int> v= pq.top();
pq.pop();

int ver=v.second;
if (1+dist[ver]<dist[i] && map[mp(pre[ver],ver)] != i){
dist[i]=1+dist[ver];
pre[i]=ver;
pq.push(mp(dist[i],i));
}
}
}


}

int main() { ios_base::sync_with_stdio(false);cin.tie(0); int n,m,k; cin >> n >> m >> k;

map<pair<int,int>,int> map;

for (int i=0;i<m;i++){
int a,b;
cin >> a>>b;
}
for (int i=0;i<k;i++){
int a,b,c;
cin >> a>>b>>c;
map.insert({make_pair(a,b),c});
}
dijkstra(map,1,n);
if (dist[n]==INT_MAX) {
cout << -1; return 0;
}
cout << dist[n];
int x=n;
vector<int> route;

while (x!=-1){
route.push_back(x);
x=pre[x];
}
for(auto i=route.size()-1;i>-1;i--){
cout << route[i]<< "  ";
}
return 0;
`

}

•  » » 2 years ago, # ^ |   0 You didn't consider the banned triplet in your code. It will just work like BFS, which is very simple. But the BANNED TRIPLETS made this problem E- LEVEL. Even I have not get it's editorial
 » 16 months ago, # |   0 Can anyone provide editorial for problem E?
•  » » 16 months ago, # ^ |   0
 » 13 months ago, # |   -21 please someone provide explaination for problem E
 » 8 months ago, # |   0 Hint for Problem E: hintCreate an auxiliary graph G' whose vertices are the edges of the given graph G. Now, connect two vertices of G'(i.e, two edges of G) (a,b) and (b,c) iff (a,b,c) is not forbidden. Perform BFS to find the answer.Check my code for implementation: My solution
 » 7 months ago, # |   0 I dont know but something is wrong with the judge behind the word problem.