Amiri's blog

By Amiri, history, 4 years ago, In English

I prepared a problem similar to 851D - Arpa and a list of numbers 2 months ago and now I want share it with you :)

https://codefights.com/challenge/6yLzBLYAM3kkP4P7A

Read more »

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

By Amiri, 4 years ago, In English

I saw MDOLLS problem in this list was in LIS part and I was wondered how it can solved using LIS?

The question is:

Dilworth is the world's most prominent collector of Russian nested dolls: he literally has thousands of them! You know, the wooden hollow dolls of different sizes of which the smallest doll is contained in the second smallest, and this doll is in turn contained in the next one and so forth. One day he wonders if there is another way of nesting them so he will end up with fewer nested dolls? After all, that would make his collection even more magnificent! He unpacks each nested doll and measures the width and height of each contained doll. A doll with width w1 and height h1 will fit in another doll of width w2 and height h= if and only if w1 < w2 and h1 < h2. Can you help him calculate the smallest number of nested dolls possible to assemble from his massive list of measurements?

I know this problem can be solved by maximum bipartite matching tecnique but I want to know is there any way to solve using LIS?

If we have w1 <= w2 and h1 <= h2 instead of w1 < w2 and h1 < h2 I have an O(n2logn) solution using LIS as follow:

Initially we sort dolls by their w values (and h In the next priority) and then try to remove LIS from new order of dolls. number of times we can remove LIS from our dolls is the answer.

But it's obvious that my solution shouldn't work for original version of MDOLLS with w1 < w2 and h1 < h2 conditions.

Please help me to know is there a solution using LIS for MDOLLS?

Read more »

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

By Amiri, history, 4 years ago, In English

I found russian version of acm.sgu

russian version: http://acm.sgu.ru/olimp/

now, we can use web cache tools for reading problems and use russian version for judge submissions but I cannot understand why they deleted English version :(

UPD: it's not russian version of acm.sgu.ru :( it's just a judge with similar visual theme and I was deceived.

Read more »

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

By Amiri, history, 5 years ago, In English

My submission with long double give me WA: 19816873

My submission with double give me AC: 19816911

Is it a known bug? or I don't know a fact about fstream in CF?

Thanks in advance

Read more »

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