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

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

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
  • Проголосовать: не нравится

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

rolandpetrean will win info cup!!!

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

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

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

anpaio will win infO(1)cup!

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

Ahmed57 will win info cup!!

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

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

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

rolandpetrean will win info cup!!!

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

Abito will lose infocup!

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

Ahmed57 will win infocup!!!

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

raduv will win info cup!!!

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

Good luck to all of you :D

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

Octagons will win infocup!

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

Either Ahmed57 or Octagons will win info cup guaranteed

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

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

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

Alwm will win info cup!!!

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

dmraykhan will win Info1Cup!

»
5 месяцев назад, # |
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

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

raduv will win info cup!!!!!!

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

raresh30 will win infocup!!!

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

Definitely one of the contests of all time

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

LucaLucaM will win info cup!!!

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

my handle: waipoli

my friend: Do_not_make_friends

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

BrynzaMasterZa228 will win info cup!!!

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

DON_F will win info cup

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

tvladm will win infO(1)cup!

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

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

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

Are there any standings ?

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

Are there live standings?

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

day 1 standings

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

  • »
    »
    5 месяцев назад, # ^ |
    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