vintage_Vlad_Makeev's blog

Codeforces Round #626 (Div.1, Div.2, based on Moscow Open Olympiad in Informatics, rated)
By vintage_Vlad_Makeev, 7 years ago, translation, In English

Hello!

Right now happens the first tour of the Open Olympiad in Informatics, and tomorrow will be the second one. This contest is prepared by Moscow Olympiad Scientific Committee that you may know by Moscow Team Olympiad, Moscow Olympiad for Young Students and Metropolises Olympiad (rounds 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545, 567, 583, 594, 622).

Open Olympiad consists of the most interesting and hard problems that are proposed by a wide community of authors, so we decided to conduct a Codeforces regular round based on it, which will happen on Mar/07/2020 12:35 (Moscow time) and will be based on both days of the Olympiad. Each division will have 6 problems and 2 hours to solve them.

We kindly ask all the community members that are going to participate in the competition to show sportsmanship by not trying to cheat in any manner, in particular, by trying to figure out problem statements from the onsite participants. If you end up knowing some of the problems of Moscow Open Olympiad (by participating in it, from some of the onsite contestants or in any other way), please do not participate in the round. We also ask onsite contestants to not discuss problems in public. Failure to comply with any of the rules above may result in a disqualification.

Problems of this competition were prepared by meshanya, cdkrot, wrg0ababd, vintage_Vlad_Makeev, DebNatkh, diko, voidmax, okwedook, ch_egor, V--o_o--V, Sender, grphil, mingaleg, KiKoS, Endagorion, budalnik guided by cdkrot, ch_egor, vintage_Vlad_Makeev, GlebsHP, Zlobober and Helen Andreeva.

Problems for second division were prepared by vintage_Vlad_Makeev, ch_egor and MikeMirzayanov, to who we also want to say thanks for the Codeforces and Polygon systems.

Good luck everybody!

UPD1:

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

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

UPD2: Editorial

UPD3: Winners!

Div. 1:

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

Div. 2:

  1. Tutituti
  2. autoint
  3. Froggay
  4. WWLDX
  5. GMaster
  • Vote: I like it
  • +154
  • Vote: I do not like it

Comments Comments (156)
| Write comment?
»
4 years ago, # |
  Vote: I like it +165 Vote: I do not like it

3 years ago? wut?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope for no accident!

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

im ok meme fire!

→ Reply
»
4 years ago, # |
  Vote: I like it +35 Vote: I do not like it

3 years ago :D

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

→ Reply
»
4 years ago, # |
  Vote: I like it -52 Vote: I do not like it

Please no mathforces!

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

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

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

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.

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

    The are two days, each has 4 problems for 5 hours.

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    Each of these problems have subtasks, so they may be given I suppose.

    → Reply
»
4 years ago, # |
  Vote: I like it -19 Vote: I do not like it

Paşa

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -15 Vote: I do not like it

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?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    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.

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

      preparing most of the problems started even before announcement writing

      You mean more than 3 years ago? XD

      → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

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?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the score for each problem?

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

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

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

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

    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.

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

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it +60 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it -10 Vote: I do not like it

Who else checked the date? :p

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is this contest rated?

→ Reply
»
4 years ago, # |
  Vote: I like it +17 Vote: I do not like it

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +92 Vote: I do not like it

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

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

After solving C

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    Only in edu round, you are allowed to copy.

    → Reply
»
4 years ago, # |
  Vote: I like it +17 Vote: I do not like it

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

How to solve Div 2 D?

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

Problem Div1 B was Info1Cup 2017 XORsum

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

    Its a little difficult to understand from the editorial given. Can you simplify the approach to solve this question?

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

How to solve Div2B

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

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it +36 Vote: I do not like it

Hate SpeedForces.

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

How to solve div2 B??

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

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

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

    i already told you swistakk as the age passes contests become much and much better as they were in your young days.

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

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

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

    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.

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

    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

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve div2 D?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is testcase 6 in div2C?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have no idea for div2 D!!!

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    freq array off all pair can be calculated in o(nlogn) time using FFT but I receive Memory limit.

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

    sorry. it can be calculated in o(10^7log(10^7)) time.

    → Reply
»
4 years ago, # |
  Vote: I like it +51 Vote: I do not like it

Before the contest: I want to solve Div1 D!

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

→ Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

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

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

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

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +74 Vote: I do not like 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.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it +8 Vote: I do not like it

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

    → Reply
»
4 years ago, # |
  Vote: I like it -167 Vote: I do not like it

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;

}

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

    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

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

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

      → Reply
»
4 years ago, # |
  Vote: I like it +22 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +24 Vote: I do not like it

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

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

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!

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

    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.

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

      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.

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

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

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

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it +23 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +21 Vote: I do not like it

    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.

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

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

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

    I used multiset, set and segment tree at the same time (for different purposes), 1247 ms on pretests

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

      Seems like my implementation has a bad constant. My solution runs in 3sec on my machine (which is a bit faster than CF), and with fastset it runs in 1sec.

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

    n log n, TLE systests, byebye

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

How to solve div1C?

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

Good Balance!

→ Reply
»
4 years ago, # |
  Vote: I like it +34 Vote: I do not like it

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

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

    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.

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

Amazing problems, thanks for them!

→ Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

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

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

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

I Hate SpeedForces :(

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

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.

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

    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.

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

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

link

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

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

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

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

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

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it -30 Vote: I do not like it

        A rule that can be broken without repercussions is useless.

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

    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?

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

      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.

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

        Then how to use iostream "right"? I've done nothing but to replace std::cin>>a[i] with scanf("%lld",&a[i]) and it passed.

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

          ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);.

          And '\n' instead of endl.

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

      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.

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

After long time i will reach on specialist.

Thank you codeforces .

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

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

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

Pretest is weak?

→ Reply
»
4 years ago, # |
  Vote: I like it +49 Vote: I do not like it

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

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

    Why does it matter so much? You're printing one integer.

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

      I thought so too during the contest. But it has multiple test cases.

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

    Even if one uses the standard ordered map for storing vectors, no problem. Just the "cout" is the problem.

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

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

→ Reply
»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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

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

    No penalties for solutions failed on (pre)test 1

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

      I know about NO PENALTIES. But what about getting minus?

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

        You mean something like "-1" "-2"("tried" counter)?

        Failing on (pre)test 1 won't be counted in the "tried" counter

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

          Forget about it. I already got minus in rating.

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

            You mean rating change?I didn't understand it :( sorry for inconvenience

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

Being a master was truly magnificent experience.

Au revoir!

→ Reply
»
4 years ago, # |
  Vote: I like it +24 Vote: I do not like it

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？

→ Reply
»
4 years ago, # |
← Rev. 5   Vote: I like it -35 Vote: I do not like it

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

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

    Your solution works quite close to time limit. There are always some fluctuations in program working time, so it's just a bad luck that your submission got TL on system tests.

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

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

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

    The execution time may be different in runs.

    If your code consumed almost 1000ms(e.g:996ms) in the pretests, it's probably to fail in the main tests.

    → Reply
»
4 years ago, # |
  Vote: I like it +150 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -67 Vote: I do not like it

    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.

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

      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.

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

      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.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it -43 Vote: I do not like it

        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.

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

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

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it -74 Vote: I do not like it

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

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

              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.

              → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
              ← Rev. 3   Vote: I like it +26 Vote: I do not like it

              Ignore: in prev version Russian colypasted joke

              → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -23 Vote: I do not like it

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

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

I guess B and C got swapped :(

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

To solve this problem,I use gets lol
72676564

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

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

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

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

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

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

→ Reply
»
4 years ago, # |
  Vote: I like it -14 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

zhouyuyang congratulations for rank 1.

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

Wish Codeforces could be better and better.

→ Reply