cdkrot's blog

Codeforces Round #545 (Div.1, Div.2, based on Moscow Open Olympiad in Informatics)
By cdkrot, 6 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)

Open Olympiad consists of the most interesting and hard problems that are proposed my a wide community of authors, so we decided to conduct a Codeforces regular round based on it, which will happen Mar/08/2019 12:05 (Moscow time) and will be based on both days of the Olympiad. Each division will have 6 problems and 2:30 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 vintage_Vlad_Makeev, isaf27, Flyrise, cdkrot, GlebsHP, ch_egor, Zlobober, qoo2p5, grphil, achulkov2, Schemtschik, akvasha, mingaleg, V--o_o--V, wrg0ababd, guided by ch_egor, cdkrot, GlebsHP, Zlobober and Helen Andreeva.

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

Good luck everybody!

UPD: Congratulations to the winners!

Div.1

  1. sunset
  2. Petr
  3. Radewoosh
  4. ko_osaga
  5. orbitingflea

Div.2

  1. appplese
  2. al3xstr33t
  3. Charlene_Hao
  4. ytxytx
  5. QDEZ604

The editorial will appear soon

UPD: The editorial

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

Comments Comments (195)
| Write comment?
»
6 years ago, # |
← Rev. 2   Vote: I like it +24 Vote: I do not like it

You mean round #545?

Edit: got fixed.

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

i wish this contest will be my chance to become candidate master

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

    I wish this comment is your chance to get out of the negative :p Good luck bro <3

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

Just be careful with any streams.

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

it is like asking thieves not to steal.

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

Hopefully this contest will not end up with "Let's solve problem just for fun"

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

is it rated?

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

Another potential unrated round :)

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

Hope not two unrated contest happening in a week..

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

Looking forward to solving a problem by kun :D

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

We should believe in Codeforces that they won't make mistakes any more. (ง •_•)ง

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

Not a suitable contest timing for Indians. :(

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

Why everyone should know that this contest is based on Moscow Open Olympiad in Informatics? I think it is better to hold information like this in secret or announce it after the end if the cheating is possible.

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

    Well you need to be able to tell people that know the Moscow Open Olympiad problems not to take this contest. There's no easy way to tell people this without outright saying that the contest shares at least some problems.

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

      I believe there are better ways than make it public. Even if you know the solution but the statement is changed it will take some time to realize it. But there won't be enough time (and purpose) to spread it across the community.

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

Best contest time for Japanese! Yeah!!!

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

╮(╯_╰)╭, just have fun~

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

When will the editorial be published?

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

Meanwhile in my timezone

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

Scoring distribution?

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

getting "you have already submitted this code" for all submission I'm making .-.

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

CF rounds quality is coming down everyday and we see more and more(unbalanced,unrated,unusual,...) rounds...

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

ewww moscow

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

Can't solve last 2, but all problems were interesting. :)

(Also need to go back to sleep now).

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

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

A few unbalanced round. (maybe not a few).

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

Is it only me or every one that thought this contest was unbalanced?

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

Kudo for the pretests :D
Btw, anyone have any ideas of pretest 16 of Div1C? :D

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

    I fixed RE16 with #pragma comment(linker, ”/STACK:36777216“) (using MS C++17)

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

      Woah, that doesn't work for me. Must be some other segmentation fault I haven't figured out :<
      Still, thanks, I didn't expect this one anyway ;)

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

Saw a bug in my A after I locked in. Feelsbadman

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

How do you do Div. 2 B? :O

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

    Is it just some nasty casework?

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

      No just find all four types and use two for loops such that you check all the possibilities, by using the given conditions and two FOR loops you'll be able to check all the possibilities if nothing satisfies, print -1.

      The four types are

      1. a[i]=0 && c[i]=0
      2. a[i]=1 && c[i]=0
      3. a[i]=0 && c[i]=1
      4. a[i]=1 && c[i]=1

      Now use two FOR loops to check the number of type 2 people and number of type 3 people in group 1, then you can figure out type 4 needed.

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

        but i can't solve this problem by this way,could you explain it more clearly? Thanks

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

I tried to hack one of the solution, I uploaded script (which generates testCase) several times, but all the time, there was Generator compilation error. Could you teach me how to hack using generator scripts?

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

    You must strictly follow the format of the input data up to spaces and line breaks; For example, in problem Div2 A script generator would be

    #include <iostream>
using namespace std;

int main(){
    int n = 100000;
    cout << n << endl;
    cout << 1 << " ";
    for (int i = 1; i < n; i++){
        cout << " " << 1;
    }
    cout << endl;
    return 0;
}

    make sure that you have cout << endl; in the end of the code and spaces in right place; here is a generator that will not compile (because of unnecessary spaces int the end of line)

    for (int i = 0; i < n; i++){
        cout << 1 << " ";
    }
    → Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve Div2. B?

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

    I solved (pretest passed) it this way:

    Let a, b, c, d be number of index with (0, 0), (0, 1), (1, 0), (1, 1) respectively. If you select A, B, C, D of the types in the order, then these should hold: A + B + C + D = N / 2 and C + D = b - B + d - D. Using the second one you can say that A - D = N / 2 - b - d.
    Now, you can brute force on A, D and whenever you find one brute force on B, C.

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

      How would you account for the complexity of the solution ?

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

        O(N2) with very low constant. I think it can be optimized to O(N) if you find A, B, C, D mathematically instead of brute-forcing.

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

That moment when you solve C and D but cant solve B :(

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

Was Div2 F(Div 1D) only simulation of tortoise and hare algorithm?

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

It took me 30 minutes to realize that in C the tour can last more than one week. Granted, if that wasn't the case, the problem would be equivalent to Hamiltonian path, and in the second sample the path lasts 6 days, but I still think that the problem was unclear. Nowhere in the statement does it say that the tour can last more than one week :/

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

    I had the same problem with not understanding it at once.

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

    Exactly, I was scratching my head for long time as well figuring out why are they asking me variation about k-path problem which I know is pretty hard to solve. Need to look up explanation of sample as well.

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

Thanks for an amazing contest!

Solution for D:

Move (0, 1) and (0) (2 operations) while their positions don't coincide. If we have done k such operations we must have 2k ≡ k(mods), . Now start moving all the pieces together. After t moves they all will be at the desired point: as 2k + t ≡ t(mods), pieces 0, 1 will get there, while 2, 3, ..., 9 will obviously get there for the first time.

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

I solved A, and then I just read problem B -> C -> D -> B -> C... again and again...

CF 545 made me iterator function...

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

B on div2, is hardest B question I ever see in codeforces . what's the goal of designing such question ?

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

How to find t in div1D? (if I not mistaken we can find c due to fixed players on positions with index 2^i, before first time we meet fixed player)

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

    Hint: You don't need to find it to solve the problem.

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

      Hmm... I thought about this but I have no clue, how to find exact point in cycle?

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

Fun fact: Problem D is used as a subroutine in algorithm for subset sum in O(20.86n) time and polyspace.

I have seen this on a lecture a few days ago, which explains why I was so fast in solving this problem :P.

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

    also a subroutine in Pollard's Rho algorithm.

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

In div1C was O(N*D) the correct time complexity of the solution? I had TLE 11 witk making a graph with nodes associated with pairs of cities and days ( n*d nodes, m*d edges) What were other aproaches?

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

    Exactly :|... Got this solution pretty fast and sank for a long time in microoptimizing it and didn't make it pass 11th test :|...

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

    For any strongly connected graph there exists a number g such that, for every vertex v and sufficiently large k there exists a cycle of length gk which passes vertex v. Intuitively you can think about the GCD of all cycles. It is not, but something similar.

    If you decompose a graph into SCCs, you can calculate such g in linear time. Now you can do a DP with a state as (vertex, length mod d), and transited for every edges and SCCs. This is O((n + m)d), but the DP routine is just array scanning, so my non-optimized code runs in 0.3s.

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

      thank you

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

      Good solution! I tried to solve it in this way but failed in the contest.

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

      Good solution! I tried to solve it in a stupid way but failed in the contest.

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

        You are a Pinkie Pie too? And you are repeating my words!

        Didn't Twilight return all my clones back to the Mirror Pool, did she?

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

      To compute that value g for every connected component you have D*(number of nodes of CC)? Can you do better than this?

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

        For all cycles created by back edge take its length. For all two disjoint path created by forward edge take the difference of length of two paths. g is a gcd of them. So it is simple dfs.

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

Even additional half an hour didn't help me to solve B and C. I guess they were hard not only for me.

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

Div1 AB may be a little bit too easy.But I just have no idea about Div1C...

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

When I see a problem from school olympiad in which you have to optimize constant for O(dn) solution...

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

    Do you have an idea what caused "Runtime error on pretest 16" ?

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

      Lmao, no clues at all. I just tried changing vectors to arrays

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

        Maybe its because of recursion and too much memory in stack (in my case)

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

          It may be, but it should have been the case in the solution which got TL 18 as well.

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

          And it seems to be some compiler related stuff because same submission get AC on MS C++ -_-'

          Link

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

    51016217, 51038646. same code, same compiler.

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

Am I the only one that thought that D was easier than A, B, and C :)

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

    WA on test 70 bro, FeelsBadMan

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

    Yeah, you basically just have to know a O(n) string matching algorithm. At least that's the way I did it.

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

      can you explain which algorithm u have applied!!

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

        I used Z-algorithm to find the longest suffix is t which is also a prefix. I learned it from here, page 247.

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

What is solution for C div 1 ?

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

    Build a graph where the vertices are (u, t) where u is the node and t is the time modulo d. Then, connect (u, t) to (v, (t + 1)modd) for all edges . Compress the SCCs of this graph and do DP on DAG. The key fact is that if there is a path from (u, j) to (u, j'), then there is also a path from (u, j') to (u, j) (by going through the cycle more times), so you won't overcount cities.

    I had to do a lot of optimizations to get pass the pretests though, maybe there's a simpler method........

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

      Do I also have to do DP in the SCC?

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

        Nope, in the new graph you can take all the vertices in an SCC if you ever reached it.

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

      "I had to do a lot of optimizations to get pass the pretests though, maybe there's a simpler method........" — actually you don't need simpler method, you need harder one :P. At least that's what my friends did in order to omit recursion on 5mlns vertices. It seems you can divide just original graph into SCCs and then do some weird shit with remainders like counting GCDs of all cycles within every SCC etc. Overall complexity is O(nd) anyway, but recursive part is only O(n) and that's supposedly a profit xd.

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

      I tried some optimizations to PP but I got FST:( I think both the time limit and the memory limit are too tight.

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

that contest was tough one..

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

can anybody help me in knowing why my solution to div2 d is giving wrong answer on pretest 6. sol link : https://mirror.codeforces.com/contest/1138/submission/51026146 Thanks in advance

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

    I also kept getting WA test 6 but then I realized that there is an edge case. Consider the input:

    00001111

    101

    With my original code it would have outputted: 10110100 and it would have only contained 2 instances of t.

    But you can actually get more than 2 instances of t because the strings can overlap, so the optimal result would be: 10101010 which is actually 3 instances of t.

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

Div1 D is basically Floyd's cycle finding algorithm

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

    Oh, I knew this algorithm. Too bad I wasted the whole contest on C...

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

      I also know the algorithm but as i suck at interactive problem, i didn't even bother reading it

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

    That's a bold statement. I knew this algo and couldn't solve this problem for more than half an hour.

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

      Floyd's algorithm is the first thing that popped up in my mind seeing the problem. I wonder if anyone solved it with a different approach.

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

      That's weird, I see no difference between this algo and problem D xd.

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

        My bad. I knew the idea about moving two pointers with speeds 1 and 2, usually that's enough for all things like Pollard-rho.

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

wanted just 2 or 3 secs more. Coded the correct solution for B, going to submit and contest over.

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

Please judge my first prepassed solution on Div2D! The difference between my first solution and second solution is just number of comparisons of hash value of intervals.. I got TLE on second :(

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

very nice contest ^_^ thank you all

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

I got WA on test 70 for D :( I knew it was too good to be true.

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

Why it always have to be so long time after a contest to wait to submit my solution

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

how to solve div2 D?

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

    Maybe : Find first position i in string t such that t[i...n] is equal to some prefix of t i.e equal to t[1...n-i+1]. Then build new substring from that position keeping count of zeroes and ones left. Hashing can be applied.

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

    you can solve it very easily using some help of Z_function algorithm which tells you which idx can be prefix of the same string example:

    string s="11000110"

    you can see that at idx 5 will have a prefix to the main string which is 110 (that's what the z_function get) so from here you can deduce that after you made up the first string just concatenate the remaining string starts from idx 3. i hope you understand what i meant to say.

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

I tried to hack one of the solution, I uploaded script (which generates testCase) several times, but all the time, there was Generator compilation error. Could you teach me how to hack using generator scripts?

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

What's with upsolving?

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

Hi guys, I hope you enjoyed round!

In case you wonder why upsolving is not available yet -- it's intended, since the onsite events haven't finished yet. It will be open in roughly 2-3 hours.

About editorials, we will be happy to publish them after we finish with the onsite as well.

Thanks!

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

My Solution For Problem E can be hacked by n = 1, m = 3e5. Then we preform 299998 times 3 1000000000 1000000000, and then we perform 2 999999998 (10^9 — 2) and then go 2 1. In this way my solution (and many of solutions that get passed) will get a number exceeding the upper bound of the type long long. I think the test is too weak.

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

    This is forbidden, isn't it?

    Also it's guaranteed that the integers Ai will not grow too high. Formally, it's guaranteed that if we sum the largest addition over all events of the 3-rd type (that is, b + (n - 1)·s, where n is the number of cars at that moment) then the acquired sum would be at most 1018.

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

      Sorry, maybe I don't think my data is forbidden. For example, in your code.
      ~~~~~ pts.push_back({r, -overall_b — overall_s * (r — l)}); ~~~~~ "-overall_b — overall_s * (r — l)" this sentence will lead to a exceeding of long long.( And This is not the real value! It's just a tag.) And I have carefully checked that my data satisfies the conditon mentioned in the statement.
      ^_^

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

Is here any other guy's solution for 2c/1a is O(n^2*log(n)) and got tle? I used treap and the time limit seems too tight for me,LOL My brain is quite strange :\

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

What is test 70 on Div2D/Div1B?

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

    Same problem :(

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

    I think it counter some common hash mod, example 10^9+7

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

    Well I used KMP but also failed on this test 51057303. Anybody has an idea?

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

      I think there's a mistake with your program. For example

      1001100001111110001000101100111100101001
01001

      Your Answer is

      0100101001010010100101001010010011111111

      But this is not the optimal solution. （During the contest I want to hack it but it's too hard to construct a set of data... XD

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

        I found a mistake in my KMP and fixed it. Thx!!

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

-100 rating hmm nice number that made forget how terrible I did

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

The contest has ended and it shows Final standings but I am unable to make any submissions. Is it a bug or am I missing something here? It says you need to be registered for the contest. Edit1: I believe I am not the only one who might have missed kun's comment. For those who have gone ahead to downvote, it would be helpful if you could mention the reason for the same.

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

    From kun's comment above

    "In case you wonder why upsolving is not available yet -- it's intended, since the onsite events haven't finished yet. It will be open in roughly 2-3 hours.

    About editorials, we will be happy to publish them after we finish with the onsite as well."

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

when it will be available to submit a solution?!!

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

    It will probably take a couple more hours since the onsite event hasn't ended yet as kun has mentioned above.

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

Tricky Contest##!!##

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

How can I submit my code after the contest? It says I am not registered for the contest :(

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

I missed the contest. Is there any way to participate virtually? I see no options there.

Edit : Thanks. Got it.

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

meme

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

Hello, What is the souliton of div1 C, div2 E?

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

Does anybody know how to get/copy a test case that is finished with the ellipsis "..."?

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

    You really want to debug your code on a test case that is finished with the ellipsis "..."?

    I think there is now way now.. but you can go through other test cases from a AC solution and get a smaller test case that gives WA for you

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

div2b can anyone plz tell me what's wrong with my 51023192 . the basic idea is:

for 1st performance i iterate over all possible clowns (clowns+both_skilled).all the other both_skilled goes to 2nd performance. then i take some acro in the 2nd to make it equal . then rest of the acro goes in 1st performance. and rest of the clowns go the 2nd. and fill others with no skill actors. if all verifies i take that number of clown and print

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

How to solve div2D / div1B?

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

Ahhhh...
Finally that's my best rating change (+318) ever...
Here is my personal log on the contest:

  • 0min Start. Don't know whether to participate.
  • 15 mins. Read C,D,E. Thinking on C and fail.
  • 25 mins. Come up with the idea of E. Decide to participate and start to write B.
  • 34 mins. PP on B, reading A.
  • 51 mins. PP on A, start doing E.
  • When doing E, I basically debugged for around 20 mins just because I made the order between the slope and the intercept wrong when I read the b and s in the task (i.e. read in the order s b instead of b s).
  • 98 mins. PP on E, trying to do C and D.
  • The ten friends in D is really misleading. Finally when I figured out that 3 of them would be enough, it is already 145 mins after the start. In a rush I finished the last piece of code (and made it wrong for the first time) and submitted on 148 min. PP.

Before the contest I wanted to get around +200 to get myself a yellow, but the result is really good for me. Thank you all for the fun and exciting round!

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

How to solve D1C/D2E?

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

What is test 73 for div1C？

It looks like many people failed on it (including me)

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

cdkrot, I found some accepted codes of F is quiet similar, why no skip? 51026411 51023578 51025400 I don’t believe that there is such a coincidence.

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

Why I get RE on test 8 for div2 problem B?? https://mirror.codeforces.com/contest/1138/submission/51062872

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

cdkrot MikeMirzayanov KAN

https://mirror.codeforces.com/contest/1138/submission/51062541

https://mirror.codeforces.com/contest/1138/submission/51021650

are exactly the same for the problem 1138C, yet I got a TLE during the contest.

Any chances for getting it rejudged?

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

    If you get AC during a contest and TLE in upsolving with the same code, do you want a rejudge too?

    I think CF already runs a solution a second time if it gets TLE.

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

      Never happened with me before, just asking :p

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

so, where is the editorial? it's about two o'clock(UTC+8).

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

0rating

Now that's a first...

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

I got Accepted in 1138B - Circus in Div. 2 with Brute force on a, b, c, d (which are the numbers of different types of artists).

I just want to know how to prove the time complexity of this algorithm?

My submission is 51069702.

Thanks for everyone. :)

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

    The if condition in your second nested for loop is a bit unintuitive, but apparently squeezing the search space considerably so that you solution passes. Also you don't need the 4th for loop (over cnt[2]), you can simply assign the value of c using n, a, b and d

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

      I have been understood your reply.

      So I can easily prove that the time complexity of my solution is O(n2).

      Thank you, sincerely. :)

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

My O((N + M) * d) solution for Div2 E. / Div1 C. times out on test case 18. Could anyone tell me what is causing this? https://mirror.codeforces.com/contest/1137/submission/51080307

Edit: TLE resolved by making the DP iterative.

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

In question 1.C I got RE The main problem is

void bfs(int x,int y){
	if(vi[x][y])return; vi[x][y]=1;
	V.push_back(mp(x,y));
	for(int l=e1.son[x];l;l=e1.nextt[l])if(tong[e1.ed[l]]==tong[x])bfs(e1.ed[l],(y+1)%d);
}
// bfs is actually dfs

If you change the vector to an array, you can get AC

In fact, the dfs depth of the program can reach 5000000

Why is that?

Specific can see

51145858 51016401

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

-

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

ohhh thats so cute of you to congratulate me, you didn't have to, <:)

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

    I don't think it is a cute act to report cheating. I think everyone wants the game to be fair, so I don't think it is unnecessary to report cheating

    → Reply