Hello Codeforces Once Again
After months of hard work, cry, Lilypad and I are extremely proud to welcome you to participate in EPIC Institute of Technology Round Summer 2025 (Codeforces Round 1036, Div. 1 + Div. 2) at 06.07.2025 17:35 (Московское время). This round is combined for Division 1 and Division 2, and it will be rated for everyone.
You will be given $$$3$$$ hours to solve $$$9$$$ problems. One problem will be split into two subtasks.
We would like to thank the following people for making the contest possible:
- satyam343 for outstanding coordination, working tirelessly with us to improve problem quality and donating his own problems to us. I cannot thank him enough.
- Error_Yuan for proposing some ideas that weren't used in the end.
- Benq, Dominater069, nifeshe, __baozii__, and Friedrich for VIP testing.
- The rest of our seemingly infinite testers: EvenImage, 244mhq, A_G, N_z__, _istil, awesomeguy856, Dragos, prvocislo, Thienu, nika-skybytska, omeganot, IceKnight1093, MridulAhi, sammyuri, LipArcanjo, rexer, JagguBandar, yoru_sacri, conjectureguy, Intellegent, trash-can, AlperenT, -firefly-, efishel, amoeba4, spike1236, AksLolCoding, alexlikemath007, lunchbox, Mox_Taest3r, rewhile, reirugan, beaten_by_ai,IceWolf898, chromate00, SpyrosAliv, pianapolataa, macaquedev, larush, DivinePunishment, Non-origination, ALnQ417, ETL, Rahuldeb5, hotfog12, TiredPsyduck, squarebh, rlin61, and last but not least Yuhang_Pan.
- Alexdat2000 for Russian translations.
- MikeMirzayanov for Codeforces and Polygon.
The scoring distribution is below.
| A | B | C | D | E | F | G | H | I |
|---|---|---|---|---|---|---|---|---|
| $$$500$$$ | $$$1000$$$ | $$$1250$$$ | $$$1750$$$ | $$$2000$$$ | $$$(2000+2000)$$$ | $$$4000$$$ | $$$4750$$$ | $$$4750$$$ |
And now a word to our sponsors: EPIC Institute of Technology
About EPIC Institute of Technology
EPIC Institute of Technology is an innovative educational project, driven by the Deltix team under the EPAM Systems umbrella. As part of EPIC — EPAM Product Innovation Center, we aim to cultivate the brightest minds and prepare them for a future in cutting-edge technology projects.
Why EPIC:
EPIC Institute of Technology is an accelerator for the best talents. Our students will acquire hands-on experience in one of the selected major programs, all of which are highly demanded right now on top projects, together with the fundamental knowledge, so indispensable for real professionals. Successful graduates will have a unique chance to jumpstart their career on the most challenging and interesting EPAM projects worldwide. You will join the community of intelligent and driven individuals and have an honor to work with and learn from them.
Here are the answers to the most common questions:
How much does education cost?
EPIC Institute of Technology is completely free. There are no fees to register for exams, tuition fees or any other hidden liabilities. The only restriction for getting into EPIC Institute of Technology is age. You must be at least 18 years old to become a student.
How is the educational process organized?
Each program lasts exactly one year. The academic year consists of two semesters. Courses in the first semester are the same for all programs. Courses in the second semester depend on the selected major program.
During the semester, students complete homework assignments and take 2 exams—a midterm and a final. The final grade a student gets for each training course depends on the quality of completed assignments and participation in practical classes.
How will the classes be held?
Lectures will be pre-recorded and available for self-study. Practical classes will be held at the specified time according to the provided schedule. Also, students will have access to a Discord server, where they can discuss topics of academic interest with teachers and other students.
In what language will I study?
All programs are in English.
How can I apply?
The admissions process is as follows:
1) Register on our platform
— You can immediately try a test contest to check your readiness and get familiar with the platform.
2) Take one entrance exam on July 20, July 26, or August 1
— You only need to pass any single exam to qualify!
— If you don't succeed on one date, you can try again on the next.
3) Automatic enrollment for all who pass any exam.
Pro tip: Check out previous exam breakdowns in our Codeforces group for extra preparation help.
What will happen after graduation?
All EPIC Institute of Technology graduates will receive a diploma, and top students will be offered the opportunity to join EPAM projects where the skills gained during their training will be in high demand.
Please visit our website to learn more about EPIC Institute of Technology and the available programs. If you have any questions, you can quickly ask them in our chat. Stay tuned to our announcement channel and LinkedIn page and never miss an update!
We sincerely hope you will participate and enjoy the problems. Good luck!
UPD: score distribution released
UPD2: https://codeforces.me/blog/entry/144382 editorial
I AM satyam343'S BIGGEST FAN!!!
.
As a tester, I can confirm that satyam343 is nifeshe's biggest fan, and nifeshe is my biggest fan, so by transitive property, cry is my biggest fan too.
I don't think the fan relation has transitive property :)
As a tester, I can confirm that the most climactic moment during testing was when they said "welcome to the final problemset". Except for the fact that it wasn't the final problemset.
As a tester, I recall this happening at least three times.
As someone who met alnq irl, I can confirm he looks like his pfp.
As your doctor, I diagnose you with Lupus.
As a tester, I really enjoyed the problems. Recommend to participate.
As a tester, I really enjoyed the QEDFhjzh. Recommend to participate.
As a participant, I was invited to test this round when it was a div2 but thankfully I was lazy so I can participate officially.
ha ha ha !!!
As a tester, I tested two contests one in December and one three days ago.
As a tester, this is by far the best div1+2 I have ever tested. (It is also the only one)
As a tester, I have no idea why I’m VIP tester.
Hey I didn't cheated why my submission got skipped verdict is it due to twice submission
If you submit twice, your first submission will be skipped.
Two contests two days is something I've never seen before...
welcome to codeforces, i guess
A 3 hour cry round 😳
As a tester, I pretend to test.
This is surely gonna be a great and exciting round fr.
As a tester, this is the first contest I tested.
As a tester, when did I test this round? I don't even have a clue what you're talking about...
As a
responsibletester, I forgot to test this contest for 6 months.As a monkey tester, the problems were good enough to remind me the taste of ginger.
This round must be extremely tough due to the score distribution...
Looking forward to get absolutely destroyed by this contest (or not ?)
Finally a new Div1+2. I waited CF Div1 for whole June!
Gotta make this Div1 count cause apparently now we get two Div1 contests per year lol
Isn't this the first time we get a non Div 3/4 round by cry
As a newbie should I participate or it will be too hard?
please participate..
unless rating is very important to you for some reason... never skip contests because it will be too hard
I believe you're right. I will participate no matter what just to LEARN
lezzzzgo!!!
good luck
If you are caught using AI in an unorthodox manner, you will be sent to cry's basement.
ok so score distribution is interesting..
first of all many problems have small score so more problem solving for div2 folks.. I am hoping
F-1is easier than yesterday'sdiv2Dbut somehow they skipped
(2000-3999]and directly 4000s problems are there LOL .. good luck div1 peoplecry often releases Div3. May I ask Div1+2 = Div3 ?
you will find out
Who is going to enroll in EPIC Institute of technology?
Are the testers allowed to participate in the round?
Bro's follow up: Are problem setters allowed to participate in rounds?
As a participant I hope cheaters are sent to cry basement.
as a participant hoping for a positive delta .
Holy moly that score distribution 2000 to 4000 is wild it's giving negative delta vibes lol God save us
are you ready people !!!
to give up your sleep to get beaten by AI cheaters LMAO ...
lezzGOOO 3hours
okay, what to do for an hour now?
same lol.. watching my rank falling down
Good Questions!!
Finally cracked D in a Div. 1+2 contest for the first time.
D is not a trivial question, congrats !!!
Who in their right mind thought B was harder than A?
please share your idea of B after contest ends... I struggled a bit with B.
Same ,I struggled for an hour on B . And solved C at last min.
I also made one WA for B :( ..
although my logic was correct I had array indexing issues lol.. and then I spend a lot of time thinking my logic is wrong lmao.
find the first occurrence of 0 in array(let's assume it ind) and remove all the remaining elements from ind to n-1 from array then if size of remaining vector is 0 then return 0 else if size is 1 then return v[0] else if v[0]<v[1] then return 2*v[0] else v[0]+v[1]
I cancelled some of my weekend plans in the hope that I will get < 1000 rank in at least one of the div2 contest and will get closer to CM rank... but I have failed..
next time I will go out and touch grass for more happiness.
Hello depression my old friend!
Great problemset, had lots of fun!
Any way of solving D elegantly without frequency checks through a Segment Tree?? The greedy technique (in case v[k — 1] == v[k — 2] in the sorted version of the array led to a very tedious implementation for me)
First, remove all elements > the k-th smallest element. Then check if all elements < the k-th smallest form a palindrome. Then try to adjust the k-th smallest element
yeah exactly. but the implementation felt too long. it's like a check for <k for palindromes, then check for each interval between those whether we can accomodate kth smallest element. also need to take care of the additional palindrome check for <k where that array's size is even.
WAIT i realized. i thought we had to check twice for <k elements and also add the kth element between for the odd case. completely overlooked that it had to be palindrome on it's own!!!
that was very easy by using map
I used PBDS instead of segment tree, same logic easier on the implementation side though
Do we divide the array based on where the prefix sum >= the suffix sum in E, and then continue doing this to get the answer? (while adjusting the difference)
if the sum of all elements is odd then return -1 else find the first ind such that arr[0]+..+arr[ind]>=sum/2 if it is exactly sum/2 then print 1 and return the complete array else check if arr[0]+..+arr[ind-1]>=arr[ind]-sum/2 if no then return -1 else print 2 and for the first operation print a sum of arr[ind]-sum/2 from 0 to ind-1(using any combination) and arr[ind]-sum/2 at the ind position and 0 for ind+1 to n-1, now for the second operation print the remaining array.
B>>C, E<D. Anyway it's a good contest!
I am starting to think the authors like arrays. Literally all problems were like "you have an array and an operation on this array, what happens?"
Good luck defining algorithms without arrays or primitive operations :)
D E F G are very cool, but D is my favorite <3
Any way of solving D elegantly without frequency checks through a Segment Tree?? The greedy technique (in case v[k — 1] == v[k — 2] in the sorted version of the array led to a very tedious implementation for me) -- copied from my own comment
You can show that you can always reduce a palindrome to only contain the values among the k-1 smallest values if one exists.
i realized my mistake. i devolved into too much casework. i had the <kth element palindrome check in mind since the beginning, just mistakenly overlooked that it has to be a palindrome in either case of odd or even, the kth element just fills it's place accordingly. Thanks!
how did you use segtree to solve it ?
i cached frequencies. observed that v[i] <= n, so no coordinate compression needed. now i run two pointer for l and r, starting from both corners. if they are equal, move on ofc. Then I check if we encounter both l and r such that the frequency prefix sum < k. then it's a direct NO. else, if prefix sum for l >= k, it means there exist k elements smaller than it, and it can be removed. i move l, else i move r. if the process results in l >= r without a NO, its a YES
ok thanks for this... I understand now. you used segtree for like checking the prefix frequency sum
Yeah, I solved it with black, gray, white analogy. Black being the elements we don't care, white being the ones that are fixed, and grays were the only ones to check/adjust.
How to solve C? I'm too dumb.
I didn't prove it but any time ... a[i+1] is not divisible by a[i] .. this means a[i] has been modifid... we can find some portion of answer from a[i] ... and I did this repeatedly over the array .. and it actually passed the time limit in pretest ..
If we have a[i] not dividing a[i+1], then a[i] / gcd(a[i], a[i+1]) has to be divided out of a[i]. So our final answer will need to be divisible by a[i]/gcd(a[i], a[i+1]). Since it is guaranteed that an answer exists, we can take the lcm of all of these values.
Proof? How are we sure those elements where $$$ a_i \gt a_{i + 1} $$$ are divisible by the lcm?
Just by the fact that we're guaranteed that a solution exists. Since a factor of x is required at some position, then for any position at which we need to divide by x, (ie whenever a[i] doesn't divide a[i+1]), then a[i] / x will have to be an integer. So x | a[i].
I hope that was clear, but it didn't really feel like it, sorry. I can try to type it up better if its not. Also note that needing to divide at a position is not the same as when a[i] > a[i+1], think of [6, 10] for example.
In this testcase:
$$$x$$$ is divisible by
42/gcd(42, 14) = 3, 84/gcd(84, 28) = 3, 73080/gcd(73080, 255780) = 2, which is $$$6, 12, 18, ...$$$ but $$$x = 12$$$ is a wrong value of $$$x$$$?We take the lcm, not just the product. So instead of 3, 12, 18, it would be 3, 3, 6, since lcm(3, 3) = 3, then lcm(3, 2) = 6.
Thanks for your time but I still don't understand how simply taking the lcm works.
Sorry that I didn't explain it clearly. I think that the tutorial has a full proof.
the problems were actually really good, but I just couldn't perform well as I had expected to
How would you solve $$$F$$$? I had a $$$\text{dp[len][end_val]}$$$ defined, and I'm wondering if this is a correct approach.
for F1, I suppose you need to specifically judge the edge case of "whether the previous permutation starts with 1" due to repetitive countings that might occur for stuff like 12312.
How to do E? I am not able to figure out the most effective way, but I figured out that if the array has even sum and follows polygon property then it can be reduced to smaller such arrays.
Solve for $$$n = 3$$$ first.
I had a solution for $$$n=3$$$, i.e., first eliminate the max number and then we will have equal elements, given it follows the above conditions I mentioned, so that way answer would be either 1 or 2.
Wow i love implementing F 1 so much
Thinking about F1 solution took me like 25min, while the coding took me ages.
Are you from Red Bull?
VERYY balanced contest after such a long time.. loved it!
made a lot of blunder wrong submissions this time :') lets see if im able to cross 1900
Indeed
Why did you change the second sample in F2 (compared to F1), instead of adding a new one?
Nice trolling
oof I got got trolled hard by E. Figured it out last minute.
I felt I could do E but lol .. spend 20 min for some approach .. find a case where it fails .. repeat
what was the case that you found?
no my approach was wrong.. I started by thinking that I can always do it in 2 steps and I came up with some approach which can solve some case in 2 steps .. but then later realized it was wrong.
although not correct my initial approach was if I can find something like
S p Ssegments.. ie prefix and suffix have same sum andpis small even number .. then I can solve this in 2 steps by dividing p into two equal groups in 2 operations.. I was trying to build on this approach but kept failing.Though I couldnt submit on time, is my approach for solving D correct?
F2 n=5000 why?
Is there any "should be tle solutions"(like O(N^3) solutions) that passes n=2500 and gets tle on n=5000? What is the purpose of n=5000? Many O(N^2) sols got TLE including tourist's sol. Sorry if I sounded offensive, I'm really frustrated right now.
Tourist solution is not n^2, there you have your example :)
I had a $$$O(n^3/64)$$$ bitset solution that was quite close to TL (but didn't submit it), so there were good reasons for that
Thanks guys, never thought about bitset
Why the constraint in E is set to 17?Does the author think he is humorous?
Actually he helped you by stating that the maximum possible answer is only 17.
by 17 I thought it had to do something with bit manipulation or permutation ... but of course I was not able to solve it.
I felt it can be done much quicker.. am I correct ?
Probably the author is 17 years old
I was trying a recursive solution but didn't have enough time to implement, but I made many assumptions that I weren't sure holds true
First I assumed the optimal solution chooses a b with the maximum sum possible every time Then I assumed if there were 2 middle indexes that made b maximum, then either index works for further recursion
saw the editorial, I got trolled
And I don't think a problem that intentionally leads contestants into wrong solutions is a good problem.
it felt like a misdirection to me lol.. he was trying to mislead us into thinking towards binary search or some logN divide and conquer technique... (oh.. which i now realize couldve been a great start to come up with the correct solution lol)
There isn't any difference between $$$s\le2$$$, $$$s\le17$$$ and $$$s\le10^9+7$$$ in E...
There is some, as the purpose (i guess) is to show that output is guaranteed to be small and don't give out the solution in the same time. Still, 17 seemed too specific and might mislead someone(myself included). 20 or 50 would serve the same purpose
I don't think it is necessary to mention a very specific boundary of s, because finding it is part of the solution.
The boundary is usefull in some solutions I run the loop till 17 and if no solution found I stop Without this boundary I would have had to deduce s<=2
oh wow... system test is not even done and editorial is out, thanks authors..
Great round. Managed to find the error in my F1 in the last one minute but didn't have time to fix it. Skill issue :(
Lots of proof by AC on this one
Can anyone help me with why my code for D fails.This is my submission https://codeforces.me/contest/2124/submission/327823582
I shall explain my logic- If k<=2 then we can reduce array to <=1 elements which will be a palindrome Now for k>3 We take 2 cases,with k-1 elements and k elements.This is to ensure I solve for both even,odd parity. moving forward approach is same for k,k-1.Wherever k is written replace k-1 for k-1 case Now in each case,we mark val=a[k] I sort elements by value,put first k elements into vector.I don't put elements which are equal to val.All values in array which are equal to val,I put then into a set. Now basically what I have done is,I am checking if I have an initial palindrome,then rest elements I insert to reach total count and those elements have value=val.I put them symmetrically in exisiting palindrome. So i sort exisiting vector my position,then see if it is palindrome If yes then I proceed ahead and try to place elements==val symmetrically to reach total count.If I can place then output true,else false.
Such a well balanced round. I felt F to be easy until i coded and realized that I solved " How many different ways exist to build a valid array of size n", instead of number of distinct arrays and i was never able to arrive at the soln for the distinct arrays ones.
Loll i just read the editorial and i realized i was on the right track... NOOOOOOOOOO
i skipped E and jumped straight to F1 thinking it was straight forward dp. realized i was double counting after implementing whole solution and couldn't fix it
"You are given an array..."
cant believe I fell sleep mid competition
As a participant, this has been by far the best Div. 1+2 I’ve given — definitely the most balanced compared to recent contests!
I do not have any complaints about quality of individual problems, I think they were interesting (especially H, which I didn't solve, but found it very nice), but 9 out of 9 problems being about 1-dimensional arrays was too much...
I agree. Maybe I chose exactly the set of problems that were similar, but I only solved ad-hoc and DP problems about operations/subsequences on arrays the entire $$$3$$$ hours. Although the problems were nice,
Thanks for the feedback. I can totally see where you were coming from, and in problemsetting process we definitely were trying to avoid too many problems of the same topic (at one point, we had too many constructive problems in early positions). However, here I thought it’s okay since the problems all have different solution approaches. Also, I was a tree problem and G was a “solve q queries problem” in disguise.
Point taken, though!
I agree with you. Though I can personally understand why this may bother other people I literally don't care as long as the solutions to the problems feel different. After testing and then upsolving all 9 problems I didn't even realize all of the problems were about arrays and operations.
How does problem C's validator work?
Maybe greedily try dividing by x from the back to the front.
Oh my! a contest announcement! I can't wait to start! it must be coming so soo............. 10 DAYS???????? Y'all ought to be kidding me right? is this for real?
chill man the contest was 4 days ago what are you talking about
Problem E isn't very good,it cheat participants the extent of s and the solution is very boring.
Solution being boring is an understandable complaint. How fun one finds the solution is subjective.
However, I don't think saying that 17 being on the statement is a valid complaint. 17 is there so that participants know that the number of moves is limited (so they do not have to output too many numbers). It is the participant's fault if they interpret the number as a hint to the solution being done in LOG steps.
You are correct, but I think it would be better if you explicitly state that for all inputs contestants need to handle in this problem, the output does not exceed a certain scale. It’s entirely unnecessary to claim that we can prove s is bounded by some value; you only need to specify that s × n is guaranteed to be below a certain limit for all test cases. This avoids potential confusion. And this kind of confusion is meaningless. Thank for your reply.
Since the size of s is a crucial point in this problem, I believe it's better to minimize direct descriptions of it.