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

Автор Marco_L_T, 7 лет назад, По-английски

Hello, Codeforces!

I'm quite excited to invite you to participate in Codeforces Round #447 (Div.2 Only) which will be held on November 19 16:55 MSK.

All five problems are created by Zerui Cheng (Marco_L_T), Bingheng Jiang (NOIRP), Yiming Feng (whfym). And it's our first round on Codeforces. We want to show our great thanks to our school The High School Affiliated to Anhui Normal University and our coach Guoping Ye in competitive programming training.

And we also want to show our great appreciation to Mikhail Krivonosov (mike_live), Gleb Lobanov (Glebodin), Weihao Zhu (Tommyr7), Shiqing Lyu (cyand1317) for testing the problems, to Nikolay Kalinin (KAN) for coordination and to Mike Mirzayanov (MikeMirzayanov) for the fantastic Codeforces and Polygon platforms. The round can't be realized without their great help.

The contest will consist of 5 problems and you'll be given 2 hours to solve them. As usual, the scoring will be announced shortly before the start of the contest.

The contest is rated for Div. 2 contestants. And the same as before, Div. 1 contestants can take part out of competition.

Wish everyone high rating and bugless code!

See you on the leaderboard!

Clarification: In the mail, it reads that the duration is 2 hours and 30 minutes and it'll contain 6 problems. There's a mistake. The duration of the contest is 2 hours and there will be 5 problems.

UPD1: Scoring: 500-1000-1500-2000-2500

UPD2: The contest is finished! Have fun hacking!

UPD3: The system test is finished! Congrats to the winners!

And do you find something interesting in the statements,especailly for Chinese contestants?

Div.1 & Div.2:

  1. fateice_ak_ioi (solved all the problems and got 22 hacks)

  2. peace (solved all the problems and got 10 hacks)

  3. dreamoon_love_AA

  4. KrK (solved all the problems)

  5. Benq (solved all the problems)

Div.2:

  1. fateice_ak_ioi (solved all the problems and got 22 hacks)

  2. peace (solved all the problems and got 10 hacks)

  3. ec24 (made 16 hacks)

  4. daaaaaaaaaaaaaaaaaaa

  5. QYitong1

UPD4: Maybe you're complaining that there're too many hacks and the pretests are so weak,but it's our intention to do so. We regard hacks as a very important part and a feature of Codeforces.Do you agree?

UPD5: Editorial

Maybe B and C are a little harder than before,we'll be cautious about this next time.

Hope you have fun in solving the problems and hacking!

See you next time!

  • Проголосовать: нравится
  • +280
  • Проголосовать: не нравится

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

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

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

Hope you have fun with the contest! See you on the leaderboard!

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

    If this contest will be rated It will be very good two contests int three days Good luck

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

wish all the participants high rating! :)

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

Is is rated?

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

Hope you make progress and show yourselves!

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

Wish you have fun!

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

我随手AK

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

To be continue

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

Applause in the front.

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

For ratings!

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

3 months ago i had 100 more rating than now. This contest will get everything back to normal and even higher!!!

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

KAN, why the registration is delayed?

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

Previous contest problem description was realy sort but briefly. I hope this contest will be same :)

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

I think this is a mathematical contest because the authors are Chinese. I do not like it very much

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

Deleted

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
  • it seems an nice contest excited :)
»
7 лет назад, # |
  Проголосовать: нравится -28 Проголосовать: не нравится

Prepare for non-alogrithmic idiotic math contest

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

The announcement is not very short as previous contests.

But we can see sincere thanksgiving...))

Wish every body luck and high rating !

And wish good luck codeforces servers!

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

Two contests in three days (if not counting contest from CS Academy lately). Well, the excitement inside me is rising high :D

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

Thanks to all the people --> 2 contest in 3 days awesome feeling :) Hope for large number of hacks and good rating Wishing all the best to everyone

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

Another Chinese round, so exciting! Hope for short statements and high rating.

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

    You are out of competition, aren't you? How you get a "high rating"? :)

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

And the mail reads that the contest will be of 2 hrs 30 minutes. :| Also, it reads 6 problems instead of 5 as declared in announcement :3

Anyway, best of luck everyone. Happy Learning and Coding.

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

    Well,maybe there's something wrong with the mail. The duration of the round is 2 hours if everything goes well.

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

      Yeah, I understand that. Just bringing it to the notice of problem setter/contest setter. This issue had happened once in past too :|

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

all good luck, and let your rating go up

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

Всем удачи!!!

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

What will you do at CF#447? Are you free? Can you come to AK?

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

What a pity! I've just become candidate master. Now I can't get any rating!!!! QAQ

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

I expect short problem statements.

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

Beijing time 21:55 , perfect!

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

There should be another id to get rated. :(

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

Hope short problem statements just like past contest.

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

Hope everyone high rating! And hope me not to drop to green.

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

Wish everybody High rating)))

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

Today will be a perfect ICPC-style Contest practise!

2:00 hrs Codeforces + 2:30 hrs Codechef! :/

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

Time to beat some meat.

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

Why can't i register?

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

That feel when div2 B is harder than div2 C...

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

A=B=C < D = E

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

HackForces.

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

I was excited to see characters from Land of Lustrous in the first problem but then you dropped them later on. :/

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

    I'm sorry but I can't decide all the statement :(

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

    If I have the chance to propose a contest on my own, I would write the statement in the similar way.(But maybe it will be long long time before I have the chance.)

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

Hacks everywhere!!!

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

I was intended to hack some one on Problem C (while I found my code was wrong). But I could never load the "hack" page, watching the cycling circle. Then my submission got HACKED...??? So is it a bug?

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

    I had the same and then I changed my browser (using Microsoft Edge) and I was able to hack 18 times the C problem it was really nice cause I only managed A and C

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

The hardest B I have ever seen :D

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

What's the hack for C?

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

Понял как решается B и C после того как заблокировал их. Больше никогда не буду блокировать задачи ранее чем за 15 мин до конца контеста. Nice contest btw.

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

what's C's hack data?It's amazing.

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

Was E computing scc and calculating for each scc and taking the max of it???

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

    That's what I tried but I got WA on test 3. I also traversed from the SCC of the starting tree until the end of path and took maximum over all using DP.

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

10 hacks per second !

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

When u hack 14 but u know that ur own code is incorrect in 2 probs B) .

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

Problem difficulty: A < C < E < D < B.

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

    D was definitely hard, but, come on, D < B?

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

      Believe or not, my mind completely draw a blank in B. In the last 30 minutes of the contest, I tried some idea (like flipping sign of four cells that are corners of rectangle won't change the result), but none of them works.

      By the way, how to solve it?

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

        Notice that after you choose the numbers in the upper left N - 1 by M - 1 grid, the rest of the numbers are determined. So the answer is 2N - 1·M - 1. You also need to check the case where N + M is odd and K =  =  - 1. (Answer is 0 in such case).

        EDIT @below: Yeah, you're right, oops.

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

        It's a classical combinatorics problem. In case k = 1, you can arbitrarily fill the top-left (n - 1) × (m - 1) matrix — other fields will be uniquely determined and correct. Thus in that case the solution is 2(n - 1)(m - 1). The same logic applies when k =  - 1 and n ≡ 2m. Otherwise you can show that there is no solution.

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

          Problem B. Let's consider the k = 1 case. I don't understand the fact why solution is uniquely determined by fixing the top-left matrix arbitrarily. I get it that all the elements (i,j) where j = m and i = 1 to n-1 and i = n and j = 1 to m-1 are uniquely determined by parity of negative numbers in that row/column. The now filled numbers of the last row and the last column determine the element (n,m). What if they contradict each other ?! Then the sign of (n,m)th element is not uniquely determined right ?

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

            They won't contradict because the product of all the numbers in the last row (except the last element) is equal to the product of all the numbers in the last column (except the last element), because they are both equal to the product of all numbers in the (n - 1) × (m - 1) submatrix.

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

            After chosing one columm after another, numbers of product of cells in the same row and in each columms before is always even. So product of the last columm is even.

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

        Write brute force, build a table with answers, see the pattern :)

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

    How to solve E?

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

    For B, I did a simulation to get the pattern. Was able to make 2 hacks in my room. let's see if my solution passes the system test.

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

      can you tell how do the output for third case is 16 ?

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

        Here are the 16 possibilities.

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

    I cannot agree more! Even for me solutions of D and E were much more obvious than B. That's not something happens any often. I believe if B/C were not such killers, D and E would be solved by many more people though they were tedious.

    Then again I did not expect this solution of D with complexity O((n + m)log2n) would pass. Isn't it almost 4 × 108? 2.5s seemed impossible.

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

How do the output for third case is 16 ?

PROBLEM: B

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

Authors thanks a lot for this Hack party! Very nice problems!

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

I had I idea to code Tarjan for E (still not sure will it work) but then saw so many wrong Cs in room.

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

Wow, that was the hardest B I have seen in a while. I had to bruteforce to find the formula. Moreover, I guess a lot of people are either hacked or FST because of taking modulo mod p instead of (p-1).

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

Authors should care more about the pretests, because there were more hacks than Accepted codes on task B! -_-

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

Not a Div. 2 contest. B, C were too difficult.

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

So, how to solve B? I can't think about it anymore :(

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

What's wrong with my approach to C?

For each starting position i we find the gcd until all positions j (i < j < m). Then, for each gcd, we check if it's in the given array. If it's not, output -1; otherwise, output the given array.

Thanks in advance.

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

    4

    1 5 6 8

    ans:6 5 8

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

      I see now. The elements in the initial array don't have to be increasing order. Thanks!

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

    3
    1 4 6
    your approach would give -1 as 2 is absent which is gcd of 4, 6 but answer is possible.
    answer :
    5
    1 4 1 6 1

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

      Thanks. I unfortunately set a nonexistent constraint for myself :\

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

        can you tell me why absence of 2 is neglected????

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

          because in the final answer array every alternate position is occupied by the number which is divisible by every other number say num.
          so it is easy to see that now for every subarray of size greater than 1 you can achieve num as gcd.
          Rest remains the case for every single element (for which gcd is equal to the element itself) which are already present in the original array.
          if no candidate is possible for num then answer is -1.

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

        you are not alone bro :/

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

HackForces~

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

Hack for C :

3
3 18 24

Answer is

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

    What's the answer for this test case?

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

    when we take gcd(18,24) we get 6 but 6 is no where present in the set. how is this possible answer? am i missing something?

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

      You're missing the 3 between 18 and 24.

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

      This is answer, because you need take gcd on segment, so gcd(18,3,24)=3 and all is correct

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

      You calculate gcd(ai, ai + 1, ..., aj) for every 1 ≤ i ≤ j ≤ n, so there won't be gcd(18,24) at all, instead, it is gcd(18,3,24), which is 3.

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

Troll C-task easier then B. Good job, bro

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

Half of participants during the contest

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

It is a hacker's round...XD

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

Problem C is a very nice trolling problem :D

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

How to solve D?

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

    It is almost a complete binary tree and has max depth logN. To solve query for V, I checked all ancestors as LCA and did a range query on the subtree of the other child using persistent segtree (can be done offline with BIT too).

    Code

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

      Your method is too complicated. The author's solution uses merge sort to pre-process and takes O(log^2) time to check the answer by brute force.

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

        Okay, yeah I know it is too complicated but it struck me immediately and I coded it. My solution solves in log^2 time too but I guess persistence is unnecessary. :)

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

          umm. could you please explain the persistent segtree part. I didnt get you exactly. Thanks

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

            Given vertex V and parameter L, I need to find sum of distances from V to any vertex U in its subtree such that dist(V, U) <= L. I flattened the tree and constructed persistent segtree on it. So, the query reduces to find the sum of values in some subarray such that value <= L.

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

              How do you manage not to count twice or more the nodes of his subtree. For example in node U you count some childen node (call it x), and then when you climb up to U's parent maybe you can count again that x node.

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

y u do zis

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

although i am a bad coder because i dont practise algos efficiently i have this mathematical intution for b which lead m to solution.I though answer as 1 and 16 and immediatley power of 2 came to my mind 16 is 2^2*2 and 1 is 2^0*0 so i guessed 2^n-1*m-1.Immediately lightning fell i though i could fill up n-1*m-1 internal squares nyway then fill last row in last column my wauy. That 16 was a big hint. Power of 2

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

    lightning electrocuted me

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

    This was my thought too but I got hacked. I don't think you can fill up the internal squares in any way you like and then fill last row and column to make it work. For example consider a 4x4 grid with k=1. One way to fill in the internal 3x3 is:

     1  1  1
     1 -1  1
    -1  1 -1
    

    But there is no way to complete this. The last row would have to be: -1 1 -1 1 and the last column would have to be:

     1
    -1
     1
    -1
    

    So we get a conflict in the bottom right cell.

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

      You miscalculated the last row with your example. With you example the last row should be all -1's because each column currently has a product of -1.

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

      Oops nevermind, I made a mistake. I put the last row wrong.

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

System test already done lol

Fastest ever

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

Some of the weakest pretests I have ever seen in my life. Solutions with n and m defined as integer passed the pretests in problem B. Solutions that didn't check the case (n + m) % 2 = 1 and k = -1 passed the pretests in B. And problem C pretests were obviously a troll because most people solved a completely different problem yet passed the pretests. gg problem setters

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

Diabolical test case for C (I guess):

4

1 3 15 20

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

Today, I had a bug inside a bug in problem C which saved me from getting hacked!

// ok?
bool ok = true;
for (int i=1; i<=n; i++) {
	int g = 0;
	for (int j=1; j<=n; j++) {
		g = gcd(g, a[j]);
		if (!x[g]) {
			ok = false;
		}
	}
}
int gg = accumulate(a+1, a+n+1, 0, gcd);

if (!ok) {
	cout << -1;
	return 0;
}

So, my original idea was to check, for every subsegment of the given set, whether its GCD appears in the set. Now this is obviously wrong (testcase = [1, 4, 6]), but in doing so I misimplemented this piece of code and I actually checked whether the whole set's GCD was in the set, which is, coincidentally, exactly what I should have done, only not n times! :D Notice how the inner loop starts from j = 1 and not j = i.

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

Room 110 (my room)

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

my code with scanf accepted but with cin it got TLE!

Not cool author! not cool...

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

    Deleted

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

      I am sorry but I couldnt see in D and E statements it being suggested.

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

      Oops,my fault!I had suggested,but it was removed later. Sorry for not suggesting faster ways to input or output.

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

        Why do you need to recommend faster I/O at all? Wouldn't just setting higher time-limits be a better way of dealing with it, unless you already had some slow nearly-passing solution in mind?

        If a problem's only solvable with fast I/O that means that most likely you can only solve it in a very small number of languages. In fact, in this contest 100% of the accepted solutions were in C++. There are a few correct-looking Javas but they all got TLE. That's not great.

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

          First, scanf works better than cin, I think. And if we guarantee that cin is ok, the time-limits must be set much higher. Some TLE algorithm could pass tests easily (such as some slow O(n(log(n))2) algorithm for problem D). And we don't want this happen.

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

        Also, did you decide not to include max tests into pretests intentionally? I agree that contestants can (and in a lot of cases should) generate max.tests by themselves to be sure that their solutions work, but still — making such pretests sounds like a way to decrease success rate at first place :)

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

          Wrong information. Deleted. Sorry for no max-size cases in pretests.

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

            OK, let's take a look.

            My cin/cout solution to E which passed pretests fails on test #14 with n=400k, m=1e6. Looking at first 13 tests and assuming that all of them are pretests, the biggest one I see has n=1e5, m=233333. It means n+m=1e6/3=1/6 of max.test.

            My cin/cout solution for D fails on test #18 with n=1e6, m=1e5. Looking at first 17 tests, there is test #8 with n=438275, m=22553, and a bunch of tests with n=2e5, m=1e5. Adding it up for test #8, we'll get ~4.6e5, less than 1/2 of max test.

            So can you please tell exact constraints of largest tests provided in pretests? It seems to me like they are quite far away from being maxtests. Yep, maybe they are rather large — but from your comment it sounds like tests are "special" if N=1e6 and ordinary if N=1e5 :)

            I already saw your comment in contest announcement, and that's why I'm curious — is the story with D and E same and you expected that it will lead to a lot of hacks, or you just wanted more people to fail, or was it some sort of preventing server load or anything like that, or was it just a miss in contest preparation, or what was the motivation at all.

            In case it was done trying to increase number of hacks — such strategy doesn't work well :) I see as many as total of 2 hacked solutions on E and no hacked solutions on D. I didn't check if they failed because of TL or not :) First of all, not many people are trying to hack hard problems (most of the contestants don't even solve them), and second — hacking I/O is generally harder and takes more effort — you have to be sure about it and know some benchmarks, and there are quite a few tricks like "this thing works fast in GCC but slow in MVS" etc.. Also, I believe that most of the contestants think about it like "OK, there is probably maxtest in pretests, so if they passed — that should be fast enough". It may be different for some trickier tasks, when people try to push NsqrtNlogN algo for 5e5 or take naive solutions with a bunch of optimizations and breaks, but not for something like D/E yesterday, where complexity of any reasonable solution barely depends on input structure — but only on its size.

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

              Sorry for any inconvenience caused.We set a tight time limit on D and E because we don't want to see slow solutions pass.For example,someone used O(nlog^2n) solution on D which is not intended and someone used brute force to calculate the answer for each edge which is O(m*sqrt(Ai)).We just didn't want to let this kind of solution pass.As a result,cin/cout may get TLE.

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

                Also,you said that we didn't put maximum tests in the pretests.However,in our opinion,a contestant should be able to generate some data and use custom invocation to check whether the solution can fit in the time limit.And there isn't any regulation saying maximum tests should be put in the tests.If it made you feel not so good,we apologize for this.

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

                  I agree that contestants who don't do such checks should generally blame themselves. Also, you are right that there are no rules about what pretests should contain.

                  It didn't affect me personally — this contest had no value for me, in ordinary div1 round there is at least a change of some colorful number in profile which is called "rating", and for div2 rounds even that reason to possibly feel bad goes away; so I don't feel bad about this contest in any way (unlike some other people here in comments, especially div2 folks who did it as rated event), and I actually think I had nice time participating in it — thank you for this round!

                  One thing which you are wrong about is "use custom invocation". Custom invocation has a limit of 256kb for file that you upload. So one can't really check maxtest for problems D or E there in some trivial way — because it is much larger. You can either put generator into code, which will not allow you to check I/O part (at best you can check only output part, for problem E it is just a single number — so not very useful), or test it locally, which generally requires you to create local environment which is as close to CF as possible.

                  P.S. I understand that it is possible to do something like "generate a test of size max.test/30, use it and multiply the result by 30", but it is not very precise and not trivial.

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

            Sorry for my wrong information. Someone told me we have max-size cases in pretests.

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

And have fun FST on Problem C. QAQ

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

I like the way of setting pretests and main tests ;-)

good job

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

Less Codeforces, more Hackforces.

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

What a fuck. It was so fucking hard. A easy, C normal C. But dudes come on. WTF is with B. Even if you find the correct formula like i did, you still need to take care of corner cases and also B and fast exponentiation that's funny.

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

B is pure evil!

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

Why time limits for first three problems are 1 sec? Usually its 2 sec.

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

    read my next comment

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

    bro in youre pow function

    you should set it to :

    long long pow(long long x, long long y, long long mod) { ... }

    you've overflowed ;-)

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

      shit you are right it got accepted now. feels sad small mistake destroyed me.Else i culd have felt happy that i solved b in contest Thank you so much

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

For those who can't understand why they got hack on B, here is a problem using Fermat's Little Theorem -> see the editorial from this problem https://www.hackerrank.com/contests/infinitum18/challenges/tower-3-coloring; why a^b mod c is a^(b mod(c-1)) mod c

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

B and C were harder than normal (perhaps it would have been better to lower the constraints to avoid fast exponentiation?), but overall this round was not as hard as some other Div 2 rounds, considering that I managed to finish in 50 minutes ...

... well, until I realized that my solution to E was incorrect. Anyways, I have nothing against weak pretests. :P

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

Today's Round is the Proof of The First Law of Online Judges.

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

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

    They are twince ! Hacked !

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

    For me, A as well. Some people forgot that string.size() returns an unsigned integer. So using string.size() — 2 when string length is 1 will lead to overflow.

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

For Prob C (Marco And GCD Seq)

Input:

15

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Ouput:

10

6 7 8 9 10 11 12 13 14 15

Why this is given wa verdict? (set of pairwise gcd of elements produced the input set)

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

Solution to problem A. QAQ was already available on the internet, well before the contest.Please visit source — http://www.geeksforgeeks.org/find-number-times-string-occurs-given-string/ Hence I don't think people should be penalised if their code matches with someone...as they both referred the same source....codeforces please see into it !

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

Dear Codeforces team,

I received this email few minutes ago: "Your solution 32459520 for the problem 894A significantly coincides with solutions MoodyFares/32459305, one_two/32460865, Redwan_hossain/32461143, Ali_Shehab/32461775, Hinke/32462032. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.net/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties."

I didn't cheat. I solved the problem in 4 minutes — it was super easy. I believe the system reported a similar code because people tend to use i, j, k — for loop variables; s — for strings; and ans — for the answer.

Please rerate my submission.
Thank you!

UPD: Even in the editorial you used i, j, k, s, and ans :)
UPD2: The violation was removed. Thank you for the quick response!

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

Amazing problems... Amazing system testing... Amazing Ratings Update.. Amazing CONTEST

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

Спасибо всем организаторам за проведение контеста и участникам контеста за спасение от системных тестов путём взлома. Но очень обидно что я не смог решить задачи B,C.

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

the contest was bad. dumb weeaboo trash and weak preliminary testcases.

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

    No. I disagree with you. So maybe there were mistakes somewhere. But they did work to create a contest. You do not have the right to say that it was bad so-as you have never conducted a contest. Sorry if I did not put it right.

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

      While I don't agree with his sentiment, what you are saying is totally wrong too. You don't need to conduct a contest to recognise a bad one. That being said, I don't think today's contest was bad. However, he is free to express his opinion.

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

Don't ever put a contest again ever are you sure that it was for DIV 2 ? really ?

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

    I partially agree with you since problem B was at the level of task D. But everything else was excellent. It is my opinion.

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

I am disqulafied ,why????? My solution was by me . I am disagree with this decision

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

really terrible contest :/

very easy problems and shity codes

very very easy problem E and because of fast i/o 80% failed

worst contest ever with shity problems that sucks

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

Wow this is the hardest CF Round I have participated.

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

Why the ratings are altered again now?

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

codeforces should become ready for the goodbye 2017 contest which has the most participants :) it did very well this round i hope it remains the same

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

Ohhhh!! Hackforces Round!!!

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

Really bad time limit for problem E due to big i/o

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

    D as well. Difference between fast IO and scanf/printf is about 1.5s, which is more than half the time limit.

    You have to be soo careful during implementation to even have a chance at getting AC without fast IO.

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

    Author's code uses scanf/printf for D and E. For D,it runs in 1.1 seconds and for E,it runs in 1 second. So maybe cin and cout without ios::sync_with_stdio(false) will get TLE,otherwise,maybe your complexity isn't the intended one,so it gets TLE. For example,the intended time complexity for D is O(nlogn+m(logn)^2) and for E it is O(n+m).

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

C was such bait. Made the observation that the largest number in S must be in the sequence, and then tried to construct it from there... red herring.

Realised the correct solution with 7 minutes left in the contest.

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

What the hell was this? the worst round ever. The worst problems ever! Go home.

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

    If you're not satisfied with the contest,please point out where we didn't do well.Only blaming will make no sense and will never help us improve and prepare better problems.Thank you!

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

      The problems where very interesting, But the pretest where weak that is why.

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

Rip those submissions on C, where people saw the score board, saw high and extremely fast increasing rate of pretest passed, panicked, wrote some garbage greedy and then submitted themselves.

And they got pretests passed too ! Too bad, WA. Never ever open score board during the contest is what seems best to me.

The problem C is not very difficult and things may have been different with strong pretests.

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

Многие говорят что этот раунд был наихудшим раундом, но я не согласен с этим. Да, были какие-то ошибки, но контест был отличным.

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

Good Contest