stefdasca's blog

Info1Cup 2024
By stefdasca, history, 3 years 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

Comments Comments (52)
| Write comment?
»
3 years ago, hide # |
 
Vote: I like it +18 Vote: I do not like it

rolandpetrean will win info cup!!!

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

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +12 Vote: I do not like it

anpaio will win infO(1)cup!

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Ahmed57 will win info cup!!

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

rolandpetrean will win info cup!!!

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +20 Vote: I do not like it

Abito will lose infocup!

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Ahmed57 will win infocup!!!

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

raduv will win info cup!!!

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

Octagons will win infocup!

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

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it -11 Vote: I do not like it

Alwm will win info cup!!!

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +14 Vote: I do not like it

dmraykhan will win Info1Cup!

→ Reply
»
3 years ago, hide # |
← 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
»
3 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

raduv will win info cup!!!!!!

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

raresh30 will win infocup!!!

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

Definitely one of the contests of all time

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

LucaLucaM will win info cup!!!

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

my handle: waipoli

my friend: barbie

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

baizhorz will win info cup!!!

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

DON_F will win info cup

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

tvladm will win infO(1)cup!

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Are there any standings ?

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

Are there live standings?

→ Reply
»
3 years ago, hide # |
← 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
  • »
    »
    3 years ago, hide # ^ |
    ← 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
»
3 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

Can anybody share the problems?

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
← 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