Блог пользователя vintage_Vlad_Makeev

Автор vintage_Vlad_Makeev, 7 лет назад, По-русски

Всем привет!

Сейчас проходит первый тур Открытой олимпиады школьников по программированию, а уже завтра состоится второй. Олимпиаду подготовила Московская методическая комиссия, известная вам также по Московской олимпиаде школьников по программированию, Московской командной олимпиаде и олимпиаде Мегаполисов (раунды 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545, 567, 583, 594, 622).

Открытая олимпиада составляется из самых интересных и сложных задач, которые были предложены многочисленным коллективом наших авторов, поэтому мы решили провести рейтинговый раунд Codeforces, который состоится 07.03.2020 12:35 (Московское время) и будет основан на задачах обоих туров олимпиады. В каждом дивизионе будет предложено 6 задач и 2 часа на их решение.

В связи с этим мы просим всех участников сообщества, участвующих в соревновании, проявить уважение к себе и другим участникам соревнования и не пытаться читерить никоим образом, в частности, выясняя задачи у участников соревнования в Москве. Если вы узнали какие-либо из задач Открытой олимпиады (участвуя в ней лично, от кого-то из участников или каким-либо иным образом), пожалуйста, не пишите раунд. Участников олимпиады мы просим воздержаться от публичного обсуждения задач. Любое нарушение правил выше будет являться поводом для дисквалификации.

Задачи соревнования были подготовлены meshanya, cdkrot, wrg0ababd, vintage_Vlad_Makeev, DebNatkh, diko, voidmax, okwedook, ch_egor, V--o_o--V, Sender, grphil, mingaleg, KiKoS, Endagorion, budalnik под руководством cdkrot, ch_egor, vintage_Vlad_Makeev, GlebsHP, Zlobober и Андреевой Елены Владимировны.

Задачи для второго дивизиона были доработаны vintage_Vlad_Makeev, ch_egor и MikeMirzayanov, которому мы также говорим спасибо за системы Codeforces и Polygon, который использовался при подготовке задач этой олимпиады.

Всем удачи!

UPD1:

Разбалловка для обоих дивизионов стандартная: 500 — 1000 — 1500 — 2000 — 2500 — 3000

Заранее сообщаем, что из-за проведения официального соревнования исходные коды других участников будут недоступны ещё час после окончания раунда.

UPD2: Разбор

UPD3: Победители!

Div. 1:

  1. zhouyuyang
  2. Egor
  3. Rewinding
  4. mayaohua2003
  5. gtrhetr

Div. 2:

  1. Tutituti
  2. autoint
  3. Froggay
  4. WWLDX
  5. GMaster
  • Проголосовать: нравится
  • +154
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +165 Проголосовать: не нравится

3 years ago? wut?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hope for no accident!

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

im ok meme fire!

»
4 года назад, # |
  Проголосовать: нравится +35 Проголосовать: не нравится

3 years ago :D

»
4 года назад, # |
  Проголосовать: нравится -20 Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится -52 Проголосовать: не нравится

Please no mathforces!

»
4 года назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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.

»
4 года назад, # |
  Проголосовать: нравится -19 Проголосовать: не нравится

Paşa

»
4 года назад, # |
Rev. 2   Проголосовать: нравится -15 Проголосовать: не нравится

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?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +61 Проголосовать: не нравится

    As you can see, preparation of this contest started a long time ago (preparing most of the problems started even before announcement writing), so some of them we prepared by vintage Vlad Makeev and some by modern Vlad Makeev.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      preparing most of the problems started even before announcement writing

      You mean more than 3 years ago? XD

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

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?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What's the score for each problem?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    The scoring distribution for both divisions is standard: 500 — 1000 — 1500 — 2000 — 2500 — 3000

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    This might be the simplest explanation: Based on your rating before a contest starts, you are given an "expected rank", ie, you are expected to perform that well. If you outperform your expected rank then your rating increases and if you underperform, your rating decreases.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You can see the formula here. Though it is important, I don't care that much and use CF-predictor with live rating changes instead.

»
4 года назад, # |
  Проголосовать: нравится +60 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

Who else checked the date? :p

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is this contest rated?

»
4 года назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +92 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

After solving C

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

How to solve Div 2 D?

»
4 года назад, # |
  Проголосовать: нравится +48 Проголосовать: не нравится

Problem Div1 B was Info1Cup 2017 XORsum

»
4 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

How to solve Div2B

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I just search for windows with dimension a*b where a*b = K. I maintained prefix array of both the given array, and searched how many window of dimension 'a*1' are there in array A and how many window of dimension 'b*1' are there in array B. Multiply both the count and add to the final answer. This is O(sqrt(K) * (N+M)) solution.

»
4 года назад, # |
  Проголосовать: нравится +36 Проголосовать: не нравится

Hate SpeedForces.

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

How to solve div2 B??

»
4 года назад, # |
  Проголосовать: нравится +44 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

How to solve Div2 B?

»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    I tried to find for every $$$k$$$-th bit how many number are there such that $$$Bi+Bj$$$ $$$mod$$$ $$$2^{k+1}$$$ $$$>= 2^k$$$ where $$$Bi=Ai$$$ $$$mod$$$ $$$2^{k+1}$$$. I don't know if this is correct I had some bugs in code.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Same problem with me too, I implemented binary search instead of using lower_bound. It is giving TLE on test case 4. People who have used lower_bound did not get TLE. My submission: 72730048

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve div2 D?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What is testcase 6 in div2C?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I have no idea for div2 D!!!

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    To calculate if there's a carry in n-th binary position you can modify array a, and set bit n and higher bits to 0 in every number. Then after sorting array it is easy to count pairs of numbers with sum of 2^n or more. Pair counting step can be done in O(n), but I used binary search, which is n*log(n), and it worked fine.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +51 Проголосовать: не нравится

Before the contest: I want to solve Div1 D!

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

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

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

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +74 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

    Another proof of C would be the following.

    For a sets $$$S$$$, $$$T$$$, define $$$\gcd(S, T)$$$ as $$$\gcd$$$ of sum of elements of $$$S$$$ and $$$T$$$. We note the following, if $$$A \subseteq B$$$ then $$$\gcd(A, B) = \gcd(A, B - A)$$$.

    For two vertices we want $$$\gcd(N(u_1), N(u_2), N(u_1) \cup N(u_2))$$$, if $$$A = N(u_1)$$$ and $$$B = N(u_2)$$$.

    $$$\gcd(A, B, A\cup B) = \gcd(A, B, A\cup B - A) = \gcd(A, B, B - A)$$$
    $$$= \gcd(A, B - (B - A), B - A) = \gcd(A, A \cap B, B - A)$$$
    $$$= \gcd(A - A\cap B, A \cap B, B - A) = \gcd(A \cap B, A - B, B - A).$$$

    Notice that all these are all the sections of the Venn Diagram of $A$ and $$$B$$$. We can easily generalize to more sets (just use induction).

    We effectively have to sum all the nodes that are in the same section of the Venn Diagram. Two nodes are in the same section of the Venn Diagram if and only if, they are in the same $$$N(u_i)$$$'s which is the same as saying they have the same left neighbours. $$$\blacksquare$$$

    The dumbass I am, I didn't realize that the problem was trivial from here and managed to not solve it. :'(

»
4 года назад, # |
  Проголосовать: нравится -167 Проголосовать: не нравится

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;

}

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    can someone tell me how to ask question so that i will not get so many downvotes. I am new to codeforces. THis was my first contest. And i don't know what i did for getting so many downvotes

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      First important thing is to not post long code directly into your comment. Use a link instead

»
4 года назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +42 Проголосовать: не нравится

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!

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I really wouldn't want to be the one preparing tests for div1C. Not only is it possible to make a correct solution without realising it (see above), it's really easy to make a solution that's almost correct and distinguishing between them reliably is hard.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +38 Проголосовать: не нравится

      Oh yeah, it was quite hard to come with idea of strong tests. However there is a test with ~7500 non-zero degrees vertices in left half and exactly one subset of size 5 of vertices that you should handle to find proper GCD and connected graph.

      You can try to find such test yourself it's a very nice problem.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      You can make a solution by simply comparing neighboring vectors by size and elements instead of hashing. But indeed building strong tests for it are so difficult to me. I prefer preparing problems with easy work in generating data ^o^.

  • »
    »
    4 года назад, # ^ |
    Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится

    Mine's a randomised and a bit greedy solution as well. (greedily sorting vertices with several comparators and considering all prefix of vertices as subsets to calculate gcd).

    It passes systests, submitted after the contest. 72661488

    Unfortunately I tle'd systests during the contest with the same soln 72655512 thanks to using endl instead of '\n'. T-T

    Greedy comparators used: Sort left vertices in order of how less connected their right neighbours are to left vertices. Sort by degree.

»
4 года назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +21 Проголосовать: не нравится

    For me it was the opposite: C was very straightforward, I just looked at when some $$$x$$$ divides the GCD, and it was easy to see and prove that this holds when every non-isolated right-side vertex has value divisible by $$$x$$$ (assuming every right-side vertex has a distinct set of connections. If they do not, just join vertices with the same connections). I did get one WA from the isolated vertex case though.

    On the other hand, in D I had to work with this monstrosity: 72679047, which I couldn't optimise and debug in time.

»
4 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

How to solve div1C?

»
4 года назад, # |
  Проголосовать: нравится -17 Проголосовать: не нравится

Good Balance!

»
4 года назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    As the editorial, my O(NlogNlogMAX) time solution get TLE, maybe my implementation is not optimal enough. By the way, if I use int instead of int_64, I get wrong answer on the same test case, which means within time limits.

»
4 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Amazing problems, thanks for them!

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится -17 Проголосовать: не нравится

I Hate SpeedForces :(

»
4 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +46 Проголосовать: не нравится

    Yeah, it's quite sad that nobody had time for F, I like this problem very much :(

    However we dropped some hard problems from original competition to make this contest more solvable, but probably 0.5-1 extra hours were probably required.

»
4 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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

link

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    "Due to the official competition source codes of other participants will not be available for an hour after the end of the round."

    Wait a bit or paste the code to somewhere else, if you want to get an answer.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      Probably sensible to not paste code somewhere else as that kind of defeats the purpose of making codes not available. Just wait.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It seems I'm getting TLE due to std::cin. Why such a tight TL... Or is it intended to fail solutions with slower I/O?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      You are probably just doing it wrong. Using endl or sth like this. It's never an intention to fail solutions with iostream since it is not slower than cstdio when used properly.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Yes, I already replaced "cout<<ans<<endl" by "printf("%lld\n",ans)" and got accepted in less than one second, after failing by TLE at 72.

»
4 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

After long time i will reach on specialist.

Thank you codeforces .

»
4 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Pretest is weak?

»
4 года назад, # |
  Проголосовать: нравится +49 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Being a master was truly magnificent experience.

Au revoir!

»
4 года назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

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?

»
4 года назад, # |
Rev. 5   Проголосовать: нравится -35 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +150 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится -67 Проголосовать: не нравится

    So you knew that flushes could be a problem, but decided to use endl anyway, hoping that jury will comply with some imaginary policy that noone except you knows? Seems like you got what you deserved.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +99 Проголосовать: не нравится

      Not including all "simple" types of max tests (and I believe $$$t=500\,000$$$ is one of them) is a questionable decision, especially considering that large $$$t$$$ might be here for a reason. For example, my first idea involved factorizing a number as large as $$$10^{12}$$$, which is pretty hard when you have to do it $$$t$$$ times within 2 seconds.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +78 Проголосовать: не нравится

      I did not know how long it takes for Codeforces to process that amount of flushes. I used flushes to debug my solution locally, and forgot about it. I submitted the solution, saw that it passed within 1/3 of the time limit, and was completely convinced that it would not be that big of a problem.

      I didn't say that I deserved to pass using 500000 flushes; however, if such tests were present in the pretest, I would have known immediately what the issue was.

      For the "imaginary policy" part, feel free to enlighten yourself. Some quotes taken from the document:

      • Always make tests (at least) with minimum possible, maximum possible and some value in between for each variable and their combinations.

      • In general, pretests should include: a test with maximum size of input (e.g. maximum n), a test against integer overflow, a few random small tests.

      • There should be no warnings in polygon, except (if reasonable) "there are tests with input/output for statements [without TeX marks]". ("parameter 't' does not hit maximal value" is one such warning).

      I have involved in preparing some Codeforces rounds, I know what I am talking about. I don't pull facts out of my ass. Have a nice day.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится -43 Проголосовать: не нравится

        First and third points are about all tests, not pretests. Second point only implies that there should be a pretest with sum of $$$n$$$ equal to $$$500000$$$. Still don't understand why would you expect pretests to be perfect.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +34 Проголосовать: не нравится

          FYI, here is a screenshot taken from Polygon:

          As you can see, the system does warn about pretests being incomplete. In fact, if you insist on trying to nitpick things, the test with $$$t=500000$$$ and $$$n=1, m=1$$$ for each case also gives the maximum input size possible (about $$$1$$$ million more integers to read), therefore it should be included in the pretest (this is rather redundant, since the third quote already pointed that out anyway).

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится -74 Проголосовать: не нравится

            OK, authors are wrong. But still you relied on something that is not written in the rules (for contestants) and got punished. Seems right.

            • »
              »
              »
              »
              »
              »
              »
              4 года назад, # ^ |
                Проголосовать: нравится +47 Проголосовать: не нравится

              Yeah I mean people also expect each other to not tell a dick joke at the funeral, even if it's not written in the rules, and will be upset (rightfully so) if one does.

              But fair point I guess. Sorry for the bad analogy.

            • »
              »
              »
              »
              »
              »
              »
              4 года назад, # ^ |
              Rev. 3   Проголосовать: нравится +26 Проголосовать: не нравится

              Ignore: in prev version Russian colypasted joke

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится -23 Проголосовать: не нравится

    the same situation happened to SeehtEntity. You can consider it as a good experience :3

»
4 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

I guess B and C got swapped :(

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

To solve this problem,I use gets lol
72676564

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.com/contest/1323/submission/72650213

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    in your solution problem is with this statement " i=v.size()-1 " here v.size() is unsigned integer. make sure to convert it into int before using it like this "i=(int)v.size()-1".

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

zhouyuyang congratulations for rank 1.

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Wish Codeforces could be better and better.