ahmed_aly's blog

By ahmed_aly, 12 years ago, In English

February — 2010

1- vepifanov: 267
* 1st in Codeforces Beta Round #1: +100 (from 1500 to 1600)
* 7th in Codeforces Beta Round #2: +91 (from 1600 to 1691)

2- gusakov: 251
* 9th in Codeforces Beta Round #1: +73 (from 1500 to 1573)
* 4th in Codeforces Beta Round #2: +107 (from 1573 to 1680)

3- RAVEman: 216
* 22nd in Codeforces Beta Round #1: +29 (from 1500 to 1529)
* 1st in Codeforces Beta Round #2: +126 (from 1529 to 1655)

4- RAD: 189
* 10th in Codeforces Beta Round #1: +70 (from 1500 to 1570)
* 19th in Codeforces Beta Round #2: +65 (from 1570 to 1635)

5- GARNETCROW_a.k.a_hhanger: 184
* 2nd in Codeforces Beta Round #2: +132 (from 1500 to 1632)

You can check how are the above scores calculated here: http://codeforces.com/blog/entry/5169

Full text and comments »

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

By ahmed_aly, 12 years ago, In English

1- climpet: 503
* 269th in Codeforces Round #133 (Div. 2): +27 (from 1558 to 1585)
* 100th in Codeforces Round #134 (Div. 2): +81 (from 1585 to 1666)
* 53rd in Codeforces Round #135 (Div. 2): +70 (from 1666 to 1736)
* 52nd in Codeforces Round #136 (Div. 1): +154 (from 1736 to 1890)

2- TarasSavitskyi: 503
* 57th in Codeforces Round #132 (Div. 2): +146 (from 1528 to 1674)
* 94th in Codeforces Round #133 (Div. 2): +34 (from 1674 to 1708)
* 50th in Codeforces Round #134 (Div. 1): +126 (from 1708 to 1834)

3- I_love_Nastya: 433
* 30th in Codeforces Round #134 (Div. 1): +93 (from 1979 to 2072)
* 29th in Codeforces Round #136 (Div. 1): +96 (from 2072 to 2168)

4- Eurekash: 408
* 15th in Codeforces Round #133 (Div. 2): +86 (from 1664 to 1750)
* 64th in Codeforces Round #136 (Div. 1): +144 (from 1750 to 1894)

5- Furko: 401
* 21st in Codeforces Round #134 (Div. 1): +119 (from 1896 to 2015)
* 69th in Codeforces Round #136 (Div. 1): +71 (from 2015 to 2086)

You can check how are the above scores calculated here: http://codeforces.com/blog/entry/5169

Full text and comments »

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

By ahmed_aly, 12 years ago, In English

Hi everyone,

I've just finished implementing some Codeforces tools, you can find it here: http://ahmed-aly.com/voc/Codeforces.jsp

This page contains some statistics in 11 different categories, with the top 5 coders in each category, and you can display some statistics for a single coder also which will display many statistics which are very hard to retrieve from Codeforces itself.

Thanks.

Full text and comments »

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

By ahmed_aly, 12 years ago, In English

1- iroro: 385
* 119th in Codeforces Round #128 (Div. 2): +59 (from 1607 to 1666)
* 6th in Codeforces Round #129 (Div. 2): +87 (from 1666 to 1753)
* 62nd in Codeforces Round #131 (Div. 1): +91 (from 1753 to 1844)

2- vlad107: 358
* 42nd in Codeforces Round #129 (Div. 1): +92 (from 1923 to 2015)
* 36th in Codeforces Round #131 (Div. 1): +64 (from 2015 to 2079)

3- DamianS: 339
* 22nd in Codeforces Round #129 (Div. 1): +93 (from 2028 to 2121)
* 25th in Codeforces Round #131 (Div. 1): +55 (from 2121 to 2176)

4- sweetsc: 337
* 10th in Codeforces Round #128 (Div. 2): +154 (from 1531 to 1685)
* 84th in Codeforces Round #130 (Div. 2): +39 (from 1685 to 1724)
* 134th in Codeforces Round #131 (Div. 1): +34 (from 1724 to 1758)

5- learningSister: 334
* 30th in Codeforces Round #129 (Div. 1): +73 (from 2068 to 2141)
* 11th in Codeforces Round #131 (Div. 1): +73 (from 2141 to 2214)

You can check how are the above scores calculated here: http://codeforces.com/blog/entry/5169

Full text and comments »

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

By ahmed_aly, 12 years ago, In English

Hi everyone,

I like the idea of coder of the month which is already done in many online judges, but not in Codeforces.

So, I'm going to make a coders-of-the-month post by the end of every month, which will contain the top 5 coders of the month, not only top 1.

I'll calculate a score for every coder who participated in at least 1 rated contest during this month, this score will be simply the sum of his/her rating changes during this month, with the following rules:

1- The very first 5 rated contests for a coder will not affect his score.

2- A rating increase will be multiplied by a factor from 0.5 to 3.0, this factor will be higher if the coder's rating before the contest is higher.

3- A coder with score less than or equal to -600 for the previous 2 months combined together (without the 1st rule) will not be in the coders-of-the-month list for this month.

For sure the coders-of-the-month list will contain the top 5 coders with a positive score.

If you have a better idea to calculate this score or you have a modification for my idea, please post it here so we can discuss it.

Here is a example for coders of July 2012: http://codeforces.com/blog/entry/5170
And another example for coders of August 2012: http://codeforces.com/blog/entry/5183
And all coders of the month from February 2010 to June 2012 here: http://codeforces.com/blog/entry/5184 (the first few months are without the 1st rule)

Thanks.


Edit: Added Shafaet's idea.

Full text and comments »

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

By ahmed_aly, 12 years ago, In English

I've just fixed all the bugs in VOC which are related to Codeforces. Now you can use any problem from Codeforces problemset in your contests, and also you can add a complete Codeforces contest to a VOC contest. And the number of solved problems for each registered user is fixed, this number represents the number of solved problems during all contests, even if the user was unofficial participant, but solving problems as virtual participant doesn't count, and this problem should be listed in Codeforces problemset.

Full text and comments »

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

By ahmed_aly, 12 years ago, In English

1- The maximum number of successful hacks made by the same user in the same contest is 39, made by Kenny_HORROR in Codeforces Beta Round 60: standings 1st place.

2- The maximum number of unsuccessful submissions before getting a problem accept in a contests is 81, made by shahbox in Codeforces Beta Round 44 (Div. 2): standings 518th place.

3- The user who solved the maximum number of problems during all Codeforces contests is Egor, he solved 453 problems.

4- The user who made the maximum number of successful hacks during all Codeforces contests is Egor again, he made 358 successful hacks.

5- The user who participated in the maximum number of Codeforces contests is PAG, he/she participated in 130 contests.

6- The maximum number of unsuccessful hacks made by the same user in the same contest is 150, made by dragan224 in Codeforces Round 109 (Div. 2): standings 1434th place.

7- The user who made the maximum number of unsuccessful hacks during all Codeforces contests is sdryapko, he made 154 usuccessful hacks.

8- The user who used the maximum number of different programming languages during Codeforces contests is K_operafan, he/she used these 11 languages: Io, Befunge, C#, Pike, C, Ruby, Roco, Tcl, C++, Java, Cobol.

9- The user who solved more than 50 problems during Codeforces contests with the maximum percentage of first-submission-accepted problems is KOTEHOK, he solved 57 problems and 54 of them were accepted from the first submission, with percentage ~ 95%.

10- The user who made more than 50 hacks during Codeforces contests with the maximum percentage of successful hacks is vepifanov, he made 56 hacks and 52 of them were successful, with percentage ~ 93%.

P.S. The above statistics is calculated for all contests before Codeforces Round #131, and unofficial participants are counted, but virtual participants are not count, and this information might not be 100% accurate.

Edit 1: Number 8, 9 and 10 are added.

Edit 2: An always updated version of this post can be found here.

Edit 3: This page now shows the top 5 in each category, but in different order and number 3 is new one. And can display statistics for a single user also.

Full text and comments »

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

By ahmed_aly, 12 years ago, In English

bmerry won the last Div2-Only contest with a big margin, even after including the out of competition coders, and it was his first contest. He is still in Div2, I think if someone got a very good rank in his first contest, his new rate should be in Div1, like in TopCoder you jump directly to yellow.

Edit: And now just +79 for winning Div2 again!

Full text and comments »

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

By ahmed_aly, 12 years ago, In English

Hi everyone,

I've just finished some updates in TopCoder Tools website, and here is the summary of my updates: 1 — In the Match Results page, you can now filter by one or more schools.

2 — Added the Countries page, which includes all countries listed here, and you can view the coders for each country and the table includes the school and the number of competitions.

3 Added the Schools page, which includes all schools listed here, and you can view the coders for each school and the table includes the country and the number of competitions.

I hope that you will like these changes and find it useful.

Full text and comments »

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

By ahmed_aly, 12 years ago, In English

Registration for IPSC 2012 has now started.

Full text and comments »

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

By ahmed_aly, 12 years ago, In English

Hi everyone,

Finally, after almost 4 months of discussion between me and TopCoder admins, and I'd like to say thanks to all TopCoder admins (specially mike).

Now you can use TopCoder problems in the Virtual Online Contests website. You can create contests using TopCoder problems only (and this will be TopCoder rules), also you can mix between TopCoder problems and problems from the other 9 supported online judges (and this will be ACM rules).

You can add TopCoder problems one by one, or generate some random problems, or select a complete practice room (you can use more than 1 practice room in the same contest).

Unfortunately, I can't check if your submission is passed the system test or not, so after the end of the contest you will need to run the system test manually in the arena, and update the result manually also in the scoreboard.

First you need to sign up (if you don't have an account) and you should include your TopCoder handle in your account, then you can create and participate in TopCoder virtual contests.

I created a test contest which will be running for 2 weeks so that you can try the this new feature. You can register in this contest here: http://ahmed-aly.com/voc/Register.jsp?ID=541

P.S. If the same problem is available in 2 practice rooms, you can submit in anyone.

Thanks, Ahmed Aly

Full text and comments »

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

By ahmed_aly, 12 years ago, In English

Hi everyone,

I'll run a weekly contest on VOC. This contest will consist of 5 problems from UVa and 5 problems from SPOJ. All the selected problems will not be solved by anyone of the registrants. So the registration for this contest will be closed 5 minutes before the start time.
The contest time will be 2011-10-29 15:00:00 UTC, you can check the start time in your time zone here, and you can register for the contest here.

Full text and comments »

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

By ahmed_aly, 13 years ago, In English

Hi everyone,

The ACM-ICPC regionals are coming soon, and everyone is practicing, and for sure you may need to run a practice contest.
So I made a new website which will help to organize and run virtual online contests easily, and this website will support 9 online judges (UVa, SPOJ, Live Archive, Codeforces, TJU, SGU, PKU, Timus, ZOJ). And the same contest can contain different problems from all these online judges. You don't need to install any software, you just need an account.
This is the website link http://ahmed-aly.com/voc and you can check the FAQ page for more information.

If you already have an account in UVa And SPOJ website, you can sign in using the same username and password, just make sure to verify your account, and check your account page to add more accounts and change some default preferences.

Also there is a running contest which contains one easy problem from each online judge, you can register for this contest here http://ahmed-aly.com/voc/Register.jsp?ID=20

If you have any suggestion or feedback, please feel free to say it.

P.S. Check this page http://ahmed-aly.com/voc/Finder.jsp it's very helpful (at least for me).

Thanks,
Ahmed Aly

Full text and comments »

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

By ahmed_aly, 13 years ago, In English
Will it be live or re-run of the onsite contest?
Will it be rated?

Full text and comments »

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

By ahmed_aly, 13 years ago, In English
This is my approach for this problem, and I don't know why it's wrong.

1- Let X be the smallest power of 2 which is greater than or equal to N.
2- Let X = 2 ^ P.
3- Make P tosses to generate a random binary number consisting of P bits, let's call it I.
4- If I is less than N, so the king selects the Ith knight (0-indexed).
5- Otherwise, repeat again starting from step 3.

Now the final result should be:
F(N) = P + [(X - N) / X] * F(N)
F(N) - [(X - N) / X] * F(N) = P
F(N) * (1 - [(X - N) / X]) = P
F(N) = P / (1 - [(X - N) / X])

I'm sure this will select a knight with equal probability, but I'm not sure if it's the minimum expected number of tosses.

Is there anything wrong in my approach or is it my calculations?

Full text and comments »

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

By ahmed_aly, 13 years ago, In English
I don't know which criteria is used to select the problems difficulty. In round 78 DIV 1, almost the last 4 problems were solved by the same number of coders which is about 20 coders, and the first problem was solved by about 200 coders. These numbers don't make sense at all. Also this is not the only contest with this situation, it happened in many contests which was much harder than expected.
Another thing which I pointed before, and it's still exist, the problem stories are pretty long, why should I read more than 50% of the problem statement then I find it's completely useless?!

Codeforces admins, please give more attention to the problems in the contests.

Full text and comments »

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

By ahmed_aly, 13 years ago, In English

Hi everyone,

Here are some notes about GCJ tools website during round 1A:

1- 191,538 database queries were executed during the contest.
2- The final result for this round is available now.
3- The live scoreboard had some bugs during the contest, but everything is fixed now.
4- I spent more than half of the contest debugging and fixing bugs in the live scoreboard.
5- The whole scoreboard was updated 839 times during the contest.
6- The average time for each single update was 10 seconds.

--

Best Regards,
Ahmed Aly

Full text and comments »

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

By ahmed_aly, 13 years ago, In English

Hi everyone,

I've just added a new feature to GCJ Tools website, I think it will be very useful during the contests.
You will be able to create custom lists of any number of contestants (in GCJ you can make at most 30 friends only).
And you will be able to see the results for any list during the contest itself, and it will be almost synchronized with the actual results (just few seconds delay to be updated).
Also you will be able to see the results for any country during the contest itself, and it will be synchronized too.
And for sure you can see the results for any list in any of the previous contests.

You can check the current lists in this page, and you can create new lists in the same page but you must be logged in.
To add users to any list that you made, just click on its name in this page, and you will be able to update, delete or add contestants to this list.
To view the result for any list, you can do it from the page for this list, or from the results page.

Hope you will like it.

--
Best Regards,
Ahmed Aly

Full text and comments »

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

By ahmed_aly, 13 years ago, In English
1- Codeforces contests now are more stable than TopCoder contests, there were about 2200 registrants today (not all of them participated) and the contest ran smoothly (at least for me).

2- I like Codeforces contest format more than TopCoder contest format, the contest contains more problems and more time, and I like Codeforces hacking more than TopCoder challenges.

3- Codeforces now makes much more contests than TopCoder.

4- I like Codeforces problems quality and difficulty levels more than TopCoder.


Now Codeforces is number 1 for me and TopCoder is number 2, I love Codeforces.

Full text and comments »

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

By ahmed_aly, 13 years ago, In English

Hi everyone,

I would like to announce about my new Google Code Jam tools website, you can find it here.

This is a list of some features in this website:
1- You can see the results for any country in any GCJ round.
2- You can see the results for anyone in all GCJ rounds.
3- You can compare the results for any 2 contestants in all GCJ round.
4- You can challenge anyone to beat him in the next GCJ rounds.
5- You can see a list of all challenges for everyone.
6- You can see a list of all registered users with some GCJ stats and some challenges stats.
7- You can share anything on Facebook.

You can see the challenges rules in the homepage.

If you are going to register, please make sure to read the notes in the registration page carefully.

- The result of the qualification round is added.
- All challenges are evaluated now.
- You can start challenging for the next round.


Hope you will like it.

--
Best Regards,
Ahmed Aly

Full text and comments »

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

By ahmed_aly, 13 years ago, In English
I've noticed in the last few Codeforces contests that almost all problem statements are very long and contain a lot of useless parts.
For example in this problem, the first 4 paragraphs are completely useless, which is about 40% of the problem description.
I don't see any fun in reading a lot of useless parts, and I used to read and understand everything carefully because it could contain something important.
Why should I waste the contest time in reading and understanding useless parts?
I wish to see smaller and more direct description in the next contests.

What do you think about this?

Full text and comments »

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

By ahmed_aly, 13 years ago, In English
Problem A:
In this problem you need to do what is written in the statement. You can do it in the following 3 steps:
1- Calculate C.
2- Remove all zeros from A, B and C.
3- Check if the new values form a correct equation.

C++ solution for problem A.


Problem B:
This problem is a direct simulation to the rules written in the problem statement.
You need to iterate over all actions and parse each one to know the type of the action, and the 2 names X and Y, and if your name is X or Y then update your priority factor with this person with the action corresponding value. And take care about some special names like "post", "wall", "commented" and "on".
Then sort all names according to the sorting criteria mentioned in the statement.
Just make sure to print all names which are mentioned in the input (excluding yourself), even if the priority factor with you is 0.

C++ solution for problem B.


Problem C:
In this problem you will need to generate all common divisors between a and b before answering any query.
The first step in this problem is to factorize a and b, you can use the trial division technique which runs in O(sqrt(N)), you can check getFactors function in my solutions.
Then using a recursive function you can generate all divisors for a and b from their prime factors, you can check getDivisors function in my solutions.
Then intersect the 2 sets of divisors for both to get all common divisors, you can do this in O(N+M) where N and M are the lengths of the 2 sets, and also you can do a trivial O(N*M) intersection algorithm, because the maximum number of divisors is not too big (it's 1344).
Now for each query you need to find the largest common divisor which lies in the given range, you can do this by sorting all common divisors and do binary search for the largest one which lies in the given range. Also you can do this using linear search, because the total number of queries is not too big.

Also there is much shorter solution for this problem. Here is a hint for it, the GCD between a and b should be dividable by all common divisors of a and b.

C++ solution for problem C (with binary search).
C++ solution for problem C (without binary search).
Java solution for problem C (with binary search).


Problem D:
This problem is my favorite one in this problem set. Maybe it will be easier to solve this problem if you know how to solve the standard one.
But because we can't construct the big array, so we can't apply the standard solution for this problem.
Let's see first how to solve the standard problem, the following code solves it for a given array arr with length len:

int mx = -(1 << 30);
int sum = 0;
for (int j = 0; j < len; j++) {
    mx = max(mx, arr[i]); // we need this for the case where all elements in the array are negatives
    sum += arr[i];
    if (sum < 0)
        sum = 0;
    else
        mx = max(mx, sum);
}

Now let's solve the big array problem, the first step is to calculate 4 values for each small array:
1- The total sum of it, let's call it tot.
2- The maximum sum of 0 or more consecutive elements starting from the first element in the array, let's call it lft.
3- The maximum sum of 0 or more consecutive elements ending at the last element in the array, let's call it rght.
4- The maximum sum of 1 or more consecutive elements, let's call it gen.

The final result will be 1 of 2 cases:
1- The consecutive elements with the maximum sum will start and end inside the same small array.
2- The consecutive elements with the maximum sum will start and end inside different small arrays.

For the first case, we can simply pick the maximum gen for all small arrays which exist in the big array.
For the second case, we can apply something similar to the standard solution, we will keep a variable called sum, and it's initialized to 0, this will be the maximum sum of 0 or more consecutive elements ending at the last element in the previous small array. Now for each small array, if the maximum possible sum will end in this small array, so it will be sum+lft and maximize over this value (make sure this will be for 1 or more elements). And we need to update sum to be the maximum of the following 3 values:
1- sum+tot (we will include all elements of this small array to the old sum).
2- rght (we will take the maximum sum ending at the last element in the current small array).
3- 0 (we will not take any elements in sum).

The running time for this solution will be just for reading the input, in my solutions I have no iterations except for reading the input.

You can check my solutions for more clarification.

C++ solution for problem D.
Java solution for problem D.


Problem E:
The main idea for this problem is not hard, but maybe the hard part is implementing it.
First we need to know if the straight line segment between the source and destination points intersect with the island or not. So we will intersect this line segment with all the polygon sides. If there are 2 segments intersect in more than 1 point we will consider as they don't intersect, because it's mentioned in the problem statement that you can move on the island's edge and it will be considered in the sea.
Now we have a set of all distinct intersection points of the polygon and the straight line segment between the source and destination points. Because the polygon is convex, this set will contain at most 2 points. We have 3 different cases now:
1- This set contains less than 2 points.
2- This set contains 2 points and they are on the same polygon side.
3- This set contains 2 points and they are not on the same polygon side.

In the first 2 cases the result will be simply the length of the straight line segment.
In the 3rd case you can do the following:
1- Move from the source point to the nearest point of the 2 intersection points.
2- You have 3 options here:
    a- Move inside the island to the other intersection point.
    b- Move in clockwise direction on the island's edge to the other intersection point.
    c- Move in anti-clockwise direction on the island's edge to the other intersection point.
    First option will be considered moving inside the island, and the other 2 options will be considered moving in the sea.
    You should pick the minimum one.
3- Move from the 2nd intersection point to the destination point.

Another solution:
You can construct a graph where the nodes are the source point, the destination point, the intersection points and the polygon corner points. Then add an edge between any 2 points which you can move between them with the corresponding cost. Then run any shortest path algorithm, Floyd Warshall for example.

You can check my solutions for more clarification.

C++ solution for problem E.
C++ solution for problem E (with Floyd Warshall).

Full text and comments »

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

By ahmed_aly, 13 years ago, In English
Hi everyone,

Today I'll be the author for this round, and it's my first time to be an author in Codeforces. I hope you will like the problems and find it interesting, even for Div1 coders.

I would like to say thanks for Artem Rakhov for solving and testing the problems, for Maria Belova for preparing the problem statements, and for Mike Mirzayanov for this great system.

Good luck and have fun.

Edit 1: Congratulation to the winner Chubcheg.
Edit 2: The problem editorial is here.

Full text and comments »

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

By ahmed_aly, 13 years ago, In English
Will we have just 1 contest in April?

Full text and comments »

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

By ahmed_aly, 13 years ago, In English
Hi everyone,

Finally I did it, now you can filter Codeforces users by country.
Just go to this page and select the country and click view table.

I found that many Codeforces users didn't write a country in their profile,
but I have a TopCoder Tools website and I have all TopCoders countries in my database,
and I assumed that many users have the same usernames in TopCoder and Codeforces.
So if the country is unknown for a Codeforces user and I found a TopCoder account with the same username,
I assigned the TopCoder country to this Codeforces user.
I know that this way could assign someone the wrong country, but it will happen with low probability.
Also I got the country using this way for 1318 Codeforces users with unknown country, which I think it's very good number.

If you have just added or changed your country, you can go to this page, and write your username and click update my country, and it will be updated in my database too.
You don't need to enter your country in my website, just update it in Codeforces and do the above steps.

Anyway, if you found that your country is selected incorrectly, please send a message to me and I'll fix it.

I hope that you will find this useful.

Full text and comments »

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