Noureldin's blog

By Noureldin, 3 years ago, In English

Codeforces rounds are shorter than the ICPC world finals (40-50% the time of ICPC contests). Yet, the ICPC world finals is not equivalent to 2 Codeforces rounds. It wouldn’t have 2 As, 2 Bs, and so on. So, an ICPC contestant will need a relatively different level of stamina than the one needed in Codeforces rounds. It seems that people who practice only over Codeforces rounds, don’t usually enjoy the same level of comfort and confidence dealing with ICPC format.

There is a difference between the style of problems presented in Codeforces round, and the problems presented in ICPC world finals, and it seems that problems that fit the style of ICPC world finals are not accepted by Codeforces coordinators to be in codeforces rounds at least according to my own experience when I tried to propose a contest.

Problems presented in Codeforces rounds typically have the following characteristics:

  • Almost no knowledge required. It has to be 100% problem solving without the need to know any algorithm before coming to the contest.
  • Its code should be relatively short and quick to write. Something like 40-60 lines of code.

Although these characteristics might be getting a cleaner and better problem set (depending on what the words cleaner and better mean), however, this is not what the ICPC world finals look like.

The characteristics in the ICPC world finals are:

  • Long statements.
  • Too many corner cases.
  • You need to know and understand many algorithms and data structures and often the problems boil down to either tweaking a standard algorithm to the specifics of the problem or to understanding that the solution of the problem can be computed (or built) from the intermediate steps of a standard algorithm or an algorithm inspired by it.
  • Hard idea, not easy to find the solution anyways.
  • Long codes are normal and expected.
  • Modeling problems, where the objective is to transform the problem to (an often standard) model, where the hard step is the modelling step not the final algorithm.

So the questions to the CF community (and also ICPC community, judges and problem setters if possible) are:

  1. Is there a real difference in style between ICPC world finals and Codeforce rounds or is it superficial differences?
  2. Why does this difference exist?
  3. Are Codeforces ratings a good proxy for the ICPC world finals standings?
  4. Can people who want to succeed at ICPC world finals and its qualifiers depend on Codeforces as a main source of practice?

Full text and comments »

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

By Noureldin, history, 3 years ago, In English

I solved spoj's RESIST today, which incidently is also available on timus, to me it seemed like an excersize in solving linear equations, Kirchhof's current law yields a system of $$$(N-2) \times (N-2)$$$ equations which I solved using Gaussian elemination, that was enough to get AC on timus however it gave WA on spoj, I kept trying to find a bug in my code but I couldn't find any and I almost gave up on it when I decided to google for an algorithm or something that calculates the resistance and indeed I found cp-algorithms page on Kirchhof's matrix theoreom which got AC on both judges, naturally the next step was to stress test the two solutions to try to find a case where the first solution breaks, as of the time of writing the my stress test code has tried 26000+ random cases of different sizes and still nothing, which means that the case that breaks my first code on spoj has to have interesting properties, what do you think?

Full text and comments »

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

By Noureldin, history, 3 years ago, In English

things to do in quarantine

  • train to be better at CP
  • get some work done
  • generate some CF statistics

vanishing rating points

so I ran a python script that collected all rating changes of every rated round and I found some interesting stuff which can be found at the end of blog, however the thing that caught my attention is that rating points are vanishing at a rate of ~5.483 points/round/contestant!!!

the average rating change is negative ~ -5.483 points/contestant/round which is weired, you would expect that number to be around zero since the rating system scales everything so that the sum of ratings of contestants after each round remains the same as it was before the round, maybe a side effect of rounding ?

to verify this I compared the sum of rating of all rated accounts against what it should be, there are 258434 accounts that competed in at least one rated round, the sum of current rating of those accounts is 364795845 which is 22855155 (5.895%) less than what it should be 1500*(number of accounts) = 387651000

so why no one notices and ratings generally increase, it's -I think- because of the large influx of new accounts, each new account adds 1500 points to the pool of points once it starts participating in rated rounds so no one will notice ~5.483 points lost per contestant per round

if you think of the points as money and rating changes as transactions then you most likely won't notice that 5$ vanishes with each transaction from your account if each transaction involve $1000s, so basically we are acquiring points/money a lot faster than we are losing them and we won't start to feel the loss until the number of active accounts saturates, unless I'm missing something?!

so in a hypothetical scenario in which no new accounts are created and we just keep competing against each other and assuming all accounts are active we will all have ~ zero rating after ~257.44 rounds :V (or 6653.22 rounds if the number of contestants in each round is the -currently- more typical number of contestants of 10K)

how long you will need to reach high rating

you -probably- need -if ever- around 2.36 the time you needed to become a master to become LGM

the average number of rounds that contestants needed to hit a rank for the first time is summarized in this table

rank average number of rounds to become
Master 27.163
International Master 34.818
Grandmaster 39.651
International Grandmaster 47.638
Legandary Grandmaster 64.038
rank/percentile 0th25th50th75th100th
Master2.0 8.0 18.0 38.0 250.0
International Master3.0 12.0 25.0 48.0 213.0
Grandmaster3.0 15.0 30.0 55.0 274.0
International Grandmaster5.0 21.0 39.0 66.25 198.0
Legendary Grandmaster8.0 31.25 54.0 88.75 221.0
I wanted to list the accounts that reached each rank in minimum number of rounds however I found that most of them are fake accounts :\ :(

Full text and comments »

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

By Noureldin, history, 4 years ago, In English

UPDATE: it's back ^_^

so it came to my attention a few days ago by fegla that icpcarchive only gives WA or CE verdicts (judging status) to make sure I submitted a couple of my already AC codes and they gave WA ... so it seems that it's not functioning properly.

I don't know if it's down for good or temporarily but livearchive (though admittedly not the nicest of OJs, I mean who didn't get frustrated because of WA due to \n or a space or a weird I/O format or corrupted testing data) was a great repository of regional CPC and ICPC contests (with contests dating from 1988 from all over the world) and it's really sad to lose it.

so is there anything that can or is being done to save it -and while at it improve it- ?

Full text and comments »

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

By Noureldin, history, 4 years ago, In English

since ACPC is drawing nearer and most regional contests are over, I'm starting a list of teams attending ACPC.

please comment with the name of your team name, university, country and team members' accounts or of teams you know.

UPDATE: the ACPC will be held between Nov, 29th and Dec 3rd in Sharm Elsheikh, Egypt.

Country University Team Name Member 1 Member 2 Member 3 team rating
Jordan PSUT Aurora Motarack Hiasat Dark 2561
Egypt unofficial high school team Room 116 mohammedehab2002 Osama_Alkhodairy zoooma13 2388
Egypt AAST (unofficial) Too late :( Yousef_Salama Omar_Elawady tamp_ 2345
Egypt FCIS Ain Shams 3 x 1 Abdelrhman_Akram islammohsen BohotySenpai 2314
Egypt FCIS Ain Shams Compilation Error missing 'slifer' compiler_101 Error_404 Slifoor 2307
Egypt AAST EnthusiasmOverflow mahmoudbadawy Noureldin BitHashTech 2299
Syria Damascus University Assert Baraa_Armoush Mouaz_Alkhodari EsmaelSY 2290
Tunisia INSAT NP-BOSTAJI lionadis letmeC svanO 2254
Syria Damascus University How you doin?;) Mohammad_Kartoumeh Turing.Machine khaled97ha 2224
Egypt Faculty of Engineering Alexandria university IGN Mohammed_Badawi Ahmed_AIansary Evro 2199
Egypt FCI Cairo University Be Done OsamaFathy alimagde omar22 2188
Jordan unofficial high school team JOI3310 Wesam OmarNaseer Adhami 2165
Egypt GUC Gotta ACe'm all ZeyadKhattab mennafadali Nesrin 2131
Syria Syrian Virtual University (SVU) Traitors Adel_SaadEddin Salim_Shebli Zaher 2070
Syria Tishreen University Too lazy to propagate NourAlhadi NeuTronic C137 2047
Lebanon American University of Beirut Segment Team ChaosAngel Charbel 0-jij-0 2036
Syria Al-Baath university Peaky Blinders Mll Akheer SyrianTony _Mugiwara_ Al-Merreikh 2025
Lebanon American University Of Beirut BlackLotus abcdefghijklmnop1234 HadyKo Hadi_A 2023
Egypt Assiut University Ya 5rabyy Muhammad_Mustafa _AhmedHafez Abdelrahman_Elhawary 2015
Egypt Shoubra FE-BU BugLife IsmailToukhy Elwazer _Samir 2006
Egypt Faculty of engineering Cairo university WF ISA Half-Blood_Prince AbdallahHemdan Hassanosama 2005
Egypt unofficial high school team glad to take your input Bakry Mohamed.Sobhy PATH242 2001
Egypt GUC Educated Noodles YahiaSherif Hemose O_E 1995
Egypt Assiut University Ala7lam_team Muhammed_Atef_Hassan AhmedEzzatG karemo 1986
Egypt FCIS Ain Shams While(++Procrastinators) Khaled-Mohamed _HossamYehia_ Essawi 1983
Syria Al-Baath university Can we defeat SyrianTony? thecarrot Mourad_16 Naseem17 1980
Egypt FCI Cairo University Stack Overshab7na abdallah_naguib Dardy Mona_Ahmed 1958
Syria Tishreen University Acceptophillia aboAdnan EleCursity SubSpring 1951
Syria Damascus University ICPCNextCentury SaeedSabbagh abdalkader-s Bsher 1931
Tunisia Tekup university IDERSHIP BigDaddyPanda A.m-E.r Amine 1877
Egypt Faculty of Engineering Alexandria university Finding Dory AbdulRahman_Nour kindCactus LouaiZahran 1837
Egypt Tanta University -3iq Mr__Red fawzy20 _zaher_ 1812
Tunisia Tunisia Polytechnic School GG&GG/Yes __vayper Haykoul Rm6 1811
Egypt AUC full_slack dolaStream theRadFad Oschart 1785
Syria Aleppo University Penguins Mohamad_AboDan AbdulQader_Q Ali_ZaiBug 1782
Egypt FCI Kafrelsheikh University No pain no balloon YahiaAglan74 It_Wasnt_Me Eltoney 1780
Palestine Palestine Polytechnic University 7Up ItsMeMario Logic_PS Mr-Spy 1779
Egypt Suez Canal University Mal2yna4 esm ll team m4 7war y3nee KerollosNabil KhaledRezk Kerolloz 1765
Egypt Faculty of engineering Cairo university MEKASO Muhammad98 kareem98 The-Last-Avenger 1744
Egypt Faculty of Science — Cairo university Faree2.L.Batt AbdullahAlabd ONE.EYED.OWL moaz310 1735
Egypt Minia University java++ Abdelrahman_Mohammed Abdul_the_brave X-O__O-X 1683
Oman Sultan Qaboos University Null sal2 n3sser massar 1678
Oman Sultan Qaboos University Syntax Error Ahmed_Allawati mashal1996 khalfan 1674
Syria Al-Baath university Dark mode Mohammad.Nour yaser01 omar94 1670
Palestine Birzeit University Limitless laithmubarak11 Masalmah SHQAIR 1651
Egypt unofficial middle school team BLE ahmedfouadnew Yasseenkamel yahia 1602
Jordan Al- Balqa' Applied University (BAU) Teeny Tiny Posibillity Batool_AbuRumman M-Levi Abukhadijah 1598
Egypt Nile university Brows Menna-Allah05 Hossam._.Ali Khaled.Emad 1562
Egypt Helwan University ayasm G0o0LD L-Lawliet HASHINSHIN_101 1480

Full text and comments »

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

By Noureldin, history, 5 years ago, In English

Hello CodeForces! I'd like to invite you to the online mirror of the 2017 ACM egyptian collegiate programming contest ,which will be held on Wednessday, 6 July 2018, 02:00pm Cairo time

contest link: ACM ECPC 2017

standings: link

ACM ECPC 2017 Highlights:

the problems were prepared and tested by : Thrax -chief judge-,Badry, Noureldin, Jarrar, Safrout, Lvitsa, amrSamir, Amirnasr, islam-al-aarag, justHusam and RedStone

problems authors:

Assessment — islam-al-aarag

Breaking the curse — Badry

Cheering parabolas — Thrax

Dream Team — Lvitsa and Thrax

Evaluations — Noureldin

Forgot the Flag! — Noureldin

Glorious Stadium — Jarrar

Half Nice Years — Lvitsa and Thrax

Important matches — justHusam

Jacking ticket — Thrax

Katryoshka — Lvitsa

Lazy ERCD — Mohamed Fouad `

You will be given 5 hours to solve the problems.

Good Luck and have fun!

UPDATE as some of you found out the test sets weren't complete and only samples were ported to the gym version ... that's due to a mistake I made while porting the contest

what happened?

I tried importing the contest normally by coping the contest.xml to the ftp server but it generated alot of errors which I couldn't understand at the time so I imported the problems manually but forgot to run the and as a result none of the big test files were generated

now the contest is part of 'codeforces history' so I can't modify it, so I created another one with the original tests used in the contest so have fun with ECPC17

Full text and comments »

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

By Noureldin, 9 years ago, In English

for a competitive programmer the most important features are what C++11 has already introduced namely (range based loops ,lambda expressions ,brace initialization of aggregates, unordered containers ,..... etc) which can be found here .

in addition to:

1) numeric literals

now you can separate digits of a number with single quotes ( ' ) to improve readability

auto num = 10'000'000; // num = 10^7

this works for floating numbers as well

auto fnum = 0.000'015'3; // fnum = 1.53 * 10^-5

now you can initialize numbers using their binary form this feature was experimentally included in C++0x (the prototype of C++11) however it didn't become official until the announcement of the new standard

auto bnum = 0b0100'1100'0110; // bnum = (010011000110)2 = (4C6)16 = 1222

//note that the spacing of the quotes doesn't matter

auto snum = 1'0'0'000'00; // snum = 10^7

2) std::gets was removed due to its tendency to cause RTE due to overflow in its buffer

3) lambda expressions can now be generic:

in C++11 you had to specify the type of the inputs to the lambda expression

auto lambda = [](int x, int y) {return x + y;}; // C++11 --- had to specify type of x and y
auto lambda = [](auto x, auto y) {return x + y;}; // C++14 the compiler will decide the type for you ;)

4) improved std::tuple (in particular improved std::get)

in std::tuple introduced by C++11 (which was experimentally added to TR1 in 2007) to get the value of an element you had to use only its index

int element = std::get<2>(mytuple); //get the third element in mytuple

now you can do the same thing plus the ability to index by type

std::string element = std::get<string>(mytuple);// return the string element in mytuple

note: if the tuple had more than one element of the same type using std::get that way would cause compilation error

a feature of C++11 that's not mentioned in the link above that I find very useful

C++11 introduced the ability to pass rvalues by reference that's to pass temporary values by reference such as

// compilation error in C++03 .... legit in C++11 & C++14
string mul(string && a,string && b); 

as you can see from the specific example I used ,it speeds up calculuations in particular this snippet is from my biginteger implementation which sped up biginteger multiplication by 30-40% on average (tested on numbers containing ~ 50000 digits)

note: some legit C++03 && C++11 codes might break if compiled using C++14 standards

codes that use std::gets are the simplest case but there are others for more details you can refer to this link

finally ,there are some other additions and modifications in C++14 that are very important (relaxed constexpr restrictions ,improved lambda capture expressions ,the attribute [[deprecated]] ,heterogeneous lookup ,....etc) to name a few, yet their importance to a competitive programmer is less than that of the mentioned features (at least from my point of view)

Full text and comments »

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