kristevalex's blog

Codeforces Round #518 [Thanks, Mail.Ru!] — announcement
By kristevalex, 6 years ago, translation, In English

I would like to invite you to participate in the rated Codeforces Round #518. Date and time of the round: Wednesday, October 24, 2018 at 18:05. The round was postponed from October 23 to October 24 because of the ICPC Indian Online Qualifier.

This is the first competition I proposed. I hope you will enjoy it.

The round will have 6 tasks for the second division and 5 tasks for first (3 problems are common). The contest will last for 2 hours.

Tasks for you were prepared by Alexey kristevalex Kristev and Alexey Um_nik Danilyuk. Also thanks for:

Nikolay KAN Kalinin and Ildar 300iq Gainullin for help in preparing the problems; Ivan isaf27 Safonov и Oleg Merkurev Merkurev for testing the round; Mike MikeMirzayanov Mirzayanov for Codeforces and Polygon platforms.

I would like to express a special gratitude to Um_nik for the help throughout the process of preparing the round and also for patience for my stupid questions.

slight lyrical digression

This round is a thanks-round for support from Mail.Ru during the 8-year campaign!

Scoring distribution will be announced later. I wish you a high rating and looking forward to see you at the competition!

I'll be on the community Discord server shortly after the contest to discuss the problems.

UPD: scoring distribution div1: 500 1000 1750 2250 2500 div2: 500 1250 1500 2250 2750 3500

UPD2: edtorial.

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

Comments Comments (152)
| Write comment?
»
6 years ago, # |
  Vote: I like it +65 Vote: I do not like it

Codeforces is the best platform :) We are proud to work together!

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

I've noticed that 300iq is still unchanged to his real form. The legend will be mad.

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

If Um_nik didn't told you to stop creating problems, then I guess it will be a great round.

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

    Participate and find out for yourself :)

    I think that kristevalex really is a talented problemsetter. Of course he need more experience both in preparing and solving problems but his ideas are sometimes brilliant. Or maybe that was one time and will never happen again. Who knows.

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

    Dude that doesn't even have anything to do with this round's setter, seems your so salty have to put your issues on random blogposts ._.

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

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

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

.

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

Is it rated?

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

6 consecutive hidden comments, ridiculous.

UPD: 7 comments.

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

FST forces!

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

The time page gives 404 error, please fix it.

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

hhey is it rated or i dont partisipate

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

Why so many downvotes?

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

    even who's downvoting doesn't know why

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

I don't mind my comment to be harmonious with the others (since it doesn't mean that I was wrong to comment).

The time link still gives 404 Error.

I can know when the contest will begin from the timer of Codeforces, but I want to be sure, because the difference between our country's time and previous blogs' time was zero, and now it is one hour and a half.

→ Reply
»
6 years ago, # |
  Vote: I like it +15 Vote: I do not like it 
Let's call the set of rooks on the board connected if from any rook we can get to any other rook in this set moving only through cells with rooks from this set

Seriously, another problem with a bad statement, time to leave.

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

    Totally agree you cannot use a word to define it's self "Let's call the set of rooks ... with rooks from this set" , it like saying a ball is a round-shaped ball, it doesn't make sense.

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

      While I agree that the line (and problem statement as a whole) could have been phrased better, I'd also like to point out that what is being defined here is 'connected', so using 'set of rooks' in the definition isn't leading to circular definitions.

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

    Yeah, I kept on staring this line without any clue for quite some time. Glad that I was not the only one.

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

Am I the only one who found problem statement of Div.2 A to be tremendously hard to understand?

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

    can anyone please tell the solution for div 2 A

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

      Notice that minimal answer multiplied by M need to have L+K coins. So ans*M=L+K, or ans=(L+K)/M. It can happen that (L+K)%M!=0 and in that case you need to increment ans by 1, or otherwise ans*M will have less than L+K coins. Lastly, if ans*M exceeds N, then answer is impossible (-1), otherwise output ans.

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

    I think C had good problem statement. Maybe you didn't read it carefully, I don't know.. Maybe I'm one of the lucky ones.

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

    You're not alone, I got pretests cleared after 3 WAs and I'm still not sure I understood it correctly.

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

This contest is plain garbage.

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

    Contest was really nice. If you found contest easy try D,E,F, if tough then A,B were really easy. I liked 2A. In 2B, we just have to count the number of divisors of b.

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

nice contest

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

Excellent explanation. https://www.imageupload.co.uk/image/TAkQ

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

Problem A Div.1 Sample is useless.

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

    after weak pretest, weak systest, we have weak sample now XD

    just joking )

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

Hack for D1B?

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

    I hacked 1 solution with:

    21 2
3 1
4 1
5 1
6 2
7 2
8 2
1 2
9 1
9 10
9 11
9 12
10 13
10 14
10 15
11 16
11 17
11 18
12 19
12 20
12 21

    Maybe some solutions could get hacked by changing k from 2 to 3.

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

GreenGrape, your rounds are perfect

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

E: link. Nice problem!

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

    I used the same :D

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

    So, how to solve it based on this fact? My thought was like consider every edge separately, use something like tree dynamic programming to compute the probability for it to be the matching edge. But I'm not quite sure if this would work.

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

      There is a greedy algorithm to find maximum matching in a tree. So, I have DP[n][2] — vertex and "Would this vertex be already matched in greedy algorithm?". When I consider some unmatched vertex with its unmatched child — I must match them (like I would do in greedy algorithm). Each DP[v][i] is a pair of integers — how many subsets of edges in this subtree would lead to this state and what is the sum of results in these situations.

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

        Aha!Got it,thx. Just a slightly change of the algorithm of finding the maximum matching in a tree.

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

      You can use standard dp. dpv, 0 is max matching in subtree if we didn't take v, dpv, 1 is max matching if we took v. Every time we connect v and u which were not taken, we should add edge (v, u) to matching.

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

      Tree DP is right. Count the number of max. matchings and the sum of their sizes, where the top of a subtree can be unmatched / has to be matched. When processing a vertex's sons, you can use an intermediate state "has this vertex been matched with some son?". There are some annoying long formulas, but that's basically it.

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

I alone do not understand this part of the condition of problem C: "Let's call the set of rooks on the board connected if from any rook we can get to any other rook in this set moving only through cells with rooks from this set. Assume that rooks can jump over other rooks, in other words a rook can go to any cell which shares vertical and to any cell which shares horizontal."? After all, this means that the rook can make a move only in the next cell, where there is another rook (which does not correspond to test 1). Or how then to understand it?

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

Thought I had something for C, but I guess I was wrong! Kept getting WA pretest 3. Anyone want to share solution?

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

How to solve A?

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

    i change long long to double long and i get ac

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

    My solution is dp[i][number on position i][is a[i — 1] >= a[i]], to calculate it use prefix sums.

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

    I think for Div2C, you have to construct a zig-zag like pattern. Messed up my implementation though!

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

    let dpi, j, 0 / 1 denote for the first i elements, with the last value j, and the last dimension stands for is it needed that the next element is greater than/equal to the last element. Naively doing it would result in O(2002 × n), With prefix sum optimization, it can be reduced to O(200 × n).

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

    Div1A/Div2D is DP[10^5][200][2] , but I can't implement it ).

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

Div2A statement is bad :(

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

When Um_nik criticize misof for TCO and then, interestingly, leads a contest which consists of extremely bad statements... Just saying...

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

    Really activates my almonds.

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

      hahaha what does that even

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

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

          wait wtf is a homemade coconut? I never knew food science was advanced enough that we were doing this

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

            lmao dude have you even used a crafting table before?

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

              I see what you did there. You are trying to paint me as a man of no culture (because I don't play minecraft)

              Unfortunately, I'm always munching on cultured vegetables. Goes well with my alkalized water.

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

                Can you really talk about culture when you aren't drinking 1000 liters of milk in 3 gulps though

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

                  Dairy is bad. Instead I drink coconut kefir (from my own lab grown coconut) with some activated almonds

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

        Pete Evans describes "activating almonds" as putting them in water for 12 hours.

        I guess normal almonds haven't even achieved their final form

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

    I'd say "extremely bad" are a kind words for it.

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

    90% of questions we get were caused by participants not able to read statements and understand basic mathematical constructions.

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

      Instead, it would be better for a legend to reconsider his self-esteem.

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

        It would be good, but not instead. I can't really do anything about people who either don't know mathematical notation or don't spend time reading statements.

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

          Um_nik Hope you already know that, reading statements and understanding them are not same. And I think it's not you who will decide whether the statements were good or bad to understand. It's us, the contestants will do.
          Do you think contestants complain about problems in every contest? No. If something really went wrong, they complain about it.
          And only then you should say "I can't really do anything", when you know people hates you, so they started complaining about problems.

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

      Problem A had poor statement as well as weak pretests. :(

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

      Yeahh, right, maybe not able to guess what you hid in there. GUESSINGFORCES it was, how you like it ??

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

      No matter the quality of problems, I agree with Um_nik that there are so many stupid questions asked. It happens every contest, even if people don't complain later in the comments.

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

How to solve div2E?

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

    I didn't solve it, but here is my idea

    Cut all the vertexes with degree 1, repeat it until one is left : the root Then simply check if all vertex's child degree is not less than 3

    *Is it right?

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

    This is what passed pretests for me:

    A k-hedgehog has  ≥ 3k leaves. Since n ≤ 105 this bounds k by 11 or so.

    Now, perform k steps. At each step, remove all leaves from the graph, and decrease the degree of their parent by 1. Make sure that any non-leaf node either sees no change in degree, or their degree changes by >= 3. After this, update the graph so that you get a new set of leaf nodes, and do this again. After k steps, you should be left with exactly 1 node at the end. Any other case is a "No".

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

    Div1C solution is just a cross:

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

    After contest, I solved it after drawing some examples on paper and noticing the symmetry the hedgehog type of tree has, which turned out to be solution 2 from editorial.

    My solution:

    The natural solution I saw to the problem was to identify the "center" of the tree (which, must exist if it is a hedgehog) and then, from there do DFS/BFS to check if the given tree satisfies the properties given in the statement. The problem is, we need to identify the center quickly. How do we do that? If the tree is a hedgehog, every longest path must pass through the center node, which is number k, zero indexed (one can notice this by carefully reading how the hedgehog type of tree is created). So we find a longest path, and check if the length of it is > k. If it is not, then it is not a hedgehog. Else, we take the center node of the path and run BFS/DFS to check the properties, which are:

    • The center node must have degree equal or larger than 3.
    • All nodes that are not leaves (are at a depth < k from the center) must have degree >= 3 without counting its parent.
    • All leaves (are at depth k from the center) must only have degree 1.

    If all these are satisfied, we print "Yes", else, the given tree is not a hedgehog.

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

Does having two rows of white squares (0, 0), (2, 0), (4, 0), etc and then (0, 3), (2, 3), (4, 3), etc work???

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

Shit. I just found an asymptotically sufficient assignment for div1C:

  • a row of knights in the middle
  • 2 columns in the middle
  • out of these two columns, remove most of the top half of one and most of the bottom half of the other

Also, Um_nik, if div1E reduces to div1A-B after an easy to find observation, it shouldn't be in an online contest!

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

    Easy to find you mean online? I didn't succeed, but I'm not good at googling. I'm sorry for that, you are right about problem being only about this observation.

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

      "adjacency matrix" rank tree: gives SE as the second link, the first answer mentions something 2x size of matching

      "adjacency matrix" rank tree matching: gives the answer for a tree directly, generalising this to a forest is easy

      Not completely easy to find, but easy enough.

      My story: I looked at the scoreboard immediately after submitting B, saw that someone solved it already and decided to work with the assumption that the solution is online. I read the statement, decided that if something is online, then it's the rank of an adjacency matrix, found something (including the first link), read the statement again and realised — I missed that the input is a tree, made the two queries, mentally checked that the first sample fits, so I haven't found something irrelevant, and started thinking about a solution.

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

The descriptions were not clear at least for me. Didn't like this contest.. AWFUL

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

Deleted

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

    How did you generalise that? It's just 1 row + 2 knights.

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

problem C statement was really bad .. ofcourse so many solved it but you should consider not everyone has shakespear english level and give the beginners who hasn't read alot alot of problems a chance to solve it

I was going to try it but i was like if i need so much time to understand it then when I'm going to think how to solve it

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

    Not your fault. I've read Shakespeare in school, it was easier than C.

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

Any idea why this submission would get WA on test 3 while this one passes pretests?

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

Being in #1 for almost all the time, then got punished by a hack on 2A :D At that moment, I realised the statements were bad enough for me to deny reading them in the 10 last minutes :D

Btw, anyone can provide me a hack for 2A? :D

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

    Could be overflow, numbers go up to 10^18

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

      Not with mine. My solution consists of at most 1 addition, and no multiplication, the other operations possible were division only...

      My hacked solution: 44781223 (not sure if accessible now)

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

    10 6 3 4

    many programmers checked only if m>n or (l+k)>n, then print -1 else printed ans=(l+k)/m + bool((l+k)%m), they never checked if ans*m is exceeding n or not and hence got hacked.

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

    Both statement and pretest for Problem A were too poor. I will also fail system test! :(

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

Pretest 3 of div1A?

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

    I don’t know what is test 3.

    But you can try this one.

    3

    -1 -1 -1

    Answer should be 40000

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

      Thanks, my solution does work for that test though :(

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

Is DearMargaret going to have a bad rating change for first time?

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

How to solve Div2.C ? I'm really confused by the statement, thus cant solve it ://

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

    Same here, examples didn't make sense for me.

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

    for every edge x1-x2 put rook of color x1 to (x1, y) and of color x2 to (x2, y). make 'y' value unique for every edge and check condition that all colors should be on chessboard

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

      There could be n * (n — 1) / 2 edges, which is 100 * 99 / 2 = 4950 for 100 colors. Your solutions places 2 rooks for every edge, resulting in 9900 rooks on the board. This is a violation of: "Total number of rooks must not exceed 5000."

      There is accepted solutions with this algorithm. Could anyone please explain where my thoughts are wrong? Are they?

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

        m <= min(1000, n*(n-1)/2)

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

          Thank you, so this was a 'how do I read correctly' kind of problem... |-)

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

Am I the only one who passed the pretests of problem A Div.1 using a Top Down approach?

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

    deleted

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

    I did, but I had to resubmit at the end of the contest to reduce memory usage :( Recursion uses memory too, so having array size within the limits is not enough.

    I tried this test in Custom Invocation and got MLE: -1 200 -1 200 ....

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

Does anyone have a correct solution for Div. 2 F/ Div. 1 C? I found something that gave but I couldn't improve it further.

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

    Nigga read the comments.

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

      Sorry, I had missed your comment, thanks!

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

How to solve Div1C:

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

    How do you generalize the answer from this? It's just 5 guys chilling in a row with 2 in front of them

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

      In one column you have a knight at y=0, in the next one at y=0 and y=3 and that pattern repeats. It seemed quite obvious to me.

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

EDIT : Didn't see that the editorial is already published.

EDIT: Most probably, it fails because I am assuming the CHT implementation to be min-oriented but it actually is max-oriented.

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

    Idk, seems reasonable to me. But I also observed that the optimal i for each t would be the same, i.e. we just spam some i until one upgrade is available. So no need to use CHT here.

    EDIT: Same as jtnydv25 and realized the editorial doesn't do what I did :s

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

      Do you mean for each t > 1? (otherwise the statement is definitely wrong), and how do you prove it even for t > 1 ?

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

        Wow, right when I tried to write my proof I realized it was completely wrong :o

        How it was not caught in the pretests is beyond my knowledge though.

        Anw there goes my red xD was fun bragging around

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

Please someone tell me, why do I get TLE in this: http://codeforces.me/contest/1068/submission/44804608 This is Div2B

Please tell me, it won't take a minute for you to read my code.

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

    Integer overflow. Remember, n ≤ 1010.

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

    i*i becomes a negative value when it overflows, so your for is basically infinite

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

Div1C
Is this the way to place the knights?

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

Dear kristevalex and Um_nik, please stop making problems.

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

What's wrong with vintage_Vlad_Makeev? Was he hacked or just rofl?

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

English statements are not too good, especially problem Div2C. Still, it was a fun competition, thanks for the effort.

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

The problems were nice, but the contest was bad. Here are the reasons:

  • A is much harder than B. So a lot of guys decided to not participate when they haven't solved A in 10-15 min. So A+B guys with bad time will be severly punished for participating in ranking. While A+B fast will be ~60th place.
  • E after googling is on the same level as A, still harder than B.
  • in C you can submit anything, get the authors output and generlize...
→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    All of that are valid points, thanks.

    • That's kinda my fault, but I still think that A is easier. A is standard DP and B needs some observations. Also I don't think that authors should be thinking about strats like 'couldn't solve A in 10 minutes — leave'.
    • Nothing to add here
    • I didn't know about that feature of CF. We changed outputs for samples and thought that was enough.
    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Output of C provides almost no information. I don't think there is any mistake here. Out of 3 people who said "easy to generalize" only 1 guy actually did it.

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

      which observations does B need? it was obvious from the picture how to solve it

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

div1 B test case "1 1" is not in the pretest...

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

Why was Div2B given a max score of 1250 instead of the usual 1000? Did you think Div2B was closer to Div2C than Div2A? I read Div2B 4 times because of your decision to give it 1250 points. Guess I should have done that for Div2A instead as it had such a good corner case. I read similar complaints about Div1A and Div1B as well. Points distribution was not good.

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

After this round, i am demotivated for sure.

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

if http://codeforces.me/contest/1068/submission/44797756 is AC. why http://codeforces.me/contest/1068/submission/44800937 is WR?

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

    Participant's output -501767591

    So it seems that you have overflow. Checking the code you declared int bs() instead of ll bs(). I didn't test it but it seems that is the problem.

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

Started after 10 minutes, misunderstood B, got WA, then solved A, panicked with B, pretests passed E, panicked with B again then finally understood(felt so stupid at that time), couldn't submit C with 2 seconds in hand! :(

Watched the status board with heart in my mouth whether E will pass the system test or not. It passed :D Submitted C after contest, AC in one go. -_-

Mixed feelings, A very eventful contest indeed!

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

Very nice problem !

And I finally got the Expert Title during this contest!

I wait for this blue name for a YEAR and I finally got that!

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

Unfortunately the system tests on today's Div 1 problem D were quite weak. I wrote up an explanation here: https://codeforces.me/blog/entry/62692. Make sure to take a look if you are trying to solve problem D in practice mode (or just interested in the problem).

→ Reply