A.K.Goharshady's blog

By A.K.Goharshady, 13 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

| Write comment?
13 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.
»
5 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