EPIC Institute of Technology Round Summer 2024 (Div. 1 + Div. 2)
By Vladithur, 4 days ago, In English

EPIC

Hi, Codeforces!

We are pleased to invite you to EPIC Institute of Technology Round Summer 2024 (Div. 1 + Div. 2), which will be held on Jun/30/2024 17:35 (Moscow time). You will be given 8 problems, two of which are divided into two subtasks, and you will have 3 hours to solve them. The round will be rated for everyone.

At least one of the problems will be interactive, so please read the guide for interactive problems if you are not familiar with it.

We would like to thank:

We hope you'll like the problemset!

UPD: The score distribution is 250 — 750 — 1000 — 1500 — 1750 — (2000 — 500) — (3000 — 2000) — 5000

UPD2: Editorial (work in progress)

And now, a few words from today's sponsor!

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 older than 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 an 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. Fill out the form on the website.

  2. Take part in one of the entrance exams that will be held in our Codeforces group. You can also find past exam breakdowns there, which may help you in your preparation. Exam dates will be announced later, so stay tuned to the announcement channel and our LinkedIn group.

  3. If you successfully pass the exam, you will receive an invitation email.

What will happen after graduation?

All EPIC Institute of Technology graduates will get a diploma and the best students will be offered to join, either as an intern or a full-time position, one of the hot EPAM projects where skills acquired at EPIC Institute of Technology will be demanded.

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.

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

»
3 days ago, # |
  Vote: I like it +40 Vote: I do not like it

As a tester, I was blue at the time I tested.

→ Reply
»
3 days ago, # |
  Vote: I like it +16 Vote: I do not like it

As a tester, I was green at the time I tested.

→ Reply
»
3 days ago, # |
  Vote: I like it +19 Vote: I do not like it

As a tester, I had 0 contribution at the time I tested.

→ Reply
»
3 days ago, # |
  Vote: I like it +9 Vote: I do not like it

As a tester, I was orange while testing and then going roller-coaster to blue and then purple today.

→ Reply
»
3 days ago, # |
  Vote: I like it +14 Vote: I do not like it

As a tester, I was cooking my brain in blue.

→ Reply
»
3 days ago, # |
  Vote: I like it +1 Vote: I do not like it

As a tester, did I even test this?

→ Reply
  • »
    »
    39 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    why your profile have negative rating?

    → Reply
    • »
      »
      »
      33 hours ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      because he's really bad at cp

      → Reply
      • »
        »
        »
        »
        32 hours ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        no, i don't think so, he has authored contests in past.. i am curious how

        → Reply
»
3 days ago, # |
  Vote: I like it +26 Vote: I do not like it

EPIC site has really unique design

→ Reply
»
3 days ago, # |
  Vote: I like it +12 Vote: I do not like it

As I wasn't a tester, I don't know why I'm doing this...

→ Reply
»
3 days ago, # |
  Vote: I like it +59 Vote: I do not like it

Sir, I didn't find any section about authors

→ Reply
»
2 days ago, # |
  Vote: I like it +12 Vote: I do not like it

As a participant, I hope my color will also change after participation :)

→ Reply
  • »
    »
    38 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    +121? :o (btw i wanna get back to specialist after this contest, or at least stay at P)

    → Reply
»
2 days ago, # |
  Vote: I like it +18 Vote: I do not like it

As a tester, when did I test this?

→ Reply
»
2 days ago, # |
  Vote: I like it -20 Vote: I do not like it

As a participant, I hope to reach blue this round.

→ Reply
»
46 hours ago, # |
  Vote: I like it -34 Vote: I do not like it

233 point to CM, I can't wait

→ Reply
»
44 hours ago, # |
  Vote: I like it +33 Vote: I do not like it

wtf epic games hosting cf round?!11!

→ Reply
»
42 hours ago, # |
  Vote: I like it +11 Vote: I do not like it

Very few words indeed :)

→ Reply
»
42 hours ago, # |
  Vote: I like it +50 Vote: I do not like it

As a participant, I want to know how many problems there are, and whether there are any interactive problems.

→ Reply
»
39 hours ago, # |
  Vote: I like it +1 Vote: I do not like it

How many problems and what will be the score distribution of these problems in this round?

→ Reply
»
38 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

As a participant, I hope my color will be different after contest.

→ Reply
  • »
    »
    27 hours ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Even the number of colors you have may change! (By becoming lgm)

    → Reply
»
38 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

As a participant, I hope my color will be change after the contest.

→ Reply
»
37 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

As a participant, I hope to get my purple name back xD

→ Reply
»
36 hours ago, # |
← Rev. 2   Vote: I like it -22 Vote: I do not like it

Hello smart people, I wander through comments below posts to ask for helping with my problem.

I can`t solve problem, can you help me, please? I thank everyone in advance.

→ Reply
  • »
    »
    10 hours ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Thanks, anymore I don`t need your help, I have solved it

    → Reply
    • »
      »
      »
      10 hours ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I assume that you weren`t be able to open this task because it is private, if it is true, accept my apologies.

      → Reply
»
35 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

what is rating distribution for this round??

→ Reply
  • »
    »
    34 hours ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    The score distribution will be published later.

    → Reply
»
34 hours ago, # |
  Vote: I like it -16 Vote: I do not like it

As not a tester, how to be a tester actually?

→ Reply
  • »
    »
    34 hours ago, # ^ |
      Vote: I like it -19 Vote: I do not like it

    Very good Question actually. Someone please answer this.

    → Reply
    • »
      »
      »
      33 hours ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      If someone setting a round knows you and trusts you they might contact you to be a tester. It doesn't really have any requirements it's just up to the setters

      → Reply
»
29 hours ago, # |
  Vote: I like it +10 Vote: I do not like it

Can anyone join in the CF group?

→ Reply
»
28 hours ago, # |
  Vote: I like it +10 Vote: I do not like it

As a bored random person surfing Codeforces, I smiled reading other comments on this.

→ Reply
»
28 hours ago, # |
  Vote: I like it +10 Vote: I do not like it

hope to become CM again

→ Reply
»
27 hours ago, # |
  Vote: I like it +11 Vote: I do not like it

Plz approve the request to join the EPIC Institute of Technology group on Codeforces!

→ Reply
»
27 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm new to Codeforces so I don't know much about this but is this round affect my Codeforces rating or it will be unrated??

→ Reply
  • »
    »
    27 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Read the statement.

    → Reply
    • »
      »
      »
      27 hours ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Oh got it:) I though its not Codeforces one so it might be rated

      → Reply
»
26 hours ago, # |
  Vote: I like it +18 Vote: I do not like it

Vladithur is back )

→ Reply
»
26 hours ago, # |
  Vote: I like it +2 Vote: I do not like it

i hope i become purple after this round :)

→ Reply
»
25 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Are the problems in div1+2 harder than standard div2 problems?

→ Reply
  • »
    »
    23 hours ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    from experience, they are aaround the same in difficulty. Div1+2A ~ Div2A.

    → Reply
»
18 hours ago, # |
  Vote: I like it -17 Vote: I do not like it

Is it Rated?

→ Reply
»
15 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

How many problems will be there?

→ Reply
»
13 hours ago, # |
  Vote: I like it +7 Vote: I do not like it

i hope i can reach 1750 in the next two rounds QAQ

→ Reply
  • »
    »
    13 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    that means i have to rank about 1000 a little bit tricky..

    → Reply
»
11 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Wait no score distribution?

→ Reply
»
10 hours ago, # |
  Vote: I like it +10 Vote: I do not like it

Please publish the score distribution

→ Reply
»
8 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

as a tester, i wish you good luck, problems are good

→ Reply
»
6 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Do you think I can be an expert today?

→ Reply
»
6 hours ago, # |
  Vote: I like it +9 Vote: I do not like it

Hope to solve 5 problems this contest

→ Reply
»
6 hours ago, # |
  Vote: I like it +9 Vote: I do not like it

Maybe it will be my last div.1 contest before NOI2024.

Good luck to everyone.

→ Reply
»
6 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

What does (2000 — 500) mean in the score distribution? Why are there parentheses?

→ Reply
  • »
    »
    5 hours ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    It means Problem 6 is divided into two subtasks, where first one is worth 2000 points and second one 500 points. Second one is worth less because if you solve the first one, second one may be a bit easy after the knowledge you gain from the first. OR you may start second one directly as solving it will solve both of them at the same time.

    → Reply
»
5 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

I have braced myself for turning green again. But let's hope it doesn't come to that :)

→ Reply
»
2 hours ago, # |
  Vote: I like it +1 Vote: I do not like it

contest is not over yet, but i cant anymore. i thought i would at least solve 2 but ended up with one. anyways, good contest i guess

→ Reply
»
98 minutes ago, # |
  Vote: I like it +19 Vote: I do not like it

The pain of watching your rank go down for ~2hrs, minute by minute, as more cheaters submit the +1th(D) problem correctly. :(

→ Reply
»
98 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

375 pretests in H? What?

→ Reply
»
97 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

nice round) A in 2 mins, staring at B 1 hours, staring at C 0.5 hour, staring at D one hour

→ Reply
»
92 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

any hint for $$$D$$$?

→ Reply
  • »
    »
    90 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Some observations I made:

    Alice's strategy should be greedy

    Bob must take all of the occurrences of a cake for his actions to be useful

    Can we memoize based on position/turns?

    → Reply
    • »
      »
      »
      76 minutes ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I tried to implement a strategy where I count the number of elements of tastiness x > (greatest tastiness Alice has eaten) and then erase one of the elements from whichever element has the fewest identical elements, but I couldn't figure out how to implement it in time. I also don't know if it works.

      → Reply
      • »
        »
        »
        »
        19 minutes ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I also tried assigning cakes to bob greedily(minimum frequency first) but I got wa2

        → Reply
        • »
          »
          »
          »
          »
          16 minutes ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yeah I started with greedy too. The correct approach requires dp. The tutorial is out now.

          → Reply
  • »
    »
    52 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    solved using memoization (dp) ,logic is if bob has to remove any number than he remove all occurences of the number, calculate frequency of all element then store in a vector and do o(n^2) memoization (knapsack) you can see the memoization dp solution 268191223

    → Reply
»
92 minutes ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

The contest was nice, but am I the only one who feels that the problems were slightly on the standard side?

→ Reply
»
91 minute(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

D was a cool problem, here's how I solved it:

Alice's strategy is obviously greedy, so she should always take the minimum available cake. Then we can memoize based on the position in the array and the number of turns taken. Let Bob gain 1 turn every time Alice eats a cake, and have the choice to remove a cake from the game for freq[cake] turns. We can simulate this using DP in O(N^2).

Code
→ Reply
»
91 minute(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

What was D?

→ Reply
  • »
    »
    89 minutes ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Don't know what to do in CP, just try DP.

    → Reply
  • »
    »
    81 minute(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    • Alice will eat one of each cake tastiness in ascending order except for those tastiness values where Bob can eat all the cakes before Alice reaches it.

    • So for Bob the strategy is simple, he wants to pick the maximum number of tastiness values $$$t_1, t_2, ... t_k$$$ such that he can eat all of their cakes BEFORE Alice reaches the corresponding tastiness values.

    • Since it is only optimal for Alice to eat them in ascending order, we can sort the tastienss values in ascending order and do a knapsack like dp on their counts. Let $$$dp_{i, j}$$$ mean that Alice has managed to eat $$$j$$$ of the $$$i$$$ smallest cakes and Bob has $$$dp_{i, j}$$$ remaining turns for which we haven't decided what cake he ate. Then the transititions just become:

      $$$1$$$. Alice eats a cake of the current tastiness and Bob gains another turn — $$$dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)$$$

      $$$2$$$. We use Bob's remaining previous turns to eat the remaining cakes (if possible) — $$$dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] - cakecnt[i])$$$ (iff $$$dp[i][j] >= cnts[i]$$$).

    Then the maximum $$$j$$$ for which $$$dp[n][j]$$$ is $$$\geq 0$$$ is clearly the answer.

    → Reply
»
91 minute(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Is problem D just a greedy simulation with priority queue?

Edit: Nevermind, you can just do a linear iteration over possible Bob moves for each greedy Alice move and get $$$O(n^2)$$$

→ Reply
»
91 minute(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

After some dirty optimization, I passed the pretest test of problem E (hoping I could pass the systest by luck). Can anyone tell me how to do it correctly?

→ Reply
  • »
    »
    70 minutes ago, # ^ |
    ← Rev. 3   Vote: I like it +5 Vote: I do not like it

    If $$$a_v \gt \sum a_{child}$$$, then we clearly need to increment $$$a_{child}$$$ for some child.

    Notice that incrementing a node $$$v$$$ by $$$1$$$ means that we will need to increment some chain of nodes $$$x_1, x_2, \cdots x_k$$$ where $$$x_1 = v$$$, $$$x_i$$$ is a child of $$$x_{i - 1}$$$ and one of the following conditions is satisfied for $$$x_k$$$:

    1. $$$a_{x_K} \lt \sum a_{child}$$$
    2. $$$x_k$$$ is a leaf

    Also observe that a given node can be used as $$$x_k$$$ by the first condition at most $$$\sum a_{child} - a_{x_K}$$$ times, while a leaf node can be used an unlimited number of times.

    Moreover, such a chain results in a cost of $$$k$$$. So at any instant, we want to pick the shortest chain possible, i.e, pick a node least depth first among nodes in the subtree of $$$v$$$ which satisfy the above condition.

    So we can just store the number of possible contributions at each depth for the subtree of each $$$v$$$ while iterating using dfs and use the above approach to fix cases where $$$a_v \gt \sum a_{child}$$$.

    Code — 268172990

    → Reply
    • »
      »
      »
      64 minutes ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh, I understand now. Thank you for your explanation and the clean code.

      → Reply
»
90 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

Great contest, the problems are very clear to understand.

→ Reply
»
90 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

enjoyed the contest, really nice problems.

→ Reply
»
90 minutes ago, # |
  Vote: I like it -6 Vote: I do not like it

The samples are a little bit weak, especially for F and G1 :(

Couldn't debug G1 in time :(

Though my predictor says I have positive delta :)

→ Reply
»
88 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to be CM the first time after the system testing.

→ Reply
»
88 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D, was anyone else getting the right answers for the sample test when the code run locally but got WA on pretest 1 when uploaded to codeforces?

What should I do the next time this happens to me?

→ Reply
»
87 minutes ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

For about half an hour I was wrestling with MLE on problem E, but I still have very little idea what was really causing it in the first place: first submission that passed pretests 268214003, resubmission without clearing vectors by hand 268217966 (by the looks of it switching from pbds to a map solved the problem). Did I fall victim to some funny memory allocation shenanigans with vectors, or are pbds just that evil when it comes to memory consumption?

→ Reply
»
83 minutes ago, # |
  Vote: I like it +5 Vote: I do not like it

I feel the problemset is a bit too unbalanced because ABDEFG are optimization problems, considering the major classification between optimization and counting.

I liked D and especially F, though. Thanks for preparing the round!

→ Reply
»
83 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

constraints of D are just to trick?

→ Reply
  • »
    »
    79 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Maybe. Although I used O(n^2) approach, there possibly has an O(n) IMO.

    → Reply
    • »
      »
      »
      73 minutes ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      first attempt -> O(n^2 * log(n)) -> TLE
      second attempt -> fast IO -> MLE
      third attempt -> O(n * log(n)) -> pretest pass hope no FST
      really enjoyed the contest :)

      → Reply
»
79 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

does this approach work for problem D ?

every turn, Alice will choose the minimum cake that she didn't eat yet

then, Bob will take the maximum cake with the lowest frequency which Alice didn't eat, and he didn't eat all of them (every turn, Bob will reduce the frequency by one until there are no more cakes left with that number)

what did I miss ?

→ Reply
  • »
    »
    74 minutes ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Assume there's an array {t[1], t[2], ..., t[r]} and Bob need to let Alice can't eat cakes with tastiness t[i]. Then for each tastiness t of cakes, let f[t]=1 is Alice can eat it, f[t]=-cnt[t] if Alice can't eat it, then every prefix sum of f[t] must be non-negative. You need to find the maximum array size by DP.

    → Reply
»
78 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve c?

→ Reply
  • »
    »
    78 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Simulate the process.

    → Reply
    • »
      »
      »
      77 minutes ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The constraints are too high for simulation right?

      → Reply
      • »
        »
        »
        »
        76 minutes ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You could simulate it in O(n) actually.

        → Reply
        • »
          »
          »
          »
          »
          75 minutes ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          How? Please explain.

          → Reply
          • »
            »
            »
            »
            »
            »
            73 minutes ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            dp[n]=h[n], dp[i]=max(h[i], dp[i+1]+1)

            → Reply
          • »
            »
            »
            »
            »
            »
            63 minutes ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Traverse $$$a$$$ in reverse order. It is easy to see that the whole process will be terminated when $$$a_1 = 0$$$. Then, we only need to care about some positions $$$i$$$ such that $$$a_{i - 1} <= a_i$$$ because it will cause the process "delay". We will add $$$a_{i - 1} - a_i + 1$$$ to our result in this case because it is the required time to make $$$a_{i - 1} > a_i$$$. In the case that $$$a_{i - 1} > a_i$$$, we need to subtract $$$a_{i - 1}$$$ with the time that has passed, i.e our current result. The answer will be result added by the current $$$a_1$$$.

            Submission: 268158682

            → Reply
          • »
            »
            »
            »
            »
            »
            60 minutes ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            if a[i]>a[i+1] then ith will take a[i] amount of time to reach 0 but if a[i]<=a[i+1] then it will take some extra time which will be equal to the time a[i+1] takes to reach a[i]-1 so simulate this time taken by each tree from right to left and the time taken by the leftmost tree will be the answer

            → Reply
      • »
        »
        »
        »
        64 minutes ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        i thought about finding increasing order from backward(N , N-1...) and currTime will the index where this break + 1( if there if atleast 1 more value than maxValue of sequence) and making this segments and taking maximum time

        → Reply
  • »
    »
    60 minutes ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Try to find how the answer increase from [i+1....n] to [i....n].

    If a_i is smaller than a_i+1, it means there must be some point where a_i equals a_i+1, and when a_i+1 becomes 0, the work is done between[i+1....n], and more importantly a_i is now 1.so ans++. If equal, ans++.

    If bigger, it depends on what the current answer is. If current answer is bigger or equal than a_i, it still means there must be some point where a_i equals a_i+1, thus ans++. And if current answer is less, ans+=a_i-ans,which i guessed out.

    → Reply
  • »
    »
    59 minutes ago, # ^ |
    ← Rev. 6   Vote: I like it 0 Vote: I do not like it

    Since h>0, it is enough with:

    for (int j=0;j<n;j++) m=max(m,h[j]+j);

    (find the height which is the most costly)

    → Reply
»
75 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

is E slopetrick? if so i'd be depressed cuz i've been solving slopetrick problems.

→ Reply
  • »
    »
    68 minutes ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I just bashed it with brute force until it passed pretests (still can FST tho). I also considered small-to-large merging, but at the time I thought it was not going to work.

    → Reply
    • »
      »
      »
      58 minutes ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      merge what?

      And what is FST

      thank you so much

      → Reply
      • »
        »
        »
        »
        56 minutes ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        FST — fail system tests

        In short in my solution I was pulling negative sum nodes to their ancestors

        → Reply
        • »
          »
          »
          »
          »
          53 minutes ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          seems i wasn't even close to the proper solutions.

          and thx.

          → Reply
  • »
    »
    8 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes (at least the way I solved it)

    → Reply
»
74 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

Saw D and E and realised its way out of my paygrade so just watched the Euros instead. Still is surprising seeing so many AC on D and E. Can anyone explain them? I am really dumb

→ Reply
  • »
    »
    47 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    solved D using simple memoization (just think if bob has to remove any element then he should have to remove all occurrences of that element and just do dp[submission:268191223]

    → Reply
  • »
    »
    33 minutes ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    For D:

    Observation 1: Order does not matter, so move things around however we want

    Observation 2: It is always optimal for Alice to eat the smallest cake, so we should sort the cakes

    Observation 3: Bob should only eat a cake if he intends to eat all of those cakes of that level of tastiness

    So with that, we can reduce this problem down to: for each type of cake (so we aggregate into tastiness, frequency pairs) in sorted order of tastiness, will Bob eat all of this type of cake or will Alice eat one of the cakes?

    Let's think about the consequences of each action

    Alice eats the cake: +1 to Alice's score, but Bob can eat 1 more cake

    Bob eats the cake: Bob can eat $$$count[cake]$$$ fewer cakes, but Alice's score does not change.

    Let $$$dp[i, j]$$$ represent the minimum number of cakes Alice can eat, starting with the $$$i^{th}$$$ least tastiest cake with Bob being able to eat $$$j$$$ cakes.

    This leads to recurrences:

    $$$dp[i, j] = min(Bob, Alice)\\\\$$$
    $$$Bob = \begin{cases} dp[i + 1, j - count[i]] & \text{if } j \geq count[i]\\ 0 & \text{otherwise} \end{cases}\\\\$$$
    $$$Alice = dp[i + 1, j + 1]\\$$$
    → Reply
»
72 minutes ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Place your bets, gentlemens: will my F1 randomized solution with time cutoff FST or not?
FST
Not FST

→ Reply
  • »
    »
    70 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Spoiler
    → Reply
»
70 minutes ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

I have a solution for problem D with a complexity of $$$O(nlogn)$$$ 268173518. It's observed that Alice always picks the cake with the lowest tastiness from those remaining, and Bob will use some of his turns to take all cakes with the same tastiness. Therefore, we can solve this problem greedily. Specifically, when considering cakes sorted in increasing order of tastiness, if Bob can take all cakes with the same tastiness as the current cake being considered, we let Bob take them all. Otherwise, Bob will discard the maximum number of cakes he would have taken before and replace them with the current cake's value (provided there are fewer cakes of that value than the previous ones). Therefore, it's straightforward to use a priority queue to solve it.

→ Reply
»
68 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

Was C really easy or am I just stupid?

→ Reply
  • »
    »
    21 minute(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    many problems are easy... once you know the solution

    → Reply
»
68 minutes ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Another Cheatforces round...thank u indian students...submissions on C is crazy(bcoz code is small and easy to copy)

→ Reply
  • »
    »
    61 minute(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I once read somewhere..
    → Reply
»
68 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the contest! Problems were quite good! Enjoyed today!

→ Reply
»
65 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

Problems are clean and organized overall, but the samples are a bit weak, especially for problem F. Literally any code could pass it (even if the dp was completely nonsense).

BTW, E could be solved easily in $$$O(n\log n)$$$ with small to large merging, just curious why was the constraint $$$5000$$$?

→ Reply
  • »
    »
    49 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    BTW, E could be solved easily in $$$O(n \log n)$$$ with small to large merging, just curious why was the constraint $$$5000$$$?

    I suspect its to prevent irritating issues with overflows. Like, you need a leaf to contribute at least $$$n \cdot \max(a)$$$, but a node can sum to upto $$$n \cdot n \cdot max(a)$$$ which will overflow int64 for $$$n = 2 \cdot 10^5$$$ and $$$a_i \leq 10^9$$$. This is fairly easy to fix by capping the sum to $$$n \cdot \max(a)$$$ but its also irritating for no real reason.

    Also, I personally feel that adding small to large merging doesn't make the problem any better, its a bog standard implementation of it.

    → Reply
    • »
      »
      »
      41 minute(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The second reason is correct, I didn't feel like it added much to the problem)

      → Reply
»
63 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

Random stress tester for F save me from penalty for F1 (Wrong greedy (take from back if possible) passes all quite small cases, so I should try larger tests, but happily in random case the number of possible state is not so large)

→ Reply
  • »
    »
    55 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I actually was convinced the greedy idea was wrong but it passed ~500 rounds / 2 mins of stress testing at $$$N = 16$$$ so I submitted the code, only for it to find a countercase 2 seconds after submission T_T

    → Reply
  • »
    »
    40 minutes ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Sorry this might be dumb but what is random stress tester, is it different from stress testing we do?

    → Reply
»
63 minutes ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Everybody at cloudflare needs to be locked up

→ Reply
»
49 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm a little confused why G2 is separated from G1, the feeling of having to add many cases and pre-calculations into the code is really frustrating. (And I failed to debug it in time)

Using G1 only will make the problem more clean. Discard G1 and use G2 only will make the thinking process less interrupted and will prevent coding from being tedious in my opinion.

Anyway, the problems are good.

→ Reply
  • »
    »
    48 minutes ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    also curious if it is possible to implement G2 quickly and clean

    → Reply
  • »
    »
    11 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For me, the number of cases was the same for G1 and G2. For G2 all I needed to add was if statements before some of the cases from the G1 solution.

    → Reply
»
39 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

In this contest, I definitely reached the expert and at the end of the competition I decided to resubmit problem D with optimization (just like that, I understood that my first solution worked). But I didn’t know that only the last attempt is counted, where is it even said about this? And why some people have multiple parcels tested (in system tests). Because of this stupid rule, I will not reach the expert, thanks for this, any desire for programming is gone.

→ Reply
  • »
    »
    23 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    When a contestant realizes there is a bug in their submission, and have not yet locked it, they should be able to resubmit. Naturally, the last such attempt will be tested.

    If you want to submit an optimized version that shouldn't affect the standings, you can do it after the contest.

    → Reply
    • »
      »
      »
      20 minutes ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why can't system tests just test solutions in order?

      → Reply
      • »
        »
        »
        »
        19 minutes ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Because it will be abused by solutions which pass with certain probability?

        → Reply
        • »
          »
          »
          »
          »
          17 minutes ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Still, it is assumed that the pretests are good enough

          → Reply
          • »
            »
            »
            »
            »
            »
            1 minute ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Random algorithms are random no matter the test.

            So one could submit several random solutions and the chance of all of them failing would be significantly smaller.

            → Reply
»
37 minutes ago, # |
  Vote: I like it +15 Vote: I do not like it

lol

→ Reply
»
25 minutes ago, # |
  Vote: I like it +3 Vote: I do not like it

First Solves

A: InternetPerson10

B: tourist

C: gamegame

D: Benq

E: tourist

F1: tourist

F2: tourist

G1: tourist

G2: ecnerwala

H: Radewoosh

→ Reply
»
19 minutes ago, # |
  Vote: I like it +1 Vote: I do not like it

Thank you for the contest!

In particular, most of the problems get away from the common pattern of "solve me much faster than O(input^2)", which is nice and refreshing.

→ Reply
»
10 minutes ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

started 50 min late,great contest tho

→ Reply
»
3 minutes ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

can anyone plz tell what is wrong with my logic for B. here is my code-268197602

→ Reply