Problem Topics Good Day to you! I've been asked to make some topic-wise list of problems I've solved. Even though I couldn't involve all problems, I've tried to involve at least "few" problems at each topic I thought up (I'm sorry if I forgot about something "easy"). I've alredy made such list once anyway I've tried to include more problems now &mdash; so here it is: <spoiler summary="aho"> http://www.spoj.com/problems/ADAJOBS/ URI 2226 (5) //[NICE][NUMBERS][DP] http://www.spoj.com/problems/SUB_PROB/en/ http://codeforces.me/contest/696/problem/D 8 http://www.spoj.com/problems/AHOCUR/ 5 //Aho-Corassic + DP https://www.codechef.com/problems/LYRC (5) //Sample aho-brute-force http://codeforces.me/problemset/problem/346/B //Proposed by [user:bradyawn,2019-08-03] </spoiler> <spoiler summary="automat"> 6861 [LA] //CYK UVA 10679 //Suffix Automat http://www.spoj.com/problems/STRMATCH/ //Suffix Automat &mdash; trie might do too http://www.spoj.com/problems/NSUBST...

Full text and comments »

IICPC Global Codefest 2026 Hello! Registrations for IICPC Global Codefest 2026 are opening soon. This is the first global edition of India's largest offline competitive programming competition. **About IICPC Codefest** IICPC (Intercollegiate Informatic and Competitive Programming Camp) is an academic and industry-backed organization focused on identifying, evaluating, and nurturing high-potential students in competitive programming, algorithms, and computer science fundamentals through rigorously designed, large-scale competitive examinations and camps. We organize Codefest, a multi-stage competitive programming competition conducted across India. This year, we are opening participation to international students from 50+ countries. **The prelims is individual participation, and online for international students. The deadline for registration is 15th January, 23:59 IST**. <img src="https://i.ibb.co/bRJt7y44/codefest-banner.png" height="50"> **Competition Structure** Prelims &mdash; Janua...

Full text and comments »

[Invitation] IICPC CodeFest 2025 ### Greetings, Codeforces Community! We are thrilled to invite you to **CodeFest**, a premier competitive programming event brought to you by [IICPC](https://iicpc.com/), co-sponsored by [Citadel](https://www.citadelsecurities.com/) and [Jump Trading](https://www.jumptrading.com/), Associate sponsors as [Jane Street](https://www.janestreet.com/), [Hudson River Trading (HRT)](https://www.hudsonrivertrading.com/), [Landeed](https://www.landeed.com/) and [QuantInsti](https://www.quantinsti.com/) being the Knowledge Partner.  The camp is being hosted by the 8 IITs namely Madras, Delhi, Bombay, Guwahati, Hyderabad, Kharagpur, Roorkee and Indore and we are grateful for the same! You can check our event announcement video [here](https://www.youtube.com/live/cKTUU0PEBYA?si=eEwZ0iiLaeiYkdM4). --- ### **Inspiration** In late 2024, Ayush and I were wondering what could be done next to improve the Competit...

Full text and comments »

[Tutorial] Euler's phi function, its properties, and how to compute it Hello codeforces! In one of the recent contests there appeared [a problem](https://codeforces.me/problemset/problem/1717/E) which involved Euler's phi function, and I figured I could write a bit about this function here. First, I will briefly introduce Euler's phi function, talk about two of its properties, and give you proofs of both of them. Ultimately, it will lead us to a way to compute the value of this function for some given integer $n$ with reasonable time complexity. [cut] <br> I tried to keep this post quite basic, so that it's accessible to everyone. Therefore, if you are already quite good at some topic mentioned here, feel free to skip a section or two. Also, I would like to say thank you to my friend, [user:sysia,2022-09-11], who helped me a lot with writing this post and suppressed my tendency to write too much. <br> ### What is Euler's phi function? Euler's phi function (which may be also called Euler's totient function) is a function that g...

Full text and comments »

IICPC Global Quantfest 2026 Hello! Registrations for **IICPC Global Quantfest 2026** are now open. This is 2nd Global IICPC Examination, bringing together Quantitative Finance, Probability, and Competitive Programming, built on IICPC's rich legacy of nurturing top talent. **About IICPC Quantfest** IICPC (Intercollegiate Informatic and Competitive Programming Camp) is a student-led initiative dedicated to advancing competitive programming and quantitative problem solving for the globe. Over the past few years, IICPC has organized bootcamps, contests , recruitment examinations, and educational programs connecting thousands of students with industry and academia. Quantfest is a global quantitative problem-solving festival where the brightest analytical minds tackle challenges inspired by real-world trading and quantitative roles. This year, we are opening participation to international students from 50+ countries. **Registrations go live on July 20, and remain open till August 20.** There is no partic...

Full text and comments »

Online Competitive Programming Summer Camp, by Programming Club IITM Hello, Codeforces!  **Note:** The camp is designed to be **extremely beginner friendly** (for someone who has just started coding), and the contents will not be suitable/informative for Expert or higher-rated participants. I am glad to announce the [Competitive Coding Conclave](https://cfi.iitm.ac.in/summer-school/session/Competitive-Coding-Conclave) hosted by [Programming Club, IIT Madras](https://cfi.iitm.ac.in/clubs/programming-club) that is scheduled to happen online from **6 to 25 July 2023**. The camp will comprise 9 sessions (every Tuesday, Thursday, and Saturday) and 3 contests. The camp is **free of cost**. The sessions will be conducted on Microsoft Teams, and the problem sets, and contests will be conducted in [this Codeforces group](https://codeforces.me/group/7mxf4oQFY7). The expected starting time of the sessions is **5 PM IST**, and the contests will be held on weekends. The camp will ...

Full text and comments »

[Invitation] IICPC QuantFest 2025 We are thrilled to invite you to QuantFest, a premier quant finance event brought to you by [IICPC](https://iicpc.com/), sponsored by Jane Street, Tower Research Capital, Hudson River Trading and IMC!  All students from host campuses are expected to appear on-site for prelims. Everyone else, including those who have graduated can appear in the online mirror. We will have 95% seats for on-site students and 5% seats for online mirror students in the regionals. International Students will have separate seats. --- **Details** ------------------ Quantfest is a 3 stage Individual Contest: **Stage 1 (Prelims) :** To be held on campus by all 23 IITs, IIITH, IIITD, IIITA, IIITL, BITS Pilani, Goa and Hyde...

Full text and comments »

Coprime Integers Problem: Euler Totient Function I am trying to solve [Coprime Integers](https://open.kattis.com/problems/coprimeintegers). I believe the central idea to the problem involves the ETF, as I can solve the number of integers between a <= x <= b such that gcd(x, n) = 1, and loop this (or possibly leverage Euler Phi Function) for all c <= n <= d. If anyone has a general explanation of the solution, this would also be helpful. Nevertheless, ETF is "the number of integers [1...n] that are coprime with n. I need "the number of integers [1...c] that are coprime with n. For example, if n=40=2^3*5 and c=12, then the following 5 pairs are valid: (1,40), (3,40), (7,40), (9,40), (11,40). I think the way this should be generated is this: total number of integers &mdash; number of integers not coprime + the number of double counts= 12 &mdash; floor(12/2) &mdash; floor(12/5) + floor(12/10) = 5. However, this is too inefficient as inclusion-exclusion may take a long time. I know that the ETF is multiplicative and that phi(P1...

Full text and comments »

Precalculating phi function 1..N http://www.spoj.com/problems/ETF/ Is there an $O(N)$ method to calculate phi functions of all the numbers from 1 to N? I swear, i saw a post here on codeforces about it, but i just can't seem to find it. Anyway i used the fact that $\phi(n \cdot m) = \phi(n) \cdot \phi(m) \cdot \frac{d}{\phi(d)}$ where $d = gcd(n, m)$ + a sieve to solve the above problem in $O(N\log{N})$, is it possible to do it in $O(N)$?

Full text and comments »

SPOJ ETFS [Problem](http://www.spoj.com/problems/ETFS/) <br> My solution : [solution](http://pastebin.com/Kxj7SGua) <br> I was trying to solve this problem. It asks me to print phi(n) for n=a to b(inclusive). where, 0<a<b<10^14<br> and b-a<10^5<br> My solution is,<br> first do sieve and save all primes <= 10^7 in a vector prm. Then, run a segmented sieve to mark which ones are prime/composite in the range [a,b]. Then do another segmented sieve to calculate phi(n) in range [a,b]. <br> I used long long(also tried unsigned long long) almost everywhere, but i'm getting WA. Can someone give me some corner cases/reason why I may be getting WA. <br> Thank you.

Full text and comments »

LCMSUM I am trying to solve this problem but could not able to solve it. www.codechef.com/problems/LCMSUM After searching a lot on the web i find this. summation of (LCM[i,n]) for all i belongs to [1,n] = (((summation of ETF(d)) + 1)*n)/2. where ETF() euler totient function . and d belongs to set of diviors of n. Can anybody explain the logic behind it or how does it work. I am unable to find any explanation or details about it. So, can anyone help me.

Full text and comments »

Need Help on SPOJ ETFS Question. I am try to solve SPOJ ETFS Question [Question Link](https://www.spoj.com/problems/ETFS). [My Solution Link](http://ideone.com/3IMO41) I calculate prime no less than 10^7 using Seive and then suing segemnt seive calculate phi(i) for every i But getting WA asnwer...

Full text and comments »