stefdasca's blog

Info1Cup 2024
By stefdasca, history, 9 months ago, In English

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

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

»
9 months ago, # |
  Vote: I like it +18 Vote: I do not like it

rolandpetrean will win info cup!!!

→ Reply
»
9 months ago, # |
← Rev. 3   Vote: I like it +14 Vote: I do not like it

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

→ Reply
»
9 months ago, # |
  Vote: I like it +12 Vote: I do not like it

anpaio will win infO(1)cup!

→ Reply
»
9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Ahmed57 will win info cup!!

→ Reply
»
9 months ago, # |
  Vote: I like it +2 Vote: I do not like it

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

→ Reply
»
9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

rolandpetrean will win info cup!!!

→ Reply
»
9 months ago, # |
  Vote: I like it +20 Vote: I do not like it

Abito will lose infocup!

→ Reply
»
9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Ahmed57 will win infocup!!!

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

raduv will win info cup!!!

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck to all of you :D

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Octagons will win infocup!

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Either Ahmed57 or Octagons will win info cup guaranteed

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 months ago, # |
  Vote: I like it -11 Vote: I do not like it

Alwm will win info cup!!!

→ Reply
»
9 months ago, # |
  Vote: I like it +14 Vote: I do not like it

dmraykhan will win Info1Cup!

→ Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

how many chips will be eaten at this contest?

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

→ Reply
»
9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

raduv will win info cup!!!!!!

→ Reply
»
9 months ago, # |
  Vote: I like it +2 Vote: I do not like it

raresh30 will win infocup!!!

→ Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Definitely one of the contests of all time

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

LucaLucaM will win info cup!!!

→ Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it +17 Vote: I do not like it

my handle: waipoli

my friend: Do_not_make_friends

→ Reply
»
9 months ago, # |
  Vote: I like it +9 Vote: I do not like it

BrynzaMasterZa228 will win info cup!!!

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

DON_F will win info cup

→ Reply
»
9 months ago, # |
  Vote: I like it +11 Vote: I do not like it

tvladm will win infO(1)cup!

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Are there any standings ?

→ Reply
»
9 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Are there live standings?

→ Reply
»
9 months ago, # |
← Rev. 3   Vote: I like it +16 Vote: I do not like it

day 1 standings

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

→ Reply
  • »
    »
    9 months ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it

    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.

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

      Wow that's a really nice solution! orz

      → Reply
»
9 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Can anybody share the problems?

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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

Aleks Grigoryan, representing Armenia

Mansur Mamadakhunov, representing Kazakhstan

Maksym Shvedchenko, representing Ukraine

→ Reply