A.K.Goharshady's blog

By A.K.Goharshady, 4 years ago, In English,

Hi, Here's the editorial.

Please note that not all the codes presented below belong to me. (It's a combination of codes from our problemsetters and testers) -- And I borrowed AKGMA's account since I wasn't able to link to my own submissions somehow!

Note: It seems that the Codeforces mark-up is not functioning. To see a submission go to: http://www.codeforces.com/contest/282/submission/submission-number

A: Bit++

Just use a simple loop. (Take a look at the Python code)

GNU C++: 3314442, 3314464

GNU C: 3314471

Python: 3314475

B: Painting Eggs

This one can be solved by a greedy algorithm. Start from the 1st egg and each time give the egg to A if and only if giving it to A doesn't make the difference > 500, otherwise give it to G.

To prove the correctness, one can use induction. The base case is trivial. Suppose that we've assigned the first n - 1 eggs such that the total money given to A is Sa and total money given to G is Sg. We can assume Sa ≥ Sg. Now we must either add gn to Sg or add an to Sa. If we can't add gn to Sg, then Sg + gn > Sa + 500, so  - 500 > Sa - Sg - gn, adding 1000 to both sides gives us the inequality 500 > Sa + (1000 - gn) - Sg which is exactly what we need to make sure that we can add an = 1000 - gn to Sa.

GNU C++: 3314480, 3314484

GNU C: 3314488

Python: 3314492

C: XOR and OR

First of all, check the length of the two strings to be equal. Then with a little try and guess, you can find out that the zero string (00...0) can't be converted to anything else and nothing else can be converted to zero. All other conversions are possible.

GNU C++: 3314503, 3314504, 3314509, 3314512, 3314514

D: Yet another Number Game

For n=1, everything is clear. If a1 = 0 then BitAryo wins, otherwise BitLGM is the winner.

For n=2: define win[i][j] = (Whether i,j is a Winning position). It's easy to calculate win[i][j] for all i and j, using a loop (Checking all possible moves). This leads us to an O(n3) solution.

For n=3: Everything is similar to NIM, With the same statement of proof as for NIM, i,j,k is a winning position if and only if (i xor j xor k)  ≠ 0.[Don't forget the parentheses in code :) ] Complexity: O(1)

One can also solve this case using DP. We define lose[i][j]= (Least k, such that i,j,k is a losing position) ,lose2[i][j]=(Least k, such that k,k+i,k+i+j is a losing position) and win[i][j][k] just as the case with n=2. As in the codes below, one can calculate all these values in O(n3).

Using the same DP strategy for n=2 and the O(1) algorithm for n=3 and n=1, leads us to a total complexity of O(n2) which was not necessary in this contest.

GNU C++: 3314578, 3314580, 3314585, 3314588

E: Sausage Maximization

Can be solved using a trie in O(n log (max{ai})).

Start with a prefix of size n, and decrease the size of prefix in each step. For each new prefix calculate the XOR of elements in that prefix and add the XOR of the newly available suffix (which does not coincide with the new prefix) to the trie, then query the trie for the best possible match for the XOR of the new prefix. (Try to get 1 as the first digit if possible, otherwise put 0, then do the same thing for the second digit and so on). Get a maximum over all answers you've found, and it's all done. [By digit, I mean binary digit]

GNU C++: 3314616, 3314619

We hope you enjoyed the tasks.

Read more »

 
 
 
 
  • Vote: I like it  
  • +50
  • Vote: I do not like it  

By A.K.Goharshady, 5 years ago, In English,

I think virtual contest must end as soon as all problems are solved.

It's quite unfit for it to continue while the user can do nothing more.

Read more »

 
 
 
 
  • Vote: I like it  
  • +19
  • Vote: I do not like it  

By A.K.Goharshady, 6 years ago, In English,
I wrote this post to help my friend , Iman Movahhedi , complete this one.
Round #40 was my first contest here in Codeforces and I feel I fell in love with CF just after that.

A-Translation: (C# code)
Many languages have built-in reverse() function for strings. we can reverse one of the strings and check if it's equal to the other one , or we can check it manually. I prefer the second.

Read more »

 
 
 
 
  • Vote: I like it  
  • +21
  • Vote: I do not like it  

By A.K.Goharshady, 6 years ago, In English,

Hear the song Here
این ترانه را از اینجا بشنوید

Read more »

 
 
 
 
  • Vote: I like it  
  • -11
  • Vote: I do not like it  

By A.K.Goharshady, 6 years ago, In English,

Hi all!

Unknown language round #1 was up, 21st of February and now we're going to hold yet another Unknown language round.

It will be the usual ACM-ICPC unrated contest , so there is no hacking! The only feature - you will be able to submit problems using the only one, not very popular language. What? It's a secret! And I expect you'll have to learn the language at the time of contest since the used language will be a secret until ~1 minute before the start of contest.

Problem setters of this round are Alireza FarhadiSaeed IlchiSajjad GhahramanpourZahra Rohanifar and Me. We are extremely grateful to Mike Mirzayanov and Artem Rakhov.

Number of problems will be more than usual and the problems concentrate on coding abilities rather than algorithmic view and problem solving techniques.

UPD:The contest is over

Congratulations to the top 3 winners who solved all problems:

Wrong

tomek

watashi


Read more »

Announcement of Unknown Language Round #2
 
 
 
 
  • Vote: I like it  
  • +52
  • Vote: I do not like it  

By A.K.Goharshady, 6 years ago, In English,
 
 
 
 
  • Vote: I like it  
  • +5
  • Vote: I do not like it  

By A.K.Goharshady, 6 years ago, In English,
This post is written to help my friend , Iman , complete this one.
Problem A: Triangle (code)
For each of the possible combinations of three sticks , we can make a triangle if sum of the lengths of the smaller two is greater than the length of the third and we can make a segment in case of equality.

Read more »

 
 
 
 
  • Vote: I like it  
  • +3
  • Vote: I do not like it  

By A.K.Goharshady, 6 years ago, In English,
 
 
 
 
  • Vote: I like it  
  • +4
  • Vote: I do not like it  

By A.K.Goharshady, 6 years ago, In English,
This one can be solved in O(nlgn) using a segment tree.
First we convert all powers to numbers in range 0..n-1 to avoid working with segments as large as 109 in our segment tree. Then for each of the men we should find number of men who are placed before him and have more power let's call this gr[j]. When ever we reach a man with power x we add the segment [0,x-1] to our segment tree , so finding gr[j] can be done by querying power of j in our segment tree when it's updated by all j-1 preceding men.
Now let's call number of men who are standing after j but are weaker than j as le[j]. These values can be found using the same method with a segment-tree or in O(n) time using direct arithmetic:
le[j]=(power of j -1)-(i-1-gr[j])
note that powers are in range 0..n-1 now.
Now we can count all triplets i,j,k which have j as their second index. This is le[j]*gr[j]
so the final answer is 

( \sum_{j=0}^{n-1} le[j]\times gr[j] )

Read more »

 
 
 
 
  • Vote: I like it  
  • +1
  • Vote: I do not like it  

By A.K.Goharshady, 6 years ago, In English,
This one has two different linear-time solutions. Greedy and dynamic programming.

Greedy solution:
You should stop at the city with maximum distance from the root (city number 1). So all roads are traversed twice except for the roads between the root and this city.

Dynamic Programming:
For each city i we declare patrol[i] as the traverse needed for seeing i and all of it's children without having to come back to i (Children of a city are those cities adjacent to it which are farther from the root) and revpatrol[i] as the traverse needed to see all children of i and coming back to it. we can see that revpatrol[i] is sum of revpatrols of its children + sum of lengths of roads going from i to its children. patrol[i] can be found by replacing each of revpatrols with patrol and choosing their minimum.


Read more »

 
 
 
 
  • Vote: I like it  
  • +8
  • Vote: I do not like it  

By A.K.Goharshady, 6 years ago, In English,
The code for converting decimal numbers to Roman was on Wikipedia , so I'm not going to explain it.
Since we have the upper limit 1015 for all of our numbers , we can first convert them to decimal (and store the answer in a 64-bit integer) and then to the target base.
For converting a number to decimal we first set the decimal variable to 0, then at each step we multiply it by the base and add the left-most digit's equivalent in base 10.
We had some tricky test cases for this one which got many people :
test #51:
2 10
0
many codes printed nothing for this one, this was also the most used hack for this problem

test #54:
12 2
000..00A
a sample of having initial zeros in input

test #55:
17 17
0000000...000
There were many people who just printed the input if bases were equal

there were two nice extremal hacks:
2 R
101110111000 
and
10 2
1000000000000000

Read more »

 
 
 
 
  • Vote: I like it  
  • +4
  • Vote: I do not like it  

By A.K.Goharshady, 6 years ago, In English,
In this problem signs can be ignored in both initial and answer strings, so first we remove signs from initial strings. Then we make a list of the six possible concatenations of the 3 initial strings and convert all of them to lowercase.
For checking an answer string , we remove the signs , convert it to lowercase and check if it is just one of those 6 concatenations.

There were two really nice hack protocols , the first one is:
-------__________;
_____;
;;;;---------_
2
ab____
_______;;;

Here all concatenations become empty.

The second one was putting 0 as number of students :D

Read more »

 
 
 
 
  • Vote: I like it  
  • +8
  • Vote: I do not like it  

By A.K.Goharshady, 6 years ago, In English,
Problem A:
This was indeed the easiest problem. You just needed to XOR the given sequences.
The only common mistake was removing initial 0s which led to "Wrong Answer"
Common mistake in hacks which led to "Invalid Input" was forgetting that all lines in input ends with EOLN.


Read more »

 
 
 
 
  • Vote: I like it  
  • +1
  • Vote: I do not like it  

By A.K.Goharshady, 6 years ago, In English,
سلام
بسیار مفتخرم که شما را به شرکت در پنجاه و هفتمین کانتست دعوت کنم.
طراحان این کانتست علیرضا فرهادی و من هستیم

همچنین از زحمات مایک میرزایانف - آرتم راخف - سعید ایلچی - محمدجواد نادری - جرالد آگاپف  و ماریا بلوا نهایت تشکر را داریم

به مناسبت روز ملی مهندس این کانتست را به خواجه نصیرالدین توسی تقدیم می کنیم


در این کانتست برای اولین بار صورت سوالها به زبان پارسی هم منتشر می شود.
می توانید صورت سوالها را پس از شروع کانتست از اینجا ببینید

کانتست به پایان رسید
:برنده

Read more »

 
 
 
 
  • Vote: I like it  
  • +8
  • Vote: I do not like it  

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

Read more »

 
 
 
 
  • Vote: I like it  
  • -1
  • Vote: I do not like it