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

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

Tenka1 Programmer Contest/Beginner Contest (atcoder.jp) will be held on Saturday (time ). Please check http://tenka1.klab.jp/2017/index.html for details. The writers are DEGwer and hasi.

Programmer Contest

Beginner Contest

Contests Announcement

The point values will be announced later.

Let's discuss problems after the contest.

UPD:

The point values will be

Beginner contest: 100 — 200 — 300 — 500

Programmer Contest: 300 — 500 — 800 — 1400

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

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

It seems that you can easily buy bitcoins by Japanese Amazon Gift card. Search by yourself if you want to know more about it.

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

It seems, hasi joined the writer of this contest. (updated, thanks -emli-)

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

how to solve D ?

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

    In problem D, this is not bitwise xor. Bitwise OR is correct. Once I misreaded, so I wrote this at the top of the comment.

    Let's constder about the pattern of K = 13:

    • All of buying things are 0 (0 or 1) (0 or 1) (0 or 1) in binary-representation, 0 — 7 in decimal
    • All of buying things are 1 0 (0 or 1) (0 or 1) in binary-representation, 8 — 11 in decimal
    • All of buying things are 1 1 0 (0 or 1) in binary-representation, 12 — 13 in decimal
    You can choose any pattern to buying, of above patterns.


    Let's constder about an another pattern, K = 22:
    • All of buying things are 0 (0 or 1) (0 or 1) (0 or 1) (0 or 1) in binary-representation, 0 — 15 in decimal
    • All of buying things are 1 0 0 (0 or 1) (0 or 1) in binary-representation, 16 — 19 in decimal
    • All of buying things are 1 1 0 0 (0 or 1) in binary-representation, 20 — 21 in decimal
    • All of buying things are 1 1 0 0 0 in binary-representation, 22 in decimal
    You can choose any pattern to buying, of above patterns.


    So, you can divide [1, K] into logK parts (maximum). The complexity is N * logK = O(NlogK).
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Unfortunately I still don't get one point. For K=13, you can choose 0001 from the first group and 1100 from the last group. Their bitwise OR is 1101 which is <= K.

      But you could also choose 0111 from the first group and 1100 from the second group, their bitwise OR is 1111 which is > K.

      How does this dividing into parts account for this?

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

        When we do bitwise or of the values ai we can get one of the following numbers:
        1101 = 13
        1100 = 12
        1011 = 11
        1010 = 10
        1001 = 9
        1000 = 8
        0111 = 7
        0110 = 6
        0101 = 5
        0100 = 4
        0011 = 3
        0010 = 2
        0001 = 1
        0000 = 0

        That is, when we do bitwise or of numbers from set A, we can get all kinds of numbers ranging from 0 to K.

        So, our first guess is to go through all of these 14 numbers and collect the numbers ai which fit the pattern:

        for (int pattern : {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13})
        {
           set<int> numbers_fitting_pattern;
        
            for (int a : A)
              if (a & pattern == a)  
                  numbers_fitting_pattern.insert(a);
        }
        

        Now we can optimize this algorithm. Let's say S0110 is the set of {ai} such that theirs bitwise or gives 0110. Namely, S0110 = {0000, 0010, 0100, 0110}.

        Now let's look at S0111 = {0000, 0001, 0010, 0100, 0011, 0110, 0111}.
        As you can see S0110S0111. Even more — the set S0111 contains all the sets S0000, S0001, S0010, S0011, S0100, S0101, S0110.

        That means we can use only S0111 and skip the sets resulting from patterns 0000, 0001, 0010, 0011, 0100, 0101, 0110. After this skipping our original loop will look like this:

        for (int pattern : {7, 8, 9, 10, 11, 12, 13})
        {
           set<int> numbers_fitting_pattern;
        
            for (int a : A)
              if (a & pattern == a)  
                  numbers_fitting_pattern.insert(a);
        }
        

        This has improved our loop almost twice, but we can get rid of a few more patterns in this loop.

        Do you understand now?

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

    Here is my blog post about D :)

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

What about rating changes?

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

    Sorry, because of the trouble in E we decided to make it unrated.

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

      mind if I ask, what was the trouble in E? How about the prize?

      UPD: the trouble in E is due to the error in constraints. Here's the statement on the site:

      "We deeply apologize, but there was a mistake in the constraints of Problem E.

      In the English version of the statement, the constraints said "2 ≤ N ≤ 10^5", but the correct range of N is "2 ≤ N ≤ 5 × 10^4". The Japanese statement also mistakenly stated that "2 ≤ N ≤ 4 × 10^4".

      We will regenerate the data under "2 ≤ N ≤ 4 × 10^4", the lowest constraint among the three, and rejudge all solutions that was not accepted. Once again, we are terribly sorry for the inconvenience caused by this inconsistency."

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

      Looks like only 3 people were affected by the issue. Couldn't you make this round unrated for them if they got negative rating change and rate it for the rest?

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

        According to chokudai's tweet, the affected person was only seven people (Hec, hogloid, kawatea, logicmachine, nuip, E869120, TangentDay), and all of them would gain rating if it was rated. Though seeing this tweet, he proved the existence of people who affected by the mistake which is not getting AC for this problem. That's why he decided to be unrated.

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

      Hello, how can I get the Lottery prize?

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

        Be lucky.

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

          I solved D problem firstly in Beginner Contest, as i remember there is also prize money for Beginner contest(First AC).

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

            Any news DEGwer or hasi?

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

              I think the first to AC should apply to both contest, which means you have to be faster than the regular contest as well.

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

                Yeah I solved D problem of the Beginner contest faster than who solved D problem in the regular contest.

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

                  From what I see from the standings page, tourist solve D in 02:14, while you solve it in 16:05.

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

I thought all the prizes are only usable in Japan only (and spefically I thought the T-shirt is given to Japanese participants only) so I think I chose not to receive prizes back when I was registering. Is it still possible to get prizes now? I didn't remember it was stated that T-shirts can be shipped internationally and I remembered it was written that the T-shirt and energy drink was for Japan only in the registration form when I registered. (though I'm not sure about this since it was a week ago)

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

When will div1 rated? div2 has rated for a while.

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

Great contest. Learnt a lot from solving them ... Took me many months actually till I got to a level where I could do the C and D of this contest but I finally did ! :)

Here is the repository of all my solutions to the Beginner Contest.

I have also written an editorial of D here.