3 years ago? wut?

Hope for no accident!

im ok meme fire!

3 years ago :D

Please no mathforces!

Blog post from 3 years ago.
Dude I thought my "5 months" were creepy enough. :D

What is the onsite format and how will both days be combined in one round? If the onsite is a 5h contest every day, then joining both in a 2h one seems brutal.

Paşa

The announcement said that this round "will be based on both days of the Olympiad. Each division will have 6 problems and 2 hours to solve them."

What does "both" means?

A. The problems of two divisions are same problems;

B. No problem exists in both division simultaneously;

My english is poor. Could anyone help me with it?

Two interesting problem setters in this round are vintage_Vlad_Makeev and Vlad Makeev

Should I prepare my vintage Paint MS for a vintage meme about vintage_Vlad_Makeev , vintage_Vlad_Makeev , vintage_Vlad_Makeev and that other guy whose handle I'm not going to type from my phone?

What's the score for each problem?

Can anyone explain how and how much rating increases or decreases depending on what factor ? I read this FAQ from codeforces Codeforces FAQ rating and div link but it is still not clear how much it changes and on what factor?

There are 11 Candidate Master among Div.2 registration and 9 Expert among Div.1 registration. When will it be corrected?

Who else checked the date? :p

Is this contest rated?

Schools are like:
Taught in Class: Div2 A
Solved for practice: Div2 B
Homework: Div2 C
Exams: Div2 D,E,F

After solving C

Why are we not allowed to copy others code in our system to check for hacking? We are only allowed to see others code. Previously we were allowed to copy also (around 7-8 months back).

How to solve Div 2 D?

Problem Div1 B was Info1Cup 2017 XORsum

How to solve Div2B

Hate SpeedForces.

How to solve div2 B??

Thanks for this great problemset, I haven't seen better one on Codeforces in a while.

How to solve Div2 B?

How to solve div 1 B. My time complexity was O(n log(n)*log(1e7)) which gave TLE on test case 4.

How to solve div2 D?

What is testcase 6 in div2C?

I have no idea for div2 D!!!

How to solve div 2 D? Was looking at a trie based approach but how to handle carries properly?

Did anyone solve with idea that converting to problem for binary array and do some stuff. btw I had something to do so I couldnt continue competing.

How to solve DIV 2D?? is it based on calculating freq array of all pair less than o(n^2) if yes then how?

Before the contest: I want to solve Div1 D!

After the contest: How to solve Div1 B and C ??

I have never seen a shitty contest like this. The problemset(Div.2) was completely imbalanced. Disgusting!!!

Div2D/1B was copied : https://oj.uz/problem/view/info1cup17_xorsum

Would still like to know how did you guys solve it ?

My solution to B: A sum $$$s = a_i+a_j$$$ (w.l.o.g. both $$$\lt 2^{k+1}$$$) has a bit $$$2^k$$$ set iff $$$s \ge 2^k$$$ and either $$$s \lt 2^{k+1}$$$ or $$$s \ge 2^{k+1}+2^k$$$. For each $$$k$$$, use a Fenwick tree to count them. $$$O(N \log^2)$$$ with a good constant.

C: Consider vertices from the right half. Let's ignore vertices with no edges to the left half. Merge vertices with the same sets of left neighbours. The answer is the GCD of the total weight and weights of all these merged vertices. Complexity: $$$O(M + N \log)$$$ with hashing.

Proof: consider the answer $$$g$$$ and its divisor $$$d$$$, which must divide the total weight. Among the merged vertices whose weights aren't divisible by $$$d$$$, find one with the smallest degree. If we take all vertices from the left half that aren't adjacent to it, then we take all other vertices from the right half, since all other merged vertices have $$$\ge$$$ degree and those with equal degree don't have the same set of neighbours, so their weight (total weight — weight of this not taken merged vertex) is indivisible by $$$d$$$.

D: There's a reasonably straightforward DP: for each aggressiveness $$$l$$$ and each suffix of already chosen candidates, calculate the maximum cost if we have $$$j$$$ people that fought and crossed over to aggressiveness $$$l+1$$$. This is $$$O(N^2M)$$$, but we can notice that the number of people that can cross over to gradually higher $$$l$$$ decreases exponentially, so we can remember the maximum $$$j$$$ that resulted in a reachable state for each $$$l$$$ and suffix. Complexity: $$$O(ok)$$$ probably.

I don't know what's wrong with this code for Div2 B. It's giving WA on testcase 3. Can anyone please tell my why??

include<bits/stdc++.h>

define lli long long int

define ulli unsigned long long int

pragma GCC target ("sse4.2")

using namespace std;

define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)

define time cout<<"\nTime Elapsed: " << 1.0*clock() / CLOCKS_PER_SEC << " sec\n";

int main() { fast; lli n,m,k; cin>>n>>m>>k; vector<pair<lli,lli>>vp; for(lli i=1;i<=sqrt(k);i++) { if(k%i==0) { vp.push_back({i,k/i}); if(i!=k/i) vp.push_back({k/i,i}); } } /*for(auto i:vp) { cout<<i.first<<" "<<i.second<<"\n"; } */ vectora,b; for(lli i=0;i<n;i++) { lli x; cin>>x; a.push_back(x); } for(lli i=0;i<m;i++) { lli x; cin>>x; b.push_back(x); }

vector<lli>dpa(n+1),dpb(m+1);
if(a[0]==1)
    dpa[0]=1;
if(b[0]==1)
    dpb[0]=1;
vector<lli>la,lb;
for(lli i=1;i<n;i++)
{
    if(a[i]==1)
    {
        dpa[i]=dpa[i-1]+1;
    }
    else
    {
        dpa[i]=0;
        if(dpa[i-1])
            la.push_back(dpa[i-1]);
    }
    if(i==n-1)
    {
        if(dpa[i]!=0)
            la.push_back(dpa[i]);
    }
}
for(lli i=1;i<m;i++)
{
    if(b[i]==1)
    {
        dpb[i]=dpb[i-1]+1;
    }
    else
    {
        dpb[i]=0;
        if(dpb[i-1])
            lb.push_back(dpb[i-1]);
    }
    if(i==m-1)
    {
        if(dpb[i]!=0)
            lb.push_back(dpb[i]);
    }
}
/*for(lli i=0;i<dpa.size();i++)
{
    cout<<dpa[i]<<" ";
}
cout<<"\n";
for(lli i=0;i<dpb.size();i++)
{
    cout<<dpb[i]<<" ";
}
cout<<"\n";
*/
lli las=la.size();
lli lbs=lb.size();
lli sz=vp.size();
lli total=0;
for(auto i:vp)
{
    for(lli j=0;j<las;j++)
    {
        if(la[j]>=i.first)
        {
            for(lli k=0;k<lbs;k++)
            {
                if(lb[k]>=i.second)
                {
                    total+=((la[j]-i.first+1)*(lb[k]-i.second+1));
                }
            }
        }
    }
}
cout<<total;











return 0;

}

Contest was unbalanced. Difficulty level between C and D was very wide.

The gap between Div2 C and Div2D doesn't nice at all

For Div1 C, I made a randomized solution, which is completely wrong. I submitted it 16 times before it got Pretests passed. So if I count with 1/16 chance to pass 12 tests and with about 96 main tests (8*12), then I have about (1/16)^8≈2*10^(-10) chance to pass main tests, so about 1 in a 5 billion. I like my chances!

D was much easier than C, in my opinion (just a straightforward dp). Also including isolated vertices in C was pure evil, Took me around a quarter to figure that out :/

Btw is the intended solution to E parallel binary search on the value of each index and then some book-keeping of left and right pointer for each index via DSU? If so, it was a bad idea to have it as E since not many would reach it in time (though it isn't much hard).

Nice problemset overall.

Is it just me or is the TL for E strict? I should have used a fast set instead of std::set.

How to solve div1C?

Good Balance!

Div2 D/ Div1 B — https://atcoder.jp/contests/arc092/tasks/arc092_b

Amazing problems, thanks for them!

Btw, statement of F was TERRIBLE, it got so many stupid things I am not even gonna point them out, cause it would take me too long

For Div2, Over 2k solutions for C, and about 100 for D. Quite a shift though

I Hate SpeedForces :(

Good problemset, but as I suspected squishing a 2-day 4-hour(?) contest into a single 2h round is just gonna make it too difficult.

Why is this solution to 1C getting TLE on test 72？

link

It seems many other people got TLE on the same testcase.

After long time i will reach on specialist.

Thank you codeforces .

So all the pretests in Div1B are either $$$n$$$ is even or $$$a_1\oplus a_2 \oplus a_3 \dots \oplus a_n=0$$$... lol

Pretest is weak?

The most important part for Div.1 C is not to use std::endl.

My solution for Div 1 A shows Pretest passed and I did not get any points for it. Does it mean it failed system test or something else? It is weird..

Will I get minus if I got wrong answer on pretest 1?

Being a master was truly magnificent experience.

Au revoir!

I took part in Codeforces Round #626 (Div. 1, based on Moscow Open Olympiad in Informatics) just now. I passed the pretest of problem A. But the system didn't send my solution into system test. Why does this happen？

My submission 72636993 got a TLE during system testing. Submitting the same exact same code does gets an AC!! Also the TLE was on test 5 wasn't it already included in the pretests??

The submissions:

72661261

The below submissions I just added another variable x, just to bypass submitting the exact same code twice. Other than that there is no difference in the codes.

72661081

72661159

72661597

Submissions image

vintage_Vlad_Makeev vintage_Vlad_Makeev ch_egor MikeMirzayanov

How come my code for B fail at test case 5 ,which was already present in pretests.

Okay, I will say it. The pretest for Div1 C is fucking garbage.

I passed pretests using only 580ms. The time limit is 2s. My solution is deterministic, and runs in basically the same time given that the input size is fixed.

It got TLE on test 72.

I then changed from cout << ans << endl; to cout << ans << '\n';. It now runs in 800ms.

It means that it takes at least 1.2s to flush 500000 times, which implies there is no such test where $$$t = 500000$$$ in the pretest (I really doubt the maximum $$$t$$$ in the pretest is even close). Now I'm pretty sure that Codeforces has the policy on problems that the pretest must satisfy i) it contains all corner cases on which some known solution fails and ii) all parameters specified in the problem must hit their respective maximal values. With that knowledge, I put my trust in the problem setters that they have at least complied with the policy and believed that Codeforces actually could handle 500000 flushes better than I thought. Turned out I was wrong on both, LOL.

It would be really great if anyone involved can explain the thought process (or lack thereof) behind the decision not to put such tests in the pretest.

I guess B and C got swapped :(

so sad, this sentence "Then output k distinct integers (1≤pi≤n), indexes of the chosen elements" in div2 A, Let me misunderstanding, i think it's k distinct integers a[i], not the index of a[i].

Unfortunately, Problem Div.1 B coincides with atcoder ARC092D.. TAT But it's nice problem anyway.

There is a small typo in the input section of the problem statement of the problem Div.1 D.

Finally this code got TLE on test 72...
72676139

To solve this problem,I use gets lol
72676564

Can anyone please tell me why this submission (for Div 2 B) gave run time error on TC 34, as on my compiler, for same case it gives the expected output 0 as answer? https://codeforces.net/contest/1323/submission/72650213

Can someone explain div1D because I can't get much of what the editorial is saying?

Div 2 was shit first 3 very easy and other all was out of mind #fuckedup

zhouyuyang congratulations for rank 1.

Wish Codeforces could be better and better.