ismailfateen's blog

By ismailfateen, 4 months ago, In English

Hello Codeforces,

Earlier this month, the ACPC (African and Arab Collegiate Programming Championship) concluded, determining the teams qualified for the ICPC World Finals from our region.

I decided to write a blog post to gather the full team list somewhere (yes, I know this is very early and most championships are still in March, but I'm so excited anyway, and I already had the script for the ACPC list, so why not!)

To add your team to the list, please comment these details:

  • Your region
  • Your country
  • Your university
  • Your team name
  • Team members' handles

Wish everyone the best of luck in preparing for the ICPC, and can't wait to meet you all!

Northern Eurasia

Country University Team Name Member 1 Member 2 Member 3 Team Rating
Russia HSE University FFTilted teraqqq Kirill22 Ormlis 3646.28
Russia ITMO University HFTilted 300iq Kirkon andreyDagger 3319.83
Russia Nizhny Novgorod Branch of HSE University Muffix Sassif sevlll777 crazyilian tem_shett 2865.87
Russia MIPT MrZver danya111 polosatic grishared 2633.53
Russia SPb SU I See Personal Computer Taechka mofeyTEA machine_solution 2477.8
Georgia Free University of Tbilisi Tbilisi FreeUni 1 Peasant OldBrilliantMate JunkieDonkey 2454.28
Russia National Research Nuclear University MEPhl Sneaky Random In The Pocket Andrew-13 heesooyaam M1chael_Petrov 2438.84
Kazakhstan Nazarbayev University clearly straight guys seduneon kenzhik fractal 2388.26

Asia East

Country University Team Name Member 1 Member 2 Member 3 Team Rating

Asia West

Country University Team Name Member 1 Member 2 Member 3 Team Rating
India IIT Kharagpur Div4Maxxers Dominater069 Aryan-Raina _ar07 3167.46
Iran Sharif University of Technology lp1 on fire ymmparsa alireza_kaviani amirhoseinfar1385 3114.96
India IIT BHU not qualified kingmessi BiggestOtaku a.out 2502.18
India IIT Delhi TOURISTS Arnav_Singhal1 lucky__389 Soumil69 2479.95
India IIT Roorkee hehe i do cp shorya1835 D1orite AKSLEGION 2426.88
Bangladesh University of Engineering and Technology BUET_Silver_hawks AIF_is_carving Shafin_Ahmed Falcon_76 2276.65
Pakistan FAST NUCES Khi ChaiWalay Musaddiq Ashar-Usmani minhaj03 2093.28

Africa and Arabia

Country University Team Name Member 1 Member 2 Member 3 Team Rating
Egypt Arab Academy for Science, Technology and Maritime Transport IFANYE AbdelmagedNour ismailfateen yahia 2724.3
Syria Syrian Virtual University Watermelon Juice Slayer FetFot Wael_Zaiback Mohanad_Nahhal 2534.66
Syria Aleppo University Guess The Imposter ApraCadabra MOUFLESS ALAov 2528.5
Syria Homs University Moz on Tree A.D. BabaVoss THE_THUNDERSTORM_BEGINS 2400.85
Syria Damascus University Shhh, You're In The Presence of Le Fishe! EyadBT Hosen_ba JaberSH1 2387.08
Palestine Birzeit University Free Palestine Wawi HIJAZ Satoru 2369.27
Egypt Alex-FE Hexa-Sha3-Sword Yahia_Emara morasha3 taha06 2344.71
Egypt Sohag University Accepted eeeh b2olak 3ayzen E3faa Ahmed_Ashraf_f Georgegg AnasMaged 2329.57
Egypt Mansoura-FE El-Coach Tooor ICPC por favor Kareem_Elgoker _Sherbiny Hamed_ 2319.93
Egypt CU-FCAI Adham 7akim w Momen 7alawany Mina7akim momen159 Mysterious109 2312.74
Egypt Menofia University L3nt-ElManifa Sersawy Khalwsh -Ahmed_-_Elsayed- 2206.5
Egypt SVU Qena Hbdnaha W El Judge 3daha AL70SSAIN AhmedElseyoufi Omar__Fawzy 2145.43

North America

Country University Team Name Member 1 Member 2 Member 3 Team Rating
United States of America Massachusetts Institute of Technology Monkey Is Typing OddImage zhoukangyang JohnVictor 3880.1
United States of America University of Maryland UMD Red Tlatoani kondasujay2 Owstin 3046.74
United States of America Arizona State University Second Wind BenjaminJ tgossett sahajrastogi 2833.64
United States of America University of Illinois Urbana–Champaign Ciallo ~(∠・ω< )⌒★!!!! lqs2015 char LetianPie 2807.97
Canada University of Waterloo UWaterloo Black kevinyang McPqndq SirTechnical 2787.39
United States of America University of Chicago pocpocpoc fextivity VHPro Francesco4203 2721.99
United States of America Georgia Institute of Technology GT 299 kevin zacharychao czjxyz 2683.38
United States of America Michigan State University MSU Spartans minhcool Voir duchung 2620.94
United States of America University of Central Florida UCF Triangulate SeptaCube Alg01 brianush1 2604.68
United States of America Stanford University Stanford Aquila lethan3 bitset spycoderyt 2585.64
United States of America Texas A&M University implementation school minhnguyenxuan60 jlass_ Andwerp 2544.77
Canada University of Toronto UofT Blue Wobert lookcook bill_lin 2519.51
Canada University of British Columbia Diamond Dust Ryazimn cran SnowLucario_Z 2463.62
Canada University of Alberta Alberta Azure asiad DigitalVest jxu 2461.89
United States of America University of California, Santa Barbara UCSB WA ezraft diss_quack lce4113 2424.02
United States of America University of Washington Jiakrico spike1236 Rico64 jia 2355.23
United States of America University of Minnesota Mad-is-sun WipeyTabletku lahlah dajeff 2319.19
United States of America Carnegie Mellon University CMU-Team 07 ? ? ? 0

Europe

Country University Team Name Member 1 Member 2 Member 3 Team Rating
Hungary Eötvös Loránd University Big as Hectic Dreaming peti1234 Peti ZsibbadtKubikus 3265.93
The Netherlands Delft University of Technology Segfault go BRRRR BLOBVISGOD Karuk jeroenodb 3238.54
United Kingdom University of Cambridge bruhopen p0tato snowysecret kevinxiehk 2915.08
Germany Karlsruhe Institute of Technology Infinite L∞pers burg113 FIorian gloria_mundi 2894.04
Turkey Middle East Technical University TBA tolbi yutabi destructive_criticism 2770.81
Austria University of Vienna Austrian Avalanche mightyrock n11k nitram 2525.03
United Kingdom Charles University MFF UK 1 JiriKalvoda Svizel_pritula SK1PY 2478.5

Asia Pacific

Country University Team Name Member 1 Member 2 Member 3 Team Rating
Japan The University of Osaka The Revenge of shinchan KowerKoint krit3379 Nachia 3564.26
Taiwan National Taiwan University std_abs BurnedChicken syl123456 abc864197532 3453.22
Singapore National University of Singapore Strong Zero yuto1115 tqbfjotld errorgorn 3272.06
South Korea Seoul National University Just use CRT platter kizen leinad2 3131.62
Japan Keio University Rinshan Solution honamikoto PCTprobability harurun4635 3070.6
Japan Institute of Science Tokyo AMATSUKAZE shobonvip noya2 Rice_tawara459 2877.14
Thailand Chulalongkorn University Here for the Free Snacks ttamx markthitrin thawin.ice 2831.62
South Korea KAIST Fox is cute SongC azberjibiou Serin 2824.43
South Korea Yonsei University Endgame Serendipity__ plast JYJin 2804.7
Japan The University of Tokyo SSQS YoshikaMiyafuji sounansya QCFium 2730.87
Vietnam University of Engineering and Technology — VNU infinity trungnotchung bachbeo2007 HollwoQ_Pelw 2716.73
Taiwan National Yang Ming Chiao Tung University NYCU_CartesianTreeII Aestivate Misuki ScottChou 2590.63
Vietnam University of Science, VNU-HCM HCMUS-ThaiFamily ConNuoiAnhThai ConRuotAnhThai ConRiengAnhThai 2530.05
South Korea Pusan National University Just Reboot JungSangHwa Parkkkkkcw qvixnh22 kolorVXL 2525.8
South Korea Hanyang University NJG ogura_yui jsj0412 Kleder 2435.24
Vietnam National Economics University NEU.Anarchaos thangdz2k7 uchihahahaha __pooh__ 2427.82
Australia UNSW Sydney ); DROP TABLE Teams;-- CactusProgrammer caterpillow horiseun 2421.12
Japan University of Aizu bonsai zawatin nono00 Taiki0715 2390.96
Japan Kyoto University bogosort tatesoto jastaway ? 2147.72
Australia University of Melbourne Uniformly Random Name ? ? ? 0

Latin America

Country University Team Name Member 1 Member 2 Member 3 Team Rating
Brazil UNICAMP Naim continua dentro de nós defnotmee LoboLobo enzopsm 2681.3
Argentina UNC Helicóptero Edu175 Jeresalen 46657526buscaR 2479.94
Brazil UFMG ooga booga mathiasgw perchuts gustavocruz 2443.66
Mexico UP Bonaterra Igloo Zone LoganGD Murinho El_Roge 2432.6
Brazil UFCG 8e6d0497880e3db3b3b093f517c13f9f jackson.souza Pedrinho_Eu holanda2103 2378.35
Brazil UDESC é sempre o XOR emoreira nzo joaozao 2264.48
Argentina UNR Red-Black Tree Maezra6 Franchu Username4132 2251.02
Brazil UnB É só fazer arthur_9548 MagePetrus duduFreire 2249.76
Mexico ESCOM IPN hmmmmmmmmm? Jose_17 Remgagagali727 Leonardo_Toral 2237.28
Chile UChile sin globito no hay fiesta m1tu dariasc MartinRT 2218.54
Peru UNI FIIS SaleEnOdeUno Teranj NekoRolly RReyes2612 2210.8
Cuba UH UH Pop EduardoBrito Ernest0_0Abreu John314 2162.62
Mexico UPGDL Testigos de Germán efishel imlearningc roostercross 2149.0
Argentina UNLP NaN (Need a Name) Joacoini PekitaZ joaco-gavernet 2145.63
Colombia EAFIT Que bendición automac juancs elpepe123 2085.53
Brazil UFPE las4s e pelados joaovictor20 pgoq icaro_nunes 2033.68
Argentina UBA Los Catastróficos NicoRicci empaktus BrunZo 1886.91
Costa Rica ITCR-Alajuela No name yet Kener_Castillo aleC_aleC hacaravaca 1859.06

Full text and comments »

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

By ismailfateen, 9 months ago, In English

Hello codeforces!

ECPC (Egyptian Collegiate Programming Contest) 2025 has just concluded so I decided to post a blog with the teams qualified to ACPC (Africa and Arab Collegiate Programming Contest) 2025. ACPC will be held in the beginning of December.

Huge congratulations to "Tamora fel d2e2a 90" from Cairo University — Faculty of Computers and Artificial Intelligence for winning ECPC 2025!!

If your team qualified, kindly put your Country, University (and College if applicable), teamname and your teammates' cf profiles and I will add it to the list.

Best of luck in ACPC!

University Teams (Details):

Country University Team Name Member 1 Member 2 Member 3
Syria Aleppo University Guess The Imposter ApraCadabra MOUFLESS ALAov
Syria Damascus University Black Hawks ali2005_syr Mohammad_Hacker Go8
Egypt AASTMT-Cairo IFANYE AbdelmagedNour ismailfateen yahia
Jordan Applied Science Private University G(old) Naseer Rayo RedMind
Syria Damascus University Mada5alak skahl15 Khaled_Al_Awad GMgrizo
Syria Homs University Moz on Tree IGM_NEXT_YEAR BabaVoss THE_THUNDERSTORM_BEGINS
Palestine Birzeit University Free Palestine Wawi_ HIJAZ Satoru
Egypt CU-FCAI Tamora fel d2e2a 90 B_3 Tamora ahmedalaa22
Egypt Assiut University 3al Hady AbdoSa3d KareemHatem Mohamed_Reda
Egypt Portsaid University FFT this HLD that — Can't a man just Binary search in peace Karim_Abdelaziz zyadhany McLAD
Egypt Alex-FE Hexa-Sha3-Sword Yahia_Emara morasha3 sword060
Morocco Mohammadia School of Engineers Emordnilap medmdg_3 safaebouziani27 salmamahdioui8
Egypt Mansoura-FE El-Coach Tooor ICPC por favor Kareem_Elgoker _Sherbiny Hamed_
Syria Aleppo University We don't need a carry just need to marry! Mr.Perfume MaherSefo NARUTO_UZUMAKI.
Egypt Fayoum University 3 Ktakeet w Tmra Moatazoleq M0N 7oka_
Syria Homs University Mafeesh akhbar 3n el verdict ?? ammar2000 FarhanHY Magician_Mathematician1
Syria Syrian Virtual University One last farewell Rising-coder Aysha_Bsata ZaiBug
Egypt CU-FCAI Adham 7akim w Momen 7alawany Mina7akim momen159 Mysterious109
Syria Al-Wataniya Private University Chill Guys Derarinho YazanAlattar Obada-_-
Lebanon American University of Beirut, Faculty of Arts and Science sa7sou7 Koosa marcas aswadk
Egypt Menofia University L3nt-Menofia Sersawy Khalwsh -Ahmed_-_Elsayed-
Egypt Al Azhar Just for Keef Eslam_Saleh EslamSamy2002 Mohamed_M.M.R
Jordan Princess Sumaya University of Technology AAA samsoom Barakat. Hanagasumii
Morocco 1337 Coding School Alfari9 Alkhari9 ceciver 3.14IQ osmann
Egypt The American University in Cairo (AUC) Bukayo Haka MEDAA pharaok A_Greedy_Gunner
Egypt SVU Qena Hbdnaha W El Judge 3daha AL70SSAIN AhmedElseyoufi Omar__Fawzy
Egypt Egyptian e-Learning University Enzel ya metdala3 El_Farag CGemmy AliRagab313
Tunisia Higher Institute of Computer Science Ariana Diga Diga Firas_Briki assazzin_2 Kairm_Zaf
Egypt Alex-FCDS Soo2 taghzeya Plato Fadyy_yosryy77 Richard-Dyinman
Egypt El Shorouk Academy El Gharbia Lmokafa7t Eldokhan Mn6fy Mostafa__Fouad -Satrix-
Egypt Benha-FCAI Cerberus Mr_Turtle_ Omar_Farhan 3alam
Egypt Benha-FE-Shoubra Hato chatgpt msh 3arf a7l Striker009 Hagag Bahy.
Tunisia INSAT Kabbout rayenbbs MehdiBenAli boukamcha77
Palestine Birzeit University Kabsa PalestinianTornado resolve100 -Nebula
Egypt Mansoura-FE Max Flooooos Shoeib MiraculousN KhaledElhady
Egypt Benha-FCAI ElBo3Bo3 El-Thaer M.Thaer MWarith Mohamed_Waheed
Tunisia INSAT University Jawek A7la Jaw Iceberg GH1hatem Moyogi
Tunisia INSAT Sigma Boiz Hups get_ducked ademby
Egypt AASTMT-Cairo Food Courses c0de-Wizard DibsingtheDs Mr.Pie
Egypt ASU-FCIS Getlak Ya 3bd El Mo3een 34an T3eny La2etak 3ayz Tt3an die-kstra QRQ4 JustOK
Tunisia École nationale des sciences de l'informatique (ENSI) 7assibet Manouba Greeedy monocrap Xecutioner
Egypt Menofia University rejected-name-05 Homz Tamatem.1 El7abal
Jordan Applied Science Private University ikindagotalittleangry D7br omarkurde Ice-Cooled-Spoderman
Morocco 1337 Coding School LKHOBZ O L3TACH Duukh yrhiba Mr_Flash
United Arab Emirates MBZUAI placeholder Yelarys acm macharstein
Egypt Luxor University dp ya maklaboOok Hitham Khalell AhmedYahia
Egypt University of Sadat City 3awzeen ICPC w ta2m 3arayes yse Borhom Sonic444
Egypt ASU-FE Hawe el code 3shan el bugs 3mara Moaz_Ragab1 MohammadAbduljalil
Egypt Tanta University Ana gaylak w naweeha Selim guess_who SeeElsayed
Egypt Suez Canal University Just RAM -RAGNAR- Mhmud_Sameh24 Ahmed_Faraj
Egypt Benha-FE-Shoubra Awlad El 7ag 3atya 0xEssam Tesla. Mo_Elaksher
Syria Aleppo University Binary_Trio Jean7 Mauricio_7 Edward_Haddad
Tunisia Higher Institute of Computer Science Ariana (ISI) I See Pc Draw_My_Solution the_mmed ammahmed004
Egypt Mansoura University — Faculty of Computer and Information Kolna 3awzen Netgawez AdhamElsaady AhmedReda11 bettercallwael
Tunisia Higher School of Communication of Tunis Coffee Limit Exceeded Picassooo Meow.Meow. TMSniper
Egypt ASU-FE Hwa Feh Haga Esmha ICPC Beboo_Osama MariamH Sh314
Jordan HTU Mr.jo7a the_seal LazLooz Sadasak
Egypt Helwan University Still We are not the same _SHAHIN _MANS0UR_ 3B3ATY
Egypt Damietta University C for Champions MinValgen OmarMoBadr Beroo
Egypt Zagazig University Mn3rf4 leh AC ShaFeiii omarkhaled1812 Zeyad_Zahran
Egypt SVU Qena Esm7oly a2olko ana 2lby shayl mnkwo Dr.rabi3 Glitch00 _mohamed_abdo
Tunisia ISAMM less than OR EQUAL TO Akrem_Ben_Zaoui Abdel_koddous Kefrov
Syria Aleppo University Rfa3 wrong the samples are strong KAKAROT-M Ra7_aljaml_bima_7aml Rasoul
Tunisia ISIMM Xorazm RaedAroua azizkhlify la_chambre
Egypt Zagazig University E3fa w etnen 3sakr ZyadFva Sha3rawy Mohamed-Said
Egypt Helwan University Yalaaahwy Ctrl Z bsor3a Uchiha_Ouda Zeyad_3BcarenO gom3a_
Jordan Princess Sumaya University of Technology Should we just trust a NEW MAN Shaaker ayoooy Ghaith_zakaria
Jordan The University of Jordan Axiom Ghost.. LaithNaimi MalekAlsaudi
Egypt Alex-FCDS Accepted bgd y abo nwaf Sa3dny Ali_Mohamed AbduAlrimali
Jordan Applied Science Private University We participated to take the copper wires after the contest Shrek. Droby jaber_
Jordan Princess Sumaya University for Technology NotDecidedYet hammoudehib Tardi yousefAbukhass
Jordan Al-Balqa' Applied University Giga Survival 0.2 Hiba_Hirzallah 4lujain HamzahZuhair
Oman Sultan Qaboos University Libre Osama_ Qa_2me alhinaimohammed19
Jordan Applied Science Private University Inner Peace Dinner Please An9on yaman.alrifai Bashar.Aref
Jordan Al-Hussein Technical University Moon's Ex --hmzabanna-- Amr.ysf Essoo
Jordan Princess Sumaya University for Technology We Bare Bears PolarGoat AmeenAlrawabdeh ali_sa3sa3
Oman Sultan Qaboos University Enigma ASD101 TheMatrix007 st133720
Oman German University of Technology Extreme Coderz jbinnafees878 Adharialabri MohdLawati

University Teams (Ratings):

Team Name Team Rating
Guess The Imposter 2528.5
Black Hawks 2506.96
IFANYE 2484.46
G(old) 2472.87
Mada5alak 2414.44
Moz on Tree 2389.49
Free Palestine 2369.27
Tamora fel d2e2a 90 2368.97
3al Hady 2362.72
FFT this HLD that — Can't a man just Binary search in peace 2354.76
Hexa-Sha3-Sword 2344.71
Emordnilap 2316.0
El-Coach Tooor ICPC por favor 2309.45
We don't need a carry just need to marry! 2287.25
3 Ktakeet w Tmra 2277.73
Mafeesh akhbar 3n el verdict ?? 2274.89
One last farewell 2263.53
Adham 7akim w Momen 7alawany 2262.81
Chill Guys 2216.72
sa7sou7 2213.0
L3nt-Menofia 2196.77
Just for Keef 2179.09
AAA 2174.35
Alfari9 Alkhari9 2166.7
Bukayo Haka 2165.76
Hbdnaha W El Judge 3daha 2145.43
Enzel ya metdala3 2134.87
Diga Diga 2131.48
Soo2 taghzeya 2129.27
El Gharbia Lmokafa7t Eldokhan 2099.89
Cerberus 2097.94
Hato chatgpt msh 3arf a7l 2073.65
Kabbout 2064.34
Kabsa 2056.64
Max Flooooos 2046.06
ElBo3Bo3 El-Thaer 2022.12
Jawek A7la Jaw 2019.1
Sigma Boiz 2018.6
Food Courses 2015.17
Getlak Ya 3bd El Mo3een 34an T3eny La2etak 3ayz Tt3an 2012.55
7assibet Manouba 2007.64
rejected-name-05 2003.78
ikindagotalittleangry 2001.72
LKHOBZ O L3TACH 1995.12
placeholder 1991.79
dp ya maklaboOok 1985.66
3awzeen ICPC w ta2m 3arayes 1980.93
Hawe el code 3shan el bugs 1974.23
Ana gaylak w naweeha 1962.64
Just RAM 1930.0
Awlad El 7ag 3atya 1926.89
Binary_Trio 1890.81
I See Pc 1888.26
Kolna 3awzen Netgawez 1883.6
Coffee Limit Exceeded 1874.12
Hwa Feh Haga Esmha ICPC 1862.76
Mr.jo7a 1858.54
Still We are not the same 1853.7
C for Champions 1846.74
Mn3rf4 leh AC 1846.4
Esm7oly a2olko ana 2lby shayl mnkwo 1829.97
less than OR EQUAL TO 1828.41
Rfa3 wrong the samples are strong 1801.65
Xorazm 1793.25
E3fa w etnen 3sakr 1779.65
Yalaaahwy Ctrl Z bsor3a 1775.33
Should we just trust a NEW MAN 1770.52
Axiom 1738.57
Accepted bgd y abo nwaf 1666.09
We participated to take the copper wires after the contest 1645.26
NotDecidedYet 1641.36
Giga Survival 0.2 1632.41
Libre 1594.04
Inner Peace Dinner Please 1545.4
Moon's Ex 1527.19
We Bare Bears 1402.94
Enigma 1335.32
Extreme Coderz 914.0

Teens teams:

Country Team Name Member 1 Member 2 Team Rating
Syria alshbalasle edogawa_something Abito 2388.36
Lebanon Saba7 al zanjabil HusseinFarhat Hadi_hh 2326.79
Egypt EOI — El team el matloob mo8lq aw 8yr mota7 Ahmed_Solyman is-this-dp 2192.94
Egypt EOI — MOoooo satalanaaaa Baraa-Ahmed O_Elmasry 2177.89
Egypt gurt: yo Adam.Aly SirPh 2031.78
Tunisia Full House AlaaAfif Friday_night 1722.09

Full text and comments »

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

By ismailfateen, 2 years ago, In English

Motivation

Dynamic CHT with sets is hard to write. I haven't learned LiChao Tree, but I will share this technique anyways, as it can be applied to other data structures.

AbdelmagedNour explained this to me $$$8$$$ months ago, and it introduced a new way of thinking to me. I could not find any references to something similar on the internet, so I decided I'll give it my best shot here.

If this already has a name, please comment it.

Prerequisites:

There are no prerequisities; however, the problem I have posted for checking implementation uses Convex Hull Trick. Please read this blog if you don't know about it.

The problem:

Assume we have a data structure which can add an element in $$$O(A)$$$ and query in $$$O(Q)$$$; however, elements have to be added in monotonic order of some valid comparison function. If we receive the elements in monotonic order, we have no problems! But what if we don't? My claim is that it is possible to add all $$$N$$$ elements in amortized $$$O(AN \log N)$$$, and query for our property in $$$O(Q \log N)$$$. Usually we want to query the maximum element/minimum element, or any property in which we can easily merge $$$2$$$ possible answers.

A classical example of this is the convex hull trick data structure. This data structure allows us to insert lines in the form $$$y = mx + c$$$, and query the minimum/maximum value of $$$y$$$ for a given $$$x$$$. It works in amortized $$$O(n)$$$ where $$$n$$$ is the number of lines added. However, this assumes that lines are sorted in monotonic order of their slopes. What if they aren't?

Initially we create an array $$$blk$$$ of size $$$\lceil{\log N}\rceil$$$. $$$blk[i]$$$ will store a version of our data structure of size $$$2^i$$$, initially, $$$blk[i]$$$ is empty for all $$$i$$$.

Now, to add the first element, we just add it to $$$blk[0]$$$; but for the second element, we clear $$$blk[0]$$$, use merge sort to sort $$$blk[0]$$$ and the second element, and insert them into $$$blk[1]$$$. The third element is inserted into $$$blk[0]$$$, the fourth is merged using merge sort with $$$blk[0],blk[1]$$$, and they are all inserted into $$$blk[2]$$$, (and $$$blk[0],blk[1]$$$ are emptied).

A simple code demonstrating it would look something like this:

DS merge(DS& a, DS& b) {
 // This function merges the 2 sorted data structures. This would depend on how the data structure works.
}
void insert(T element) {
  DS current;
  current.insert(element);
  int index = 0;
  while (blk[index].size > 0) {
   current = merge(current, blk[index]), blk[index].clear();
   index++;
  }
  blk[index] = current;
}

Why is the complexity amortized $$$O(AN \log N)$$$?

Notice that each element you add will go through at most $$$\log N$$$ places in the $$$blk$$$ array, and we add $$$N$$$ elements, each of which needs $$$O(A)$$$ to be inserted into the data structure, so it amortizes to $$$O(AN \log N)$$$.

Now, to query on this data structure, we choose the best possible answer throughout all non empty data structures in $$$blk$$$.

A simple code demonstrating it would like this:

T query(U input) {
  T ans = identity;
  for (auto& ds : blk) {
    if (ds.empty()) continue;
    ans = better(ans, ds.query(input)); // better returns whichever answer is better, or merges them, again, some things change depending on the data structure.
  }
}

The complexity of this is clearly $$$O(QX \log N)$$$, where $$$O(X)$$$ is the complexity of the better function.

As a practice for this technique, you can solve this problem.

Extra Problems

If you know any more problems which apply this technique (with any data structure), please comment and I'll add it to the list :)

P.S. This is my first educational blog, if there's any mistake or any improvements I can make, please criticize me in the comments :)

Full text and comments »

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

By ismailfateen, history, 3 years ago, In English

A lot of people are sitting for their IGCSEs/A levels in the upcoming month. Good luck to those who are! That doesn't mean you should quit competitive programming for this month, try to practice and solve 1 or 2 problems daily regardless :)

Full text and comments »

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

By ismailfateen, 3 years ago, In English

Hello, there seems to be a lot of CLion users on macOS who cannot seem to set CLion to use G++ instead of clang++

As we all know G++ is the preferred compiler for competitive programmers as it has a lot to offer (for example bits/stdc++.h, and the Policy Based Data Structures such as ordered_sets)

So, here's a guide to get G++ working on macOS! Firstly, you need to ensure homebrew is installed, you can install it from https://brew.sh After installing it, and adding it to your path, execute the command brew install gcc After executing this and refreshing your terminal. Make sure you now have access to the commands gcc-12 and g++-12 After ensuring they are available, open CLion settings, go to Build, Execution, Deployment -> Toolchains set the build tool to /usr/bin/make, C compiler to whatever the terminal says after executing whereis gcc-12, and C++ compiler to whatever the terminal says after executing whereis g++-12, for example, in my laptop it was these paths: /usr/bin/make , /opt/homebrew/bin/gcc-12 , /opt/homebrew/bin/g++-12

After refreshing CLion, you should be able to be a GCC enjoyer!

I hope that helps someone :D

Full text and comments »

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