A.K.Goharshady's blog

By A.K.Goharshady, 12 years ago, In English
This is a semi-Tutorial for codeforces #42 (Div.2) , I'm not going to explain everything but I'm just telling the ideas.
The problems were extremely nice.

A) This is pretty obvious , you can store the two strings and how many times each of them occurred
B) For each of the upper or lower case letters , take care about how many times it appeared in each of the strings. if for a character x , repetitions of x in the second string is more than the first string , we can't make it , otherwise the answer is YES.
C) We all know that the remainder of a number when divided by 3 is equal to the remainder of sum of its digits when divided by three. So we can put all of input numbers in 3 sets based on their remainder by 3. Those with remainder 1 can be matched with those with remainder 2 and those with remainder 0 can be matched with themselves. so the answer is:
half of number of those divisible by three + minimum of those having a remainder of 1 and those having a remainder of 2
D) Actually we're looking for an Eulerian tour. I found it like this:
If at least one of m and n was even do it like this figure:

else do it like this and add a teleport from last square to the first:

But there were really nice hacks as I studied them. like these two:
1 10
and
1 2

E) Let's just take care about 2 cars and see how many times they change their position. This is easy. Then do this for all cars :D
 
 
 
 
  • Vote: I like it
  • -1
  • Vote: I do not like it

12 years ago, # |
  Vote: I like it +1 Vote: I do not like it
Don't trust google-translator. This translation to Russian is awful :) But don't worry, there are a lot of analysis in Russian for this round already.
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Here's a little proof of why do we need atleast 1 teleporter in case n and m are both odd: Link

»
7 months ago, # |
  Vote: I like it -26 Vote: I do not like it

include<bits/stdc++.h>

using namespace std; int main(){ int n; map<char,int>m; int mx =INT_MIN; cin>>n; while(n--){ string s; cin>>s; for(int i=0;i<s.length();i++) { m[s[i]]++; mx=max(m[s[i]],mx); } } listl; for(auto it:m) { if(it.second==mx) { l.push_back(it.first); } } // l.reverse(); for(auto it:l) { cout<<it; } return 0; }

a solution