EPIC Institute of Technology Round Summer 2025 (Codeforces Round 1036, Div. 1 + Div. 2)
By Proof_by_QED, 10 months ago, In English

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 Jul/06/2025 17:35 (Moscow time). 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:

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

EPIC

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://mirror.codeforces.com/blog/entry/144382 editorial

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

»
10 months ago, hide # |
 
Vote: I like it +25 Vote: I do not like it

I AM satyam343'S BIGGEST FAN!!!

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

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.

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

As a tester, I really enjoyed the problems. Recommend to participate.

→ Reply
»
10 months ago, hide # |
← Rev. 2  
Vote: I like it +19 Vote: I do not like it

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.

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

As a tester, I tested two contests one in December and one three days ago.

→ Reply
»
10 months ago, hide # |
 
Vote: I like it -21 Vote: I do not like it

As a tester, this is by far the best div1+2 I have ever tested. (It is also the only one)

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

As a tester, I have no idea why I’m VIP tester.

→ Reply
»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Two contests two days is something I've never seen before...

→ Reply
»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

A 3 hour cry round 😳

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

As a tester, I pretend to test.

→ Reply
»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

This is surely gonna be a great and exciting round fr.

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

As a tester, this is the first contest I tested.

→ Reply
»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

As a tester, when did I test this round? I don't even have a clue what you're talking about...

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

As a responsible tester, I forgot to test this contest for 6 months.

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

As a monkey tester, the problems were good enough to remind me the taste of ginger.

→ Reply
»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

This round must be extremely tough due to the score distribution...

→ Reply
»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Looking forward to get absolutely destroyed by this contest (or not ?)

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

Finally a new Div1+2. I waited CF Div1 for whole June!

→ Reply
»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

EPIC!!

→ Reply
»
10 months ago, hide # |
 
Vote: I like it -26 Vote: I do not like it

Gotta make this Div1 count cause apparently now we get two Div1 contests per year lol

→ Reply
»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Isn't this the first time we get a non Div 3/4 round by cry

→ Reply
»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

i will go for an epic comeback

→ Reply
»
10 months ago, hide # |
← Rev. 3  
Vote: I like it -10 Vote: I do not like it

As a newbie should I participate or it will be too hard?

→ Reply
»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

good luck

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

If you are caught using AI in an unorthodox manner, you will be sent to cry's basement.

→ Reply
»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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-1 is easier than yesterday's div2D

but somehow they skipped (2000-3999] and directly 4000s problems are there LOL .. good luck div1 people

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

cry often releases Div3. May I ask Div1+2 = Div3 ?

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

Who is going to enroll in EPIC Institute of technology?

→ Reply
»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

After a long time div (1+2).

→ Reply
»
10 months ago, hide # |
 
Vote: I like it -18 Vote: I do not like it

Recommend noobs to stay away. Only good programmers enter otherwise stay home

→ Reply
»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Cry[user:Cry] can you motivate me to partcipate in today's contest?Please

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

What is the Invitation Code for the people who want to register with EPIC?

→ Reply
»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Are the testers allowed to participate in the round?

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

As a participant I hope cheaters are sent to cry basement.

→ Reply
»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

as a participant hoping for a positive delta .

→ Reply
»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Are there any prerequisites for joining the group? I want to see the previous exams but has not been granted access.

→ Reply
»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Holy moly that score distribution 2000 to 4000 is wild it's giving negative delta vibes lol God save us

→ Reply
»
10 months ago, hide # |
 
Vote: I like it -21 Vote: I do not like it

are you ready people !!!

to give up your sleep to get beaten by AI cheaters LMAO ...

lezzGOOO 3hours

→ Reply
»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

good luck

→ Reply
»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

okay, what to do for an hour now?

→ Reply
»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Sounds good, All the best everyone!

→ Reply
»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Damn 2 horrible contest performances in a row.

Wonder when it will end...

→ Reply
»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Good Questions!!

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

Finally cracked D in a Div. 1+2 contest for the first time.

→ Reply
»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Who in their right mind thought B was harder than A?

→ Reply
  • »
    »
    10 months ago, hide # ^ |
     
    Vote: I like it +3 Vote: I do not like it

    please share your idea of B after contest ends... I struggled a bit with B.

    → Reply
    • »
      »
      »
      10 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Same ,I struggled for an hour on B . And solved C at last min.

      → Reply
      • »
        »
        »
        »
        10 months ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        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.

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

      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]

      → Reply
    • »
      »
      »
      10 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      There can be two cases: First, we can make (1-based indexing) a2 = 0 and a1 = a1 + a2. So, then all the prefix minimums are going to 0 except for the first one. So the sum will be a1 + a2 in this case. However, this might not be the lowest possible sum. Because a1 could be less than a2 so we make the a2 = a2 + a3 and a3 = 0. In this case all the prefix minimums will be zero, except the first two ones. So the sum will be 2 * a1. This is better than the previous case because in the last case we were getting a1+a2 which is obviously larger than 2*a1. Since a1 is small than a2. So you can just print (a1 + min(a1, a2)) which handles both cases. And this is lowest sum possible.

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

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.

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

Hello depression my old friend!

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

Great problemset, had lots of fun!

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

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)

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

    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

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

      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!!!

      → Reply
      • »
        »
        »
        »
        10 months ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        that was very easy by using map 


        // Created on: 2025-07-06 22:58
// Author: Safwan_Ibrahim

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define endl '\n'

const int nn = 2e5 + 17;
int n, k; 
vector<int>A, B;

bool pos() {
    int cut = n - (k - 1);
    map<int, int>Mp;
    for (int i = 0; i < cut; i++) {
        Mp[B[i]]++;
    }

    for (int i = 0, j = n - 1; i < j;) {
        if (A[i] == A[j]) {
            i++, j--;
        }
        else {
            if (Mp[max(A[i], A[j])] <= 0) return false;
            Mp[max(A[i], A[j])]--;
            if (A[i] > A[j]) i++;
            else j--;
        }
    }
    return true;
}

void Try() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        A.push_back(x);
    }
    
    B = A;
    sort(B.rbegin(), B.rend());
    bool yes = pos();
    if (k != n) k++;
    yes |= pos();

    cout << (yes ? "YES\n" : "NO\n");
    A.clear(); B.clear();
}

int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);

    int t = 1; cin >> t;
    for (int i = 1; i <= t; i++) {
        Try();
    }
    return 0;
}
        → Reply
  • »
    »
    10 months ago, hide # ^ |
     
    Vote: I like it +3 Vote: I do not like it

    I used PBDS instead of segment tree, same logic easier on the implementation side though

    → Reply
»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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)

→ Reply
  • »
    »
    10 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
10 months ago, hide # |
← Rev. 2  
Vote: I like it +21 Vote: I do not like it

B>>C, E<D. Anyway it's a good contest!

→ Reply
»
10 months ago, hide # |
 
Vote: I like it -7 Vote: I do not like it

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?"

→ Reply
»
10 months ago, hide # |
← Rev. 2  
Vote: I like it +28 Vote: I do not like it

D E F G are very cool, but D is my favorite <3

→ Reply
  • »
    »
    10 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      10 months ago, hide # ^ |
       
      Vote: I like it +3 Vote: I do not like it

      You can show that you can always reduce a palindrome to only contain the values among the k-1 smallest values if one exists.

      → Reply
      • »
        »
        »
        »
        10 months ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        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!

        → Reply
    • »
      »
      »
      10 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      how did you use segtree to solve it ?

      → Reply
      • »
        »
        »
        »
        10 months ago, hide # ^ |
         
        Vote: I like it +3 Vote: I do not like 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

        → Reply
        • »
          »
          »
          »
          »
          10 months ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          ok thanks for this... I understand now. you used segtree for like checking the prefix frequency sum

          → Reply
  • »
    »
    10 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

How to solve C? I'm too dumb.

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

    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 ..

    → Reply
  • »
    »
    10 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      10 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Proof? How are we sure those elements where $$$ a_i \gt a_{i + 1} $$$ are divisible by the lcm?

      → Reply
      • »
        »
        »
        »
        10 months ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
    • »
      »
      »
      10 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      In this testcase:

      7
42 42 14 84 28 73080 255780

      $$$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$$$?

      → Reply
      • »
        »
        »
        »
        10 months ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          10 months ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          Thanks for your time but I still don't understand how simply taking the lcm works.

          → Reply
          • »
            »
            »
            »
            »
            »
            10 months ago, hide # ^ |
             
            Vote: I like it 0 Vote: I do not like it

            Sorry that I didn't explain it clearly. I think that the tutorial has a full proof.

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

the problems were actually really good, but I just couldn't perform well as I had expected to

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

How would you solve $$$F$$$? I had a $$$\text{dp[len][end_val]}$$$ defined, and I'm wondering if this is a correct approach.

→ Reply
  • »
    »
    10 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
10 months ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

Can someone check my code for E after the contest is over?

I'm not sure where my submission is wrong.

Here is my submission if anyone is willing to check it now :D

My Code

Edit: I found the error! It was since I forgot to replace an int with ll when printing values, unfortunate :(

→ Reply
»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    10 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it
    Hint
    → Reply
    • »
      »
      »
      10 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Wow i love implementing F 1 so much

→ Reply
»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

VERYY balanced contest after such a long time.. loved it!

→ Reply
»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

how to do d.?

→ Reply
»
10 months ago, hide # |
 
Vote: I like it -22 Vote: I do not like it

Problem E

Please tell me was this thought process correct and what was the way to get the values of vector b

For Problem E i first thought of calculating Prefix sum and suffix sums and check if there is a index where prefixsum[I] > suffixsum[i+1] and if there is no such index we can be sure that there is no way to get a to 0.(as we need to reduce elements of vector a, its only possible to make b_prefsum[I] = b_suffsum[i+1] if earlier we had a_prefsum[I] > a_suffixsum[i+1]) after that I couldn't understand how can I get all elements of a to become 0 under 17 steps.

is this correct ? 

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int INF = 1e17;
const int MOD = 1e9 + 7;
typedef pair<int,int> pi;
typedef pair<int,pair<int,int>> ppi;

const int N = 1e5 + 5;
int fact[N];

int power(int a, int b, int m = MOD) {
    int res = 1;
    while (b) {
        if (b & 1) res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

void precompute_factorials() {
    fact[0] = 1;
    for (int i = 1; i < N; i++)
        fact[i] = fact[i - 1] * i % MOD;
}

int nCr(int n, int r) {
    if (r > n || r < 0) return 0;
    return fact[n] * power(fact[r], MOD - 2) % MOD * power(fact[n - r], MOD - 2) % MOD;
}

int nPr(int n, int r) {
    if (r > n || r < 0) return 0;
    return fact[n] * power(fact[n - r], MOD - 2) % MOD;
}

void solve() {
    // your logic here
    int n;
    cin>>n;

    vector<int> a(n);
    for(auto &i:a)cin>>i;

    vector<int> ps(n),ss(n);
    ps[0] = a[0];
    ss[n-1] = a[n-1];
    for(int i = 1;i<n;i++)ps[i] = ps[i-1] + a[i];
    for(int i = n-2;i>=0;i--)ss[i] = ss[i+1] + a[i];

    bool f = true;
    int d = -1;
    for(int i = 0;i<n-1;i++){
        if(ps[i] >= ss[i+1])f = false;
        if(ps[i] == ss[i+1])d = i;
    }

    if(d != -1){
        cout<<1<<endl;
        for(int i = 0;i<n;i++)cout<<a[i]<<" ";
        cout<<endl;
        return;
    }
    if(f){cout<<-1<<endl;return;}

    vector<int> b = a;
    vector<vector<int>> ans;
    if(true){
        bool f = false;
        int index = 0;
        for(int i = 0;i<n-1;i++){
            if(ps[i] > ss[i+1]){
                index = i;
                break;
            }
        }

        int diff = ps[index] - ss[index+1];
        int x = -1;
        for(int i =0;i<=index;i++){
            if(b[i] >= diff){
                x = i;
                break;
            }
        }
        if(x == -1){
            cout<<-1<<endl;
            return;
        }
        b[x] -= diff;
        ans.push_back(b);
        for(int i = 0;i<n;i++){
            if(i == x){
                a[i] = diff;
            }else{
                a[i] = 0;
            }
        }
        ans.push_back(a);
    }

    cout<<ans.size()<<endl;

    for(auto c:ans){
        for(int i = 0;i<n;i++){
            cout<<c[i]<<" ";
        }
        cout<<endl;
    }
    
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    //precompute_factorials();
    int t;
    cin >> t;
    while(t--) solve();
    return 0;
}
→ Reply
»
10 months ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Why did you change the second sample in F2 (compared to F1), instead of adding a new one?

Nice trolling

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

oof I got got trolled hard by E. Figured it out last minute.

→ Reply
»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I felt I could do E but lol .. spend 20 min for some approach .. find a case where it fails .. repeat

→ Reply
  • »
    »
    10 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    what was the case that you found?

    → Reply
    • »
      »
      »
      10 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      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 S segments.. ie prefix and suffix have same sum and p is 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.

      → Reply
»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

great contest!

→ Reply
»
10 months ago, hide # |
← Rev. 2  
Vote: I like it +3 Vote: I do not like it

Though I couldnt submit on time, is my approach for solving D correct?

Idea:
Let e = k-th smallest element in array (after sorting with original indices).
We want to check if its possible to form a palindrome of length ≥ k-1 
using elements ≤ e (including multiple e(s) if needed).

1. Build array z = all elements ≤ e.
2. Check if elements strictly < e form a palindrome (call this y).
   If not, answer is NO.
3. Try to build longest possible palindrome using z (≤ e values), 
   allowing e as flexible wildcard to balance mismatches.
4. If length of such a palindrome ≥ k-1 → YES, else NO.
→ Reply
»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

F2 n=5000 why?

→ Reply
  • »
    »
    10 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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.

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

Why the constraint in E is set to 17?Does the author think he is humorous?

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

    Actually he helped you by stating that the maximum possible answer is only 17.

    → Reply
    • »
      »
      »
      10 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      by 17 I thought it had to do something with bit manipulation or permutation ... but of course I was not able to solve it.

      → Reply
  • »
    »
    10 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    I felt it can be done much quicker.. am I correct ?

    → Reply
  • »
    »
    10 months ago, hide # ^ |
     
    Vote: I like it +3 Vote: I do not like it

    Probably the author is 17 years old

    → Reply
  • »
    »
    10 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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

    → Reply
  • »
    »
    10 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    And I don't think a problem that intentionally leads contestants into wrong solutions is a good problem.

    → Reply
  • »
    »
    10 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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)

    → Reply
»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

There isn't any difference between $$$s\le2$$$, $$$s\le17$$$ and $$$s\le10^9+7$$$ in E...

→ Reply
  • »
    »
    10 months ago, hide # ^ |
     
    Vote: I like it +22 Vote: I do not like it

    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

    → Reply
»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Great contest, I loved the problems. It's just that today wasn't my day. I got stuck on problem C and didn't realize the obvious. I almost had it. Well, I guess it's time to say goodbye to my pupil.

→ Reply
»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

oh wow... system test is not even done and editorial is out, thanks authors..

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

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 :(

→ Reply
»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

NOICEEEEEE Contest!!!!!

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

Lots of proof by AC on this one

→ Reply
»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can anyone help me with why my code for D fails.This is my submission https://mirror.codeforces.com/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.

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

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.

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

"You are given an array..."

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

cant believe I fell sleep mid competition

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

As a participant, this has been by far the best Div. 1+2 I’ve given — definitely the most balanced compared to recent contests!

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

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...

→ Reply
  • »
    »
    10 months ago, hide # ^ |
     
    Vote: I like it -8 Vote: I do not like it

    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,

    → Reply
  • »
    »
    10 months ago, hide # ^ |
     
    Vote: I like it +19 Vote: I do not like it

    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!

    → Reply
    • »
      »
      »
      10 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I cannot see other people's code in the open hack stage of div3, and it shows N/A. How can I solve this problem? Is it a blind hack? In addition, I successfully became a green name after two div2 games, but now I still cannot see other people's solutions. How can I solve this problem? Or what specific requirements must be met to be allowed to see the code? Do I need to participate in a certain number of games or reach a certain rating?

→ Reply
»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Great problemset and enjoyable.

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

How does problem C's validator work?

→ Reply
»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

____________________________________________________________________________________________________ /\
/ \ / \ / \ / \ / <*> <*> \ / <|> \ / \ / _v______v__/ \ / \

→ Reply
»
10 months ago, hide # |
 
Vote: I like it -8 Vote: I do not like it

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?

→ Reply
»
9 months ago, hide # |
 
Vote: I like it -13 Vote: I do not like it

Dear Coeforces, There is some confusion I guess since my solution is coinciiding with someone else's solution. I would like to inform you that I have not copied my solution from someone else. I have solved the question by myself, please look into it

→ Reply
»
9 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Hello there, I have got a message saying that I have copied code for the contest for the problem 2119A which first of all my submission was wrong and was not accepted and second of all I have not copied any code or cheated please return my rating and anyway I apologise in case I have made any mistake.

→ Reply
»
9 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Problem E isn't very good,it cheat participants the extent of s and the solution is very boring.

→ Reply
  • »
    »
    9 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      9 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      9 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Since the size of s is a crucial point in this problem, I believe it's better to minimize direct descriptions of it.

      → Reply