I_love_Hoang_Yen's blog

ICPC Vietnam National 2018 Open Contest
By I_love_Hoang_Yen, 6 years ago, In English

Hi,

The ICPC Vietnam National 2018 was held recently. It is the prelim round before the ICPC Vietnam Regional 2018.

Open contest will be on Kattis. Start time: Sat — Nov 17, 2:00:00 UTC

I think it would be a good practice for teams participating in ICPC this year.

Problems are prepared by:

Standing of real contest.

Edit: It seems you cannot ask clarification on Kattis. You can ask clarification here, I will try to answer.

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

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

Will the editorial be published somewhere?

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

    I'll probably publish source code. There will only be editorial in Vietnamese (though it is not completed yet).

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

How can we solve Evolutions?

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

    Messaged you privately

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

    Our solution in the open contest was as follows:

    Precompute all geometric sequences of the form an, an - 1b, ..., abn - 1, bn where n ≥ 2, a and b are relatively prime positive integers, and the sum of all the terms is less than or equal to 106. There are only 186170 of them. Precompute how many sequences map to each sum.

    Every geometric sequence of length 3 or more can be obtained by taking one of these precomputed sequences and multiplying all terms by a positive integer scaling factor (which may be 1).

    Now, to answer a given query, we can directly enumerate how many geometric sequences of length 1 and 2 exist (1 and respectively). Factor S and compute the sum over all factors of S of the precomputed sequence map.

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

Contest starts in less than 4 hours.

Btw if you can't participate in this one, you can also create the contest yourself later on Kattis.

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

is there any editorial?

→ Reply