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

Info1Cup 2024
Автор stefdasca, история, 4 месяца назад, По-английски

Info1Cup, the first junior olympiad of 2024 is starting today with its competition days taking place tomorrow and on sunday.

I invite you all to write the codeforces handles of the participants and maybe even predict potential winners or high performers.

After the contest days, let's also discuss the problems here.

Good luck to all participants.

UPD1: The first day should end anytime from now, so let's discuss ideas for the problems that were given.

UPD2: The second day should end anytime from now, so let's discuss ideas for the problems that were given.

Congratulations to everyone and especially to the winners.

Here are the results: Link

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

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

rolandpetrean will win info cup!!!

→ Ответить
»
4 месяца назад, # |
← Rev. 3   Проголосовать: нравится +14 Проголосовать: не нравится

rolandpetrean will win infocup!!!!!!!!

→ Ответить
»
4 месяца назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

anpaio will win infO(1)cup!

→ Ответить
»
4 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Ahmed57 will win info cup!!

→ Ответить
»
4 месяца назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

I've heard they'll finally allow generating functions for model solution

→ Ответить
»
4 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

rolandpetrean will win info cup!!!

→ Ответить
»
4 месяца назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

Abito will lose infocup!

→ Ответить
»
4 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Ahmed57 will win infocup!!!

→ Ответить
»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

raduv will win info cup!!!

→ Ответить
»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Good luck to all of you :D

→ Ответить
»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Octagons will win infocup!

→ Ответить
»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Either Ahmed57 or Octagons will win info cup guaranteed

→ Ответить
»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Ahmed57 and Octagons fan here <3 Good luck!! <3

→ Ответить
»
4 месяца назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

Alwm will win info cup!!!

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

dmraykhan will win Info1Cup!

→ Ответить
»
4 месяца назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

how many chips will be eaten at this contest?

for devoted fans, we can also let the chips identify as something else too

→ Ответить
»
4 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

raduv will win info cup!!!!!!

→ Ответить
»
4 месяца назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

raresh30 will win infocup!!!

→ Ответить
»
4 месяца назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

Definitely one of the contests of all time

→ Ответить
»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

LucaLucaM will win info cup!!!

→ Ответить
»
4 месяца назад, # |
← Rev. 2   Проголосовать: нравится +17 Проголосовать: не нравится

my handle: waipoli

my friend: Do_not_make_friends

→ Ответить
»
4 месяца назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

BrynzaMasterZa228 will win info cup!!!

→ Ответить
»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

DON_F will win info cup

→ Ответить
»
4 месяца назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

tvladm will win infO(1)cup!

→ Ответить
»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
4 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Are there any standings ?

→ Ответить
»
4 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Are there live standings?

→ Ответить
»
4 месяца назад, # |
← Rev. 3   Проголосовать: нравится +16 Проголосовать: не нравится

day 1 standings

also, what is the solution for B(xorsecv) ?

→ Ответить
  • »
    »
    4 месяца назад, # ^ |
    ← Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

    Here is how I did it. First, the $$$O(n^2)$$$ solution: the contribution of $$$a_i$$$ to the sum will be $$$(\sum_{j=0}^i (a_i \oplus j)^p) \cdot (n - i)$$$.

    To optimize to $$$O(n log n)$$$, I defined $$$f(l, len, x)$$$ to be $$$\sum_{i=l}^{l+len} (x \oplus i)^p$$$. The answer will be sum of $$$f(0, i, a_i) \cdot (n - i)$$$. Now to calculate it:

    First precalculate something like $$$pref_i=0^p+1^p+...+i^p$$$. Say the highest bit of $$$len$$$ is $$$B=2^b$$$. If $$$B \gt x$$$, then we will be able to get all numbers smaller than $$$B - 1$$$, which is $$$pref_{l + B - 1} - pref_{l - 1}$$$. After that we recurse and add $$$f(l + B, len - B, x)$$$.

    Now for when $$$B \le x$$$. Let's say $$$y$$$ is equal to the number formed from only the last $$$b$$$ bits of $$$x$$$.

    • If we choose to have bit $$$b$$$ turned off, then we will be able to get all numbers smaller than $$$B-1$$$, but offset by $$$x-y$$$, so $$$pref_{x-y + l + B} - pref_{x-y+l-1}$$$.
    • If bit $$$b$$$ is turned on, then we add $$$f(l + x-y, len - B, y)$$$ (you can only influence $$$y$$$, and the bits in $$$x-y$$$ are fixed).

    Each time you recurse you remove the highest bit of $$$len$$$. So it will be $$$O(log n)$$$ at most.

    → Ответить
»
4 месяца назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Can anybody share the problems?

→ Ответить
»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
4 месяца назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Congratulations to the three winners, each of them obtaining 471 points:

Aleks Grigoryan, representing Armenia

Mansur Mamadakhunov, representing Kazakhstan

Maksym Shvedchenko, representing Ukraine

→ Ответить