top34051's blog

By top34051, 8 months ago, In English,

Hey Codeforces!

We’re thrilled to invite you guys to Codeforces Round #542, which is going to take place on Sunday, February 24, 2019, at 18:35 MSK. There will be a separate round for each division, and they will be rated!

Problems were prepared by MikeMirzayanov, zoomswk and me. As the round authors, we would like to thank ksun48, isaf27, tuna_salad, and Um_nik for testing the problems; 300iq and KAN for their help and advice in contest preparation; and the invisible MikeMirzayanov for the incredible Codeforces and Polygon platforms.

Each division will be given 6 tasks and 2 hours to solve them. As per the Codeforces tradition, scoring distributions will be revealed shortly before the round.

We wish you the greenest verdicts and hope that you’ll enjoy the tasks.

This round is in honor of Alex Lopashev who has supported Codeforces on its anniversary. Some words from MikeMirzayanov:

Alex Lopashev studied at Programming Competitions Training Center (in Saratov U) headed by me. I was really happy (and even proud!) to see his contribution on the 8th anniversary of Codeforces. I am sure that a large number of young people got a lot from our community, even if they did not achieve high results in competitions. It's great that there are those who remember and appreciate it. Thank you, Alex!

Good luck!

UPD1: Shortly after the contest, we'll be on the community Discord server to discuss the tasks.

UPD2: The score distributions are here!

Div2: 500 – 1000 – 1500 – (1000 – 1000) – 2500 – 3000

Div1: 500 – 1000 – 1500 – 2000 – 2500 – 2500

Note that task D of the second division will have subtasks.

UPD3: Last minute corrections T-T

Each division will be given 5 tasks. Also, task A of the first division will have subtasks like the way task D of the second division round do.

Div2: 500 – 1000 – 1500 – (1000 – 1000) – 2500

Div1: (250 – 250) – 1000 – 1500 – 2250 – 2250

UPD4: The Editorial is ready!

Congratulations to the winners!

Division 2

  1. Markadiusz
  2. lisifu
  3. TAISA_
  4. MagicPotato
  5. OnlyGetAC

Division 1

  1. mnbvmar
  2. LHiC
  3. Errichto
  4. V--gLaSsH0ldEr593--V
  5. V--o_o--V
 
 
 
 
  • Vote: I like it
  • +248
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it +19 Vote: I do not like it

Auto comment: topic has been updated by top34051 (previous revision, new revision, compare).

»
8 months ago, # |
Rev. 2   Vote: I like it +23 Vote: I do not like it

Wish everybody high rating

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

    Wish everybody high rating

    But Codeforces rating is a zero-sum game so you're wishing for impossible :/

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

      I was just editing randomly beacause my previous comment has already been answered by the author editing his post :P But good point

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +111 Vote: I do not like it

      **Codeforces rating is a negative-sum game.

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it +23 Vote: I do not like it

        But every new user has 1500 rating. So in some way it's a positive-sum game??

        Actually Codeforces Contest is a negative-sum game. :(

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        N no no ...

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      Don't know positive or negative nim but definitely a fun game :)

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Eagerly waiting

»
8 months ago, # |
  Vote: I like it -28 Vote: I do not like it

how many questions do red coders solve every day???

»
8 months ago, # |
  Vote: I like it +27 Vote: I do not like it

You have a mistake. You write Um_Nik, but correct variant is Um_nik))

»
8 months ago, # |
Rev. 6   Vote: I like it -24 Vote: I do not like it

I wish today's DIV 2 users wil play DIV 1 In the next Codeforces Rounds.

»
8 months ago, # |
  Vote: I like it -12 Vote: I do not like it

hello codeforces my one suggestion if you want to implement ?? instead of 2 hrs please increase the at least 30 minutes for every round on codeforces. because i think if participants can solve more questions their confidence level will increase. if you have fixed 2 hrs then give me some idea based on what you have fixed 2 hrs for most of the contests. Thanks in advance

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

    Well, participants can solve more problems before/after contest. In that case, their confidence level definitely will increase :)

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    Suppose your request is granted. What's to stop you from asking for an extra 30 minutes again, with the same logic? A line has to be drawn somewhere, and 2 hrs for 5/6 problems is where they decided to draw it.

»
8 months ago, # |
  Vote: I like it +9 Vote: I do not like it

thank mr. alex

»
8 months ago, # |
Rev. 2   Vote: I like it -6 Vote: I do not like it

Happy Coding and high rating.

Hoped that everybody( in both div.1 && div.2 ) has good feeling

»
8 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Back to Back contests. Feels Great !

»
8 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Is the div2 of this round available for ratings below 2100? It seems that I cannot register div2 with a rating between 1900 and 2100.

update: I asked this question since last few div2 rounds were available for users whose rating < 2100.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    You're in Div1. <1900's are Div2.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    If the contests is div.1+div.2,you can only go to div.1 If the contests is “rated for div.2”,you are rated. (“you” means the coder who has rating between 1900 and 2100) Sorry for my poor English.

»
8 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I want to say some words about some computer languages. When you use Cpython except classical Python your programm works faster and the syntax of it is not very difficult as the syntax of C++. I commonly use Python because you can not meet Cpython on many olimpiads, but... it is the best computer language in the world (in my opinion). And what do you think about Cpython and other languages?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    Python is slower than my grandma :D

  • »
    »
    8 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Питон лучший язык. Победа на МОШе только на нём.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well... Python in something convenient, but sometimes if you miss a space, the program breaks...

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how many problems are shared between the divisions ?

»
8 months ago, # |
  Vote: I like it +27 Vote: I do not like it

Note that task D of the second division will have subtasks.
There will be 4 shared problems!

So that problem Div2-D is shared, but Div.1 players will only solve its second subtask?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    That's right!

    • »
      »
      »
      8 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Sorry, we just made a sudden change. Now, the Div.1 players will have to solve the first subtask as well.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

"Note that task D of the second division will have subtasks."

If one makes two submissions , first to first subtask and second to whole problem , will there be penalty -50 for second submission ?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    You can consider each subtask as a separate problem, so score calculation will be independent. However, these two "problems" will have the same content except for the constraints.

»
8 months ago, # |
  Vote: I like it +5 Vote: I do not like it

i hope a good contest whithout delay

»
8 months ago, # |
  Vote: I like it +5 Vote: I do not like it

also whith good samples

»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Just curious, what about the hacks for div2D? Will it be possible to lock the first subtask only?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hacks for the first subtask will be disabled!

»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

What does '(1000 — 1000)' mean ? refer to: "Div2: 500 – 1000 – 1500 – (1000 – 1000) – 2500 – 3000"

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    There will be two subtasks on problem D, and their scores are both 1000.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    It means that Div-2 D will have 2 subtasks and as said above hacks for subtask 1 will be disabled. Just one more question as the time passes points for both the subtasks will decrease or what will happen?

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

So In total there will be 7 problems for div2 people. :)

»
8 months ago, # |
  Vote: I like it -13 Vote: I do not like it

I want high rating.

»
8 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

How to solve problem C [Connect]

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

    You can use either a DSU or a DFS to find the connected components. Then a brute force search would suffice.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks, Bro. Your comment means that I should learn more in CP. DSU and DFS and so on... Thanks for organizers thanks for All participants..

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      You just need to do a DFS to find components of the source and destination. Dsu seems like an overkill

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Run a flood fill to assign each land cell to a component. If the start and end position are in the same component, output 0. Else, try building a tunnel between every pair of cells in the components of the start and end positions and take the minimum answer over these.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Use dfs or bfs to find all spots reachable from the start and end. Then, find the cheapest tunnel you can make of all 50^4 possible tunnels that is has 1 side reachable from start, and 1 side reachable from end.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What I did, was to do BFS traversal, but instead of building a graph, I was using the 2D table that was given in the input. From there, you could either move in the 4 directions, such that you move to (i+1, j), (i-1, j), (i, j+1), or (i, j-1), without adding anything to the cost, or you could go to any other place which has land, and the cost would be as in the statement. In order to make sure that you only place a tunnel once, you can only build a tunnel when the previous cost was 0. Have a look at my implementation 50455831

  • »
    »
    8 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    If (r2, c2) can be reached from (r1, c1) the answer is 0.

    Otherwise, put all land cells that can be reached from (r1, c1) (including it) in a vector, say v1. Also, define another vector, say v2, for all land cells that can be reached from (r2, c2).

    Run an O(sz2) algorithm to calculate the minimum cost of building a tunnel between two cells, one from v1 and one from v2, where sz here represents the maximum size of v1 and v2.

    Time complexity: O(sz2) = O((n2)2) = O(n4).

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Build directed, weighted graph of 2*n^2 nodes and run dijkstra.

»
8 months ago, # |
  Vote: I like it +63 Vote: I do not like it

Really cool contest, great problems!

»
8 months ago, # |
  Vote: I like it +7 Vote: I do not like it

how to solve D??

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

    I'm not sure if my solution is correct, but it passed pretests: 50458735

    I kept the shortest distance from A to B in a circle for every A(based on all M queries), we can call it dist[A]. Then I started with every i in [1;n] and went a full circle, while updating the answer with answer = max(answer, (q[current] - 1) * n + dist[current] + cnt), where q[A] is the number of candies on station A and cnt is the number of steps we already made, starting from i.

    This solution should take O(N2) time.

    UPD: It passed system tests

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Pretest 16 for Div 2 D2?

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What's with the bounds in Div1C? I had to replace maps with vectors, sorting and binary search, and then had to remove the binary search part to pass TL, and now I'm really close to the memory limit

»
8 months ago, # |
  Vote: I like it +10 Vote: I do not like it

How to solve Div.1C? I noticed that overcount only happens when the two substrings are exactly the same. I used interval dynamic programming and hash_map to check out for each substring whether it has appeared before. The time complexity is O(m2), however, the actual running time of my code is rather slow on maximum test, due to the large constant of hash and hash_map. Is there any other solution with better complexity/constant factor? Is it intended by the author that one shouldn't use something like hash_map in this problem?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    You can check it by trie

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      Just implemented one. For the same random test case: trie: 0.1s 2 modulo hash+unordered_map: 5s XD

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

    I did this, but instead of unordered_map, I first calculated the hashes of all intervals, then sorted pairs of the hashes, their startpoints and endpoints in the string. Then, I removed duplicate hashes, keeping only the occurence with earliest startpoint. Then, for every endpoint, I found the largest startpoint remaining in the vector of pairs, and put that startpoint into an array. Then when calculating the values, I started adding the DP values at the startpoint. What a mess, but it seems to be fast enough :/

    Code: 50459140

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It's a nice way, but could we always do it while using an unordered_map?

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah, but unordered_map has too slow constants to be used here :(

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I guess (just guess) that after each modification we could find largest suffix that appeared in this string before with Suffix Array or smth else.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Yes that would work. Suffix array, then just exclude that max LCP with the suffixes so far.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      z-function works here

»
8 months ago, # |
Rev. 2   Vote: I like it +47 Vote: I do not like it

When one minute before the end of the contest you learn that your definition of a "substring" is wrong.

»
8 months ago, # |
  Vote: I like it +112 Vote: I do not like it

Nice constraints in div1 D.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +60 Vote: I do not like it

    I can make a wild guess that you once again submitted brute force — without even checking your code.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      I actually checked it in custom invocation =) Btw, 1.5s out of 3s.

»
8 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Did anyone pass div1C with hashes? Using a big modulo and unordered maps TLEd while using smaller modulo created collisions, even with 2 different moduli

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Am I right if say in Div2E you always can create array like -1 -1 -1 .... -1 x? With k = 10^9 worked.

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

    What is x here?

    Yeah so Alice's algorithm will always return x, and the correct answer will be (x - (n - 1))n. So we want to find x, n such that (x - (n - 1))n - x = k, which is the same as (n - 1)(x - n) = k, which won't exist if k is a big prime, because we would have to have n = 2, x = k + 2.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Maybe not. k=n(a prime)*a big prime. If there is a number like prime1*prime2(>1e6) minus the number of your -1(maybe still a prime=that big prime) but you print -1

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      like”-1 -1 -1 ……… x x x x x x x x x x x x x……”

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        The same. 100000001 doesn't work

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    100000001 doesn't work

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think -1 a2, a3, ..., an might work, where n is (k + 2) / 10^6 + 2 and a2 + a3 +... + an = k + n; Then figuring out a2, a3,... an is easy, you just divide the total sum by the number of terms and that is one term, then remove that term from the sum and do the same for the next and so on.

    • »
      »
      »
      8 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Never mind you have to be a little more strict with n, otherwise with large numbers the terms might go a little over 10^6. If you choose n to be (k + 2)/10^6 + 990 then it will be fine.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

A1 and A2 are too hard.X( Δ=-100 X(

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

How to solve B? is it greedy??

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You can keep track of the position of the 2 people, and choose where to take them next greedily, such that the amount added to the answer (greedily)

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I had another greedy, where I simulated the first person and always took the leftmost option. No idea why, but it's passing systests.

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Because it is correct and you can prove that by taking all the cases using two states.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I used DP[n x 2], on each step storing answer for "First takes from P[i][0] & Second takes P[i][1]" and interchanged. 50442447.

    But also interested, if there is any greedy solution.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      If you're interested, you can take a look at my submission here. 50436246

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks! I could not even imagine, that it was so simple :)

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think dp is good idea than greedy. if i submit code using greedy, I wrong this case 1 3 2 1 3 2 4 4

»
8 months ago, # |
  Vote: I like it +27 Vote: I do not like it

Standings are a bit weird right now. It tells me I got AC on A but shows -1 in the standings (for everyone, really)

»
8 months ago, # |
  Vote: I like it +95 Vote: I do not like it

Today we can see a new legendary grandmaster Errichto

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Div2 B? I used greedy approach and sorted the houses based on the tier of cake they are selling and their index value. After this every time I assigned 1st house to Sasha and 2nd house(i.e one selling same tier cake)to Dima. I failed on pretest 10.

  • »
    »
    8 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Change int to long long

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    try to change your int to long long int. Well at least this was my mistake when I was getting WA on test 10.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I also failed in pretest 10 because of overflow. I'm not sure if that's your issue, but I change my variable from an int to a long and it worked.

»
8 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

How to Solve Div 2 C ?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Just by know, what are the positions where we can reach from the first position and second position. and then check which two cells give minimum distance.

  • »
    »
    8 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Run a flood fill and "color" in the pieces of land in the same region. Then you can brute force and check for the minimum distance between every piece of land in the same region as the start and every piece of land in the same region as the end.

  • »
    »
    8 months ago, # ^ |
    Rev. 5   Vote: I like it +3 Vote: I do not like it

    if r1,c1 and r2, c2 in the same component print 0 else

    for x in fields_in_first_component
      for y in fields_second_component:
        an = min(distance(y, x), an);
    

    components can be found using dfs or something like that

»
8 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

What is going on with the standings?!

Edit: Fixed

»
8 months ago, # |
  Vote: I like it +32 Vote: I do not like it

I think, it was a very nice experiment with subtasks.

»
8 months ago, # |
Rev. 3   Vote: I like it -7 Vote: I do not like it

Can anyone tell me what the bug in this 50457135.

edit: the Error was fixed its stupid logical error thanks for down vote.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For BFS, your vis vector should update when a point gets pushed onto the queue, not when it gets popped from the queue. Otherwise the same point will get pushed multiple times.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thank you, I forget that, in contest I'am doubt between copy them from my library or code it again but I'm chose wrong way hhhh;

      • »
        »
        »
        »
        8 months ago, # ^ |
        Rev. 3   Vote: I like it +10 Vote: I do not like it

        Others may disagree, but I would say BFS/DFS are fundamental enough that you should not have them in your library, since so many algorithms are modifications of them :)

        Errors like this will come up all the time; just a matter of practice.

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          note: I Am always chose the first choice, but I'm left the training recently so...

»
8 months ago, # |
  Vote: I like it -23 Vote: I do not like it

C is actually a bad problem .. 0 thinking it was just coding :/

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

    and all implementation tasks is a bad tasks ??

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    Implementation is a skill. ¯\_(ツ)_/¯

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it -11 Vote: I do not like it

      not really xD maybe I should try solving D problems I got bored from A B C

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

        What's the point of knowing how to solve a difficult problem if you can't implement it cleanly, efficiently and correctly?

        A competitive programmer needs to be have good implementation skills along with having the required knowledge to solve problems.

        Not every problem needs to have a neat idea. It's nice to sometimes only need to think about how to implement what they tell you to.

        Lastly, just because you don't like a problem doesn't make it bad.

»
8 months ago, # |
  Vote: I like it -19 Vote: I do not like it

hello, i can not speak english

»
8 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Weird stuff going on in the system testing

»
8 months ago, # |
  Vote: I like it +4 Vote: I do not like it

who is speak turkey

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain to me the solution of div2 D2 (div1 A2), please? I have one with O(n * log2(n)) that has WA on test 6. Were there any corner cases?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I believe WA on test 6 comes from the incorrect assumption that the last station to be satisfied is one of the stations with the highest number of candies. A counterexample to this would be where you have 4 stations, and say station 1 has two candies to deliver to station 2, and station 4 has a single candy to deliver to station 3. The candy at station 4 will be the last to be delivered, despite there only being 1 candy at the station. Because of this, you can actually brute force check over all the stations that have candy to see the latest time at which all candies will be delivered, and take the max of those.

»
8 months ago, # |
  Vote: I like it +20 Vote: I do not like it

gonna purple yeah!

»
8 months ago, # |
Rev. 3   Vote: I like it +27 Vote: I do not like it

Clean approach for Div2E/Div1C:

We note that Alice's algorithm will fail to take any segment that has a negative prefix sum. Thus, we try to construct an array where the answer is the entire array, and the first element is negative, so Alice's algorithm will not choose it. We make the remaining elements nonnegative.

Let n = 2000, a1 =  - 1. Then, we see that the sum of the remaining 1999 elements (which we will denote as s) multiplied by 1999 will be what Alice's algorithm returns, even though 2000(s - 1) will be the actual answer. Thus, we want to pick an s such that 2000(s - 1) - 1999s = k, which is the same as s = k + 2000. We can thus make the first element of the array -1 and have the rest be a nonnegative sum of integers that is equal to k + 2000.

50450468

  • »
    »
    8 months ago, # ^ |
    Rev. 3   Vote: I like it +8 Vote: I do not like it

    Or more cleaner approach:

    Let n=2000 and a[1]=a[2]..=a[1998]=0, a[1999]=-y and a[2000]=x.

    Then (x-y)*n=x+k, in other words y=x-(x+k)/2000.

    Iterate from 1e6 to 1 to find x such that (x+k)%2000=0, and output answer.

»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

How much time does it has to pass after the contest is finished to be able to submit a solution of one of the problems? I want to submit my codes for the D1 and D2 problems.

»
8 months ago, # |
  Vote: I like it +35 Vote: I do not like it

I submitted the same code for problems D1 and D2 (Div.2). It got wrong answer in D1, and accepted in D2. Doesn't that mean that the tests for D2 do not cover all the cases, since D1 is a subset of D2?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    We're sorry for the weak tests, but we can't rejudge the solutions at this point. However, we'll add tests to the harder version for upsolving.

    Sorry again.

»
8 months ago, # |
  Vote: I like it +29 Vote: I do not like it

my D1 and D2 code is the same and i got wrong answer in D1 and accepted in D2 :/// please check the test cases :/

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Maybe now you'll get wrong answer in D2 too :D Just kidding, hope you get accepted on D1 as well

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      no , my code was wrong for a stupid bug and i have to get wrong in D2 too .

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We're sorry for the weak tests, but we can't rejudge the solutions at this point. However, we'll add tests to the harder version for upsolving.

    Sorry again.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

There are lots of people who submitted the same code at the easier and the harder Div1A(=Div2D) and got Accepted on the hard version, WA on the easy one. In my opinion it is really unfair to keep all these clearly wrong solutions accepted. Will be there any more testings, or anything to make it fair?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We're sorry for the weak tests, but we can't rejudge the solutions at this point. However, we'll add tests to the harder version for upsolving.

    Sorry again.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can any1 help me with problem C-Connect?? here my solution https://codeforces.com/contest/1130/submission/50454034

I run this code on Visual Studios and it's giving correct answer for both test case but when I submit it here it's giving me wrong answer. Somehow my code is generating 1 output for both test cases.

here how I approached the problem. I divided the land into different region and represented each region with a number. Then I found the color which belong to Alice and Destination. If both colors are same I am printing 0 , if colors are different I am finding the cost between all pairs of those 2 colors and printing the minimum cost. I don't understand why my program is giving wrong answer here but correct on my PC?? any help??

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There is no space at input map num, You should read char from input then transform to array a.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      OMG, that's silly of me awww... I am pupil again xD

      Is this what being dumb feels like, God?

»
8 months ago, # |
  Vote: I like it +9 Vote: I do not like it

top34051, I think that the test cases for the "Toy Train" problem are a little weak. My solution got AC on the harder version but failed the simplified version. Here are those:

Hope my rating does not change :)

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

    First of all, I really apologize for the weak tests. We'll add those tests to the harder version for upsolving.

    Deeply sorry.

»
8 months ago, # |
Rev. 2   Vote: I like it +74 Vote: I do not like it

Congratulations Errichto for becoming LGM.

»
8 months ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

Editorial link is redirecting to Announcement page. Please fix it. Edit: Works now. Thanks

»
8 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Very nice contest and problems. Thanks to all the guys that made these problems. Although I didn't manage to solve all of them, I really enjoyed this contest. Thanks to you all again.

»
8 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Good round!

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

i will get out of expert after this :D

»
8 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Chipicao !
Combinația perfectă de mâncare și distracție pentru a avea putere la concurs! :D

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

is problem div2 C solvable using DP ? i write a code that passed 23 tests and take WA on 24 , but i don't know why.. my code : https://codeforces.com/contest/1130/submission/50521284

»
6 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Update: got it.