samiemad's blog

By samiemad, history, 9 years ago, In English

Today I participated in Codeforces Round 348 (VK Cup 2016 Round 2, Div. 2 Edition), I managed to solve the first three problems in a very good time.

I started with problem D. didn't take long to figure out the idea (I like it very much BTW :). I submitted and got TLE on pretest 11. I knew it was because of huge input so I added

ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

I know that with these three lines cin/cout becomes almost as fast as scanf/printf. so I resubmitted the problem and got pretests passed. I have about 40 minutes left so I move to the last problem.

So the system test finishes, and I am shocked that my solution for D got TLE on test 29!!! Although it runs in O(n) complexity!!!

After five long hours of waiting till I can submit again -_- ... I just changed cin/cout to printf/scanf and get ACCEPTED!

problem link: 669D - Little Artem and Dance

TL submission: 17493329

AC submission: 17500406

I don't think there is another unwanted solution with a close running time to this one!! (I believe O(n log n) solution would be fairly slower than O(n) )...

So I wonder why did they use this huge input and this very tight Time Limit??

I DON'T LIKE SCANF/PRINTF AND YOU SHOULDN'T MAKE ME USE THEM!!!

This is not the first time I see this issue, and I am not saying this for the ~200 places I lost for it. but I think problem setters should take extra care when setting the TL to deliver a fair and happy competition to all the users :)

I am wondering if anyone else ever had the same problem? this time or in another round??

I know I did but not in an official round so it didn't matter much!

My suggestions:

  • either stretch the TL so both solutions pass

  • or make the input a bit smaller so it won't have this HUGE impact on running time

  • or write a note at the end of the problem to use scanf/printf

  • or send an announcement that cin/cout will not be accepted

Full text and comments »

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

By samiemad, history, 9 years ago, In English

Hi Codeforces!

I'd like to invite you to participate in an online mirror of HIAST Collegiate Programming Contest 2015. (Higher Institute for Applied Science and Technology is one of the best academic Institution in Syria) The contest will be held on codeforces gym, and will start on Saturday 2/4/2016 at 10:00 AM UTC+2, registration will open 6 hours before the start time.

The contest consists of 10 problems, and you have 5 hours to solve them, ICPC rules.

The original contest was held in HIAST, Damascus, Syria as a qualification round to the Syrian Collegiate programming contest 2015.

The problems difficulty is easy-medium, although the problems are designed for new comers into the competitive programming world, but I believe that all Div2 participants will find very interesting problems to solve!

Some other Similar Contests are :

Although I believe this one is a bit easier than the previous contests.

I want to thank everyone who participated in the previous contests, I am glad you enjoyed them. I think you will like this one too.

I would like to thank codeforces community and MikeMirzayanov for the codeforces and polygon platforms.

Wish you all happy coding, and lots of greens! :D

Full text and comments »

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

By samiemad, history, 9 years ago, In English

Hi Codeforces!

I'd like to invite you to participate in an online mirror of AlBaath Collegiate Programming Contest 2015. The contest will be held on codeforces gym, and will start on Saturday 26/3/2016 at 10:00 AM UTC+2, registration will open 6 hours before the start time.

The contest consists of 11 problems, and you have 5 hours to solve them, ICPC rules.

The original contest was held in AlBaath University, Homs, Syria as a qualification round to the Syrian Collegiate programming contest 2015.

The problems difficulty is easy-medium, although the problems are designed for new comers into the competitive programming world, but I believe that all participants will find very interesting problems to solve!

It is an old contest, I know. but it is never too late to share good problems! (I hope) :)

I would like to thank codeforces community and MikeMirzayanov for the codeforces and polygon platform.

Wish you all happy coding, and lots of greens! :D

Full text and comments »

Tags gym
  • Vote: I like it
  • +17
  • Vote: I do not like it

By samiemad, history, 9 years ago, In English

Today I was participating in 2012-2013, Samara SAU ACM ICPC Quarterfinal Qualification Contest , We solved 12/13 problems ^_^. The problems were very interesting. :D

The one I couldn't solve was "H — Game with the Stones", even though I had a bit more than 2 hours to think about it, I only got WA on test 16...

I will explain where I got so far and please tell me what I am doing wrong.

at first I came up with this pattern for a single pile: L, W, L, W, W, W, L, W, W, W, L, W, W, W, L...

for every x%4 =  = 1 we can split it to (x - 2, 2) which is a losing position for the opponent.

for every x%4 =  = 3 there is no way to get a winning position no matter how we split it.

for every even x we can split it to (x - 1, 1) or (x - 3, 3) to get the opponent to a losing position x - 1 or x - 3..

so win if X%4! = 3 and lose otherwise...

I then noticed that we only care about the 'longest' pile.. and I found what would be the length of the pile (the number of turns until it gets all 1s)

I found this pattern for the length of a pile: 0, 1, 2, 3, 3, 3, 4, 5, 5, 5, 6, 7, 7, 7, 8 ...

length(x) = x / 2 + (x%4! = 2)

finally I look for the largest winning pile and make sure that all the other piles can be finished before it, meaning that length((ai + 1) / 2) is less than length(W). (W is the largest winning pile and ai are all the other piles)

this is my code

anyone have an idea what I am doing wrong here? and/or how to solve this problem?

I always have rough time with game theory problems.. so I am trying to get a better understanding on how to think analyze and come up with the solution...

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it