TheEvilBird's blog

Codeforces Round #1078 (Div.2, based on Moscow Olympiad for Young Students, rated)
By TheEvilBird, 3 months ago, translation, In English

Hello, Codeforces!

This Sunday there will be a Moscow Olympiad for Young Students. This contest is prepared by Moscow Olympiad Scientific Committee that you may know by Moscow Open Olympiad, Moscow Team Olympiad, Metropolises Olympiad and All-Russian olympiad in the name of Keldysh.

We are glad to invite you to Codeforces Round 1078 (Div. 2) based on the problems of this olympiad, which will take place on Feb/08/2026 12:05 (Moscow time). Note the unusual time of the round. The round will be held according to the Codeforces rules and will be rated for all participants with rating below 2100.

Problems of this competition were prepared by silvvasil, Semen07, allvik66, dope, teraqqq guided by TheEvilBird, grphil and Helen Andreeva.

Thanks to FairyWinx for the round coordination, and also thanks for MikeMirzayanov и KAN for Codeforces and Polygon platforms, which was used to prepare problems of this olympiad.

We also thank:

The scoring will be available later.

UPD: Scoring distribution: 500 — 1000 — 1750 — 2000 — 2500 — (1750 + 1750)

UPD: Since the round is based on an onsite olympiad, viewing other participants' submissions and upsolving will be available starting from 12:00 UTC

UPD: Until 13:00 UTC due technical reason

UPD: Editorial

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

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

Hope to become expert again:)

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

no rated div.2 testers for a div.2 round?

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

Hope to become master again:)

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

GLHF!

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

orz

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

Hope to be pupil! :( --> :| --> :)

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

hope to reach CM

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

As a femboy, I hope to become an femboy expert!

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

It says that cf would be down 5 minutes before the contest for me

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

Hope to become expert again!!!

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

Please pay attention to the abnormal start time.

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

    Yes! I thought the starting time was supposed to be 2:35pm UTC (my codefolio app setted an event to my calendar to that particular time). Did it get re-scheduled?

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

Looking forward to being goomba stomped

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

Like all rounds "based on Moscow Olympiad" I expect $$$-1000$$$ contribution even before end of the contest.

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

My first contest. Hope to solve at least one problem.

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

My second contest，wish me high rating

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

SpeedForce A and B

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

It was supposed to be round where I get blue, but I got magic 10 extra points from somewhere (So it's round where I lose blue to tasks for 14yo's instead)

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

Generous scoring, don't you think?

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

isn't the scoring little bit surprising ? :)

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

Easy F1?

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

All my submissions have been skipped ever since the beginning of the round for seemingly no reason, what gives?

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

I think E is too easy to be an E.

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

rubbish problems

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

E 2500 and F1 1750 is crazy

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

Is D CHT ?

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

    greedy solves it

    you want to split x = totalsum/2 (this maximizes a*b)

    go down while you can (accumulated row sum does not exceed x) and then go right to get the missing elements

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

ImplementationForces

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

Isn't $$$D$$$ just implementation of the border? Because $$$(cnt / 2) * (cnt - cnt / 2)$$$ is always achievable?

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

is F2 FWHT?

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

    Yes. In F1 you can always FWT and iFWT in DFS, but in F2 you need to avoid doing these in DFS, by implementing single-index addition and query on FWT results.

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

    But the main difficulty of the task is to store the dynamics without causing a inverse transformation and only do it at the very end

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

      The XOR FWT can be defined by the following expression:

      $$$ FWT[i] = \sum_{i \circ j = 0} A[j] \;-\; \sum_{i \circ j = 1} A[j], $$$

      where $$$i \circ j = (-1)^{\operatorname{popcount}(i \land j)}$$$. Using an XOR linear basis, each value can be uniquely represented, which reduces the overall transformation to a series of single-index additions and queries. To do these, you only need to iterate all 2^k positions and add/subtract by checking $$$\operatorname{popcount}(i \land j)$$$.

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

any hints on F1 and F2?

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

Spent my whole time trying to solve D using DP... but it turns out to be a greedy problem :(

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

    Same, I was thinking of DP too.

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

    yeah, I skipped C, spent a lot of time to solve D with DP, at the end went back solved C but got not much point as it was later in the competition, and the last 30-40 minutes did nothing as I didn't have success at D earlier.

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

How to do C.

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

    iterate over all divisors of n and you can easily detect for each divisor i if it is possible to construct a string with informativity i.

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

    Store, all the candidate lengths that a repeating string can have. As, it must be divide n, hence, we will get at max. 192 different candidate lengths for any string. Now, we can just brute force them and the first smallest valid length will be our answer.

    Code : 361971199

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

    For each factor of $$$n$$$, check by brute force whether it is a feasible cycle length.

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

Why set problems like this? It’s a total waste of my time.

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

Why my solution fails for C https://mirror.codeforces.com/contest/2194/submission/361992869

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

The questions were Good I was only able to solve 2! How to solve C!

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

361978428 why WA? i feel like the reason's obvious but i can't seem to find it

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

Thanks for the round ! Congratulations to the setters/coordinator,

Here is my feedback about the problems

A
B
C
D
E
F
→ Reply
»
2 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

first contest ever, got absolutely destroyed :sob:

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

When can be upsolve,it is 12:00 UTC.

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

I think everyone who solved C but not B (like me) did so because they assumed only adjacent banks could transfer money to each other.

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

Oh yeah, I managed to upsolve E

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

D is to easy to be D , It is hardly a 1500 :\

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

D appeared to be a standard question but got no idea about C.

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

Can we have an extra registration time from the start of the contest instead of 10 minutes after the start? I had to wait for 10 minutes since I forgot to register.

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

The Note in problem B was intentionally constructed to make you overcomplicate the problem @.@

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

when will the ratings be updated

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

Why is it still not possible to upsolve problems?

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

Isn't 13:00 UTC passed already? Why is still upsolving not possible?

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

Good round!

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

Why I can't view other solutions?

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

105512D - Последнее испытание seems familiar, doesn't it?

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

I need help to find the test case for which my code fails (problem D). Let me know if anyone finds it.362024569.

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

Any hint for problem E?

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

can anybody tell me where am i wrong for question d?? >>>>

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll t,n,m,i,ones,first_row,ans,j,total_ones,flag,x;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        vector<vector<ll>>array(n,vector<ll>(m));
        for(i=0;i<n;i++)
        {
            for(j=0;j<m;j++)
            cin>>array[i][j];
        }
        ones=0;
        for(i=0;i<n;i++)
        {
            for(j=0;j<m;j++)
            {
                if(array[i][j]==1)
                ones++;
            }
        }
        if(ones%2==0)
        cout<<(ones/2)*1LL*(ones/2)<<endl;
        else
        cout<<(ones/2)*1LL*(ones/2+1)<<endl;
        ans=ones/2;
        first_row=0;
        for(j=0;j<m;j++)
        {
            if(array[0][j]==1)
            first_row++;
        }
        if(first_row==ans)
        {
            cout<<"D";
            for(i=1;i<=m;i++)
            cout<<"R";
            for(i=1;i<=n-1;i++)
            cout<<"D";
            cout<<endl;
        }
        else if(first_row>ans)
        {
            for(i=1;i<=m-ans;i++)
            cout<<"R";
            cout<<"D";
            for(i=1;i<=ans;i++) 
            cout<<"R";
            for(i=1;i<=n-1;i++)
            cout<<"D";
            cout<<endl;
        }
        else
        {
            flag=0;
            for(i=0;i<n;i++)
            {
                total_ones=0;
                for(j=0;j<m;j++)
                {
                    if(array[i][j]==1)
                    total_ones++;
                }
                if(ans>=total_ones)
                ans-=total_ones;
                else
                {
                    total_ones=0;
                    for(j=m-1;j>=0;j--)
                    {
                        if(ans==total_ones)
                        {
                            flag=1;
                            break;
                        }
                        else
                        {
                            if(array[i][j]==1)
                            total_ones++;
                        }
                    }
                }
                if(flag==1)
                break;
            }
            // printing the result
            for(x=1;x<=i;x++)
            cout<<"D";
            for(x=1;x<=j+1;x++)
            cout<<"R";
            cout<<"D";
            for(x=1;x<=m-1-j;x++)
            cout<<"R";
            for(x=1;x<=n-1-i;x++)
            cout<<"D";
            cout<<endl;
        }
    }
    return 0;
}
→ Reply
»
2 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Any idea when will the submissions get unlocked?

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

It was a pretty smooth contest, and my rating up.ヾ(≧▽≦*)o

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

This was my first contest. And i am a newbie now. （￣︶￣）↗　

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

Hello, I received a similarity warning for my submission for problem 2194E.

I would like to clarify that I solved the problem independently during the contest. I did not view or share any code with other participants, and I did not publish my solution anywhere. The approach I used is a standard Dynamic Programming solution, so similar implementations may naturally look alike.

I am fully willing to provide further explanation of my solution if needed. Thank you for your time and consideration.

→ Reply