Yandex.Algorithm makes a comeback!

4 years ago, # |

+48

Bump, 1 day of qualifying round is left.

I found in rules that 5 points are enough to qualify but will I see the number of points assigned to each problem? The rules just say that there might be groups of tests, each worth 1-5 points.

→ Reply

halyavin

4 years ago, # ^ |

+34

Yes, the number of points is stated in the problem statement.

→ Reply

ilyakor

4 years ago, # |

+36

What happens if in a certain track less than 3 people get score required to advance to the finals? Will the 3rd place prize be divided among the ones who advance? Or do organizers have an option of lowering the cutoff?

→ Reply

Nson

4 years ago, # ^ |

From https://yandex.com/cup/rules/#algorithm

The organizer reserves the right to lower the qualifying threshold if the number of participants who have scored 5 or more points in the qualifying round is less than 500.

→ Reply

4 years ago, # |

Are we allowed to discuss the problems from the qualification round here now?

→ Reply

4 years ago, # ^ |

And is there any kind of editorial?

→ Reply

solvemproblr

4 years ago, # ^ |

there are ~14 more hours

→ Reply

4 years ago, # ^ |

Oh shoot, I didn't realize it's Oct. 25, not Oct. 24.

→ Reply

4 years ago, # |

How did people solve A. Reconstructing the alphabet and D. A reliable counter?

→ Reply

Igorjan94

4 years ago, # ^ |

D: let's maintain two multisets, first, contianing first k elements and second containing others. Let s be sum of first. Then one iteration is to:

delete first element in first;
insert s into first if s < second;
insert s into second and move smallest element from second to first if s >= second;
update s.

$$$O((r + n) \log n)$$$

→ Reply

ijxjdjd

4 years ago, # ^ |

:( I didn't expect D to have such a trivial solution so I implemented annoying $$$O(N)$$$ solution.

→ Reply

4 years ago, # ^ |

What is the $$$O(n)$$$ solution you are talking about?

→ Reply

ijxjdjd

4 years ago, # ^ |

← Rev. 2 →

It basically involved storing the first K numbers and other numbers with 2 deques each. In a merge sort like fashion we can perform each update in $$$O(1)$$$ while still maintaining the relative order. I've attached my ugly code as it might make more more sense (the code itself is $$$O(n\log n)$$$ because I was too lazy to write a merge code and instead of just sorting.

Code

package Tasks;

import Code.IO.InputReader;
import Code.Utils.ArrayUtils;

import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.PriorityQueue;

public class ReliableCounter {
    public void solve(int testNumber, InputReader in, PrintWriter out) {
        int N = in.nextInt();
        int K = in.nextInt();
        int R = in.nextInt();
        long[] store = new long[N + 1];
        for (int i = 0; i < N; i++) {
            store[i] = in.nextInt();
        }
        store[N] = (long) (1e15);
        ArrayDeque<Integer> smallestK = new ArrayDeque<>();
        ArrayDeque<Integer> stillSmaller = new ArrayDeque<>();
        ArrayDeque<Integer> untouched = new ArrayDeque<>();
        ArrayDeque<Integer> touched = new ArrayDeque<>();
        long totSmall = 0;
        for (int i = 0; i < K; i++) {
            smallestK.add(i);
            totSmall += store[i];
        }
        for (int i = K; i <= N; i++) {
            untouched.add(i);
        }
        if (totSmall <= store[0]) {
            while (R-->0) {
                long temp = totSmall;
                totSmall -= store[0];
                store[0] = temp;
                totSmall += store[0];
            }
        }
        else {
            while (R-- > 0) {
                long old = totSmall;
                int minId = minId(store, smallestK, stillSmaller);
                totSmall -= min(store, smallestK, stillSmaller);
                store[minId(store, smallestK, stillSmaller)] = old;
                if (old <= min(store, untouched, touched)) {
                    if (smallestK.size() != 0 && minId == smallestK.peek()) {
                        stillSmaller.add(smallestK.pollFirst());
                    } else {
                        stillSmaller.add(stillSmaller.pollFirst());
                    }
                    totSmall += old;
                } else {
                    if (smallestK.size() != 0 && minId == smallestK.peek()) {
                        touched.add(smallestK.pollFirst());
                    } else {
                        touched.add(stillSmaller.pollFirst());
                    }
                    totSmall += min(store, untouched, touched);
                    if (store[untouched.peekFirst()] <= store[touched.peekFirst()]) {
                        smallestK.addLast(untouched.pollFirst());
                    } else {
                        smallestK.addLast(touched.pollFirst());
                    }
                }
            }
        }
        ArrayUtils.sort(store);
        for (int i = 0; i < N; i++) {
            out.println(store[i]);
        }
    }

    long min(long[] store, ArrayDeque<Integer> i, ArrayDeque<Integer> j) {
        if (i.size() == 0) {
            return store[j.peekFirst()];
        }
        if (j.size() == 0) {
            return store[i.peekFirst()];
        }
        return Math.min(store[i.peekFirst()], store[j.peekFirst()]);
    }
    int minId(long[] store, ArrayDeque<Integer> i, ArrayDeque<Integer> j) {
        if (i.size() == 0) {
            return j.peekFirst();
        }
        if (j.size() == 0) {
            return i.peekFirst();
        }
        if (store[i.peekFirst()] <= store[j.peekFirst()]) {
            return i.peekFirst();
        }
        return j.peekFirst();
    }
}

→ Reply

4 years ago, # ^ |

Wow this was pretty trivial :/ thank you!

→ Reply

Nson

4 years ago, # ^ |

+10

For A, I wrote $$$T_5$$$ down, ABACABADABACABAEABACABADABACABA, and tried to find some useful pattern. After some time I realized that all odd positions have 'A'. With this, I can test if all even or odd positions are the same and map it to 'A'.

Then I tried to erase all 'A' from $$$T_5$$$ and I got BCBDBCBEBCBDBCB where the structure is exactly $$$T_4$$$ so we can just repeatedly do the same. After every step, I erase half of the string(either all odd positions or all even positions) so it is $$$O(n\log n)$$$. It looks like it can be done in $$$O(n)$$$, though.

→ Reply

4 years ago, # ^ |

Neat! Thanks.

→ Reply

4 years ago, # ^ |

+21

Since you erase half of the string in each step, it's $$$O(N)$$$.

→ Reply

rivalq

4 years ago, # ^ |

i used dynamic segment tree.

→ Reply

4 years ago, # ^ |

Do you mean that the leaves are the numbers and you store the number of times they appeared so far? And an intermediate node contains the sum of the numbers in that range?

→ Reply

rivalq

4 years ago, # ^ |

Yeah

→ Reply

Nson

4 years ago, # |

+26

How to solve F?

→ Reply

gnudgnaoh

4 years ago, # |

where can you see the problems after the round ?

→ Reply

gnudgnaoh

4 years ago, # |

Is there an editorial for this contest ?

→ Reply

4 years ago, # |

Please announce time of final round.

→ Reply

4 years ago, # ^ |

← Rev. 2 →

+18

I received an email with the following:

Onward to the finals, which start November 7 at 12:00 (UTC+3). The competition will last 3 hours.

I assume you are talking about the Algorithm track.

→ Reply

4 years ago, # ^ |

Thanks.

→ Reply

4 years ago, # |

+10

I think that https://clist.by/ has incorrect time and date. If I understand the email correctly, this is correct time: https://www.timeanddate.com/worldclock/fixedtime.html?msg=Yandex+Algo+Finals&iso=20201107T12&p1=166&ah=3

Please confirm that you'll be taking part in your personal account.

I just see X below algo finals there. Nothing is interactive, I can't click anything.

→ Reply

aropan

4 years ago, # ^ |

+23

I think I fixed the time on clist.by.

→ Reply

4 years ago, # |

← Rev. 2 →

I still wasn't able to reach any organizer. I got enough points in quals and even got an e-mail "Congratulations! You are in the Yandex Cup 2020 final" and yet I see only this in my profile:

Please help ;__;

EDIT: thanks to Chmel_Tolstiy for help, I'm added to finals now.

→ Reply

4 years ago, # ^ |

Lmao one less guy to beat. Git gud at computers.

Jk, I had a button under "confirmation" and when I clicked it a second button appeared under "final". It leads to a Yandex.Contest page. Maybe you blocked a script or something.

→ Reply

4 years ago, # ^ |

+20

I'm checking this issue

→ Reply

alexwice

4 years ago, # |

+25

I'm qualified, I click on the contest link from logged in area, https://contest.yandex.ru/yacup/contest/21825/enter and it says "Internal server error"

→ Reply

4 years ago, # ^ |

We have some issues I'll register you and send you a message.

→ Reply

4 years ago, # ^ |

Please, check it again

→ Reply

shdut0901

4 years ago, # |

How to solve A Need more coffee?

→ Reply

4 years ago, # ^ |

binary search over derivate

→ Reply

4 years ago, # ^ |

To expand on Errichto's idea: if you give one person $$$x_1$$$ coffee and another one $$$x_2$$$ coffee, and their derivatives at those points are not equal, that means that you could give someone a little more and someone a little less and improve your answer. Therefore, an ideal case is to give everyone an amount such that their derivatives are the same.

→ Reply

4 years ago, # ^ |

You can also do it without binsearch and with sort by $$$B$$$ as the only log-operation (maybe it can be eliminated too, not sure).

Let's take out the constant sum of $$$C$$$, ignore $$$B \le 0$$$ and sort all other functions $$$(B-Ax)x$$$. All functions with $$$x \neq 0$$$ must have equal derivatives $$$K$$$ and all functions with $$$x = 0$$$ must have derivatives $$$B \lt K$$$, since if that isn't satisfied, we can always find a pair of functions and move $$$\mathrm{d}x$$$ coffee from the one with the smaller derivative $$$d_1$$$ to the one with the larger derivative $$$d_2$$$, gaining value $$$(d_2-d_1)\mathrm{d}x$$$. All the constraints I mentioned ensure that this is a valid move. It's important that the derivative of each function nicely decreases from $$$B$$$ to $$$0$$$.

Let's pick some function + all those with greater/equal $$$B$$$ in sorted order. Then for each function, $$$B-2Ax = K$$$ ($$$\le B$$$ of our function) and the amount of coffee is $$$\sum x = \sum (B-K)/2A = \sum B/2A - K \sum 1/2A \le S$$$, which gives a min-formula for the optimal $$$K$$$. Now the answer is the max of answer so far and $$$\sum (B-Ax)x = \sum (B+K)(B-K)/4A = \ldots$$$. All sums are only over selected functions and can be computed nicely.

→ Reply

4 years ago, # |

35th place despite being nearly asleep for much of the contest (10AM on Saturday smh). Not bad.

Interesting problems. E was kinda misplaced, counting pairs with $$$a+c=2b$$$ is obvious convolution and the extra step with $$$a < c$$$ is also pretty well-known d&c; I don't see what partial solutions the second subtask offered.

→ Reply

halyavin

4 years ago, # ^ |

-10

I don't see what partial solutions the second subtask offered.

You can use bitmasks to write fast $$$O(n^2)$$$ solution.

→ Reply

4 years ago, # ^ |

+10

$$$O(N^2)$$$ for $$$N=5\cdot10^5$$$? Would anyone even risk wasting time on that? It's on the edge even for the huge TL.

→ Reply

halyavin

4 years ago, # ^ |

← Rev. 2 →

People who don't know FFT would. This is how we found out about this alternative approach. I was surprised too that it passes within half of time limit.

→ Reply

neckborov

4 years ago, # ^ |

It takes a 1-2 minutes to write simple bitset solution for the first subtask. But I couldn't pass the second subtask using STL bitsets.

I was curious so I wrote my own bitset, after some constant optimizations squeezed it to ~7 seconds (given that I'm pretty bad at optimizing code). I think if one has prewritten bitsets and no FFT they may try to attempt $$$O(n^2)$$$ solution without any huge risks.

→ Reply

Igorjan94

4 years ago, # ^ |

Can you please share your std::bitset solution?
I've also implemented it in couple of minutes, but got TL. I'm sure I'm too stupid, but don't know where

→ Reply

neckborov

4 years ago, # ^ |

← Rev. 3 →

Mb you didn't use right pragmas? Not sure which instruction sets are actually helpful I just copypasted those magic words from somewhere.

Spoiler

#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const int N = 2.5e5;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    ll ans = 0;
    bitset<N> left;
    bitset<N> right;
    int n = s.length();
    for (int i = 0; i < min(n, N); i++) {
        if (s[i] == 'c') {
            right.set(i);
        }
    }
    int j = N;
    for (int i = 0; i < n; i++) {
        right >>= 1;
        if (j < n) {
            if (s[j++] == 'c') {
                right.set(N - 1);
            }
        }
    	if (s[i] == 'b') {
        	ans += (right & left).count();
    	}
        left <<= 1;
        if (s[i] == 'a') {
            left.set(0);
        }
    }
    cout << ans << endl;
    return 0;
}

→ Reply

Igorjan94

4 years ago, # ^ |

Thank you so much, your are right, I forgot about pragmas. Got 8.984s on 32nd test without modification of my code :) It's stange I didn't get that I can use bitsets of length N / 2, not N: but even with this constant optimization TL without pragmas... Shame on me

→ Reply

4 years ago, # ^ |

I just plugged one of my SSDs into an external enclosure and pulled out some old FFT implementation. Also an option is putting all your solved problems in one place and doing grep -r . -e ' convolution\('. Gotta completely miss the idea that convolution can be used since fast implementations are everywhere.

And as our purple friend below shows, it can really be risky if you don't have ingrained constant optimisations.

→ Reply

dubina

4 years ago, # ^ |

can you elaborate on what convolution is please? (i spent the entire 3hs to come up with some kind of tree ds for E and now i see "obvious"). I'd be super grateful

→ Reply

egor_bb

4 years ago, # ^ |

Consider a simpler version of the problem, where you want to count the number of $$$abc$$$ or $$$cba$$$. Then, for $$$b$$$ at position $$$k$$$ you want to count the number of pairs of positions $$$(i,j)$$$ such that $$$i+j=2k$$$ and $$$s_i=a/c, s_j=c/a$$$.

Consider polynomials $$$p$$$ and $$$q$$$, where $$$p_i=1$$$ iff $$$s_i=a$$$ and $$$q_i=1$$$ iff $$$s_i=c$$$. In $$$pq$$$ the coefficient at $$$2k$$$ is exactly what you are looking for. So, you can create $$$p,q$$$ and multiply them with FFT.

In order to count only $$$abc$$$, you can use divide and conquer approach. Split the string in two halves, count the number of triples where $$$a$$$ is in the first and $$$c$$$ is in the second half with the described approach, and solve recursively for both halves.

→ Reply

rmn

4 years ago, # ^ |

If I'm not mistaken, convolution with FFT can be done in $$$O(N\log{}N)$$$. Does that mean that the complexity of the divide and conquer + FFT solution will be $$$O(N\log^2{}N)$$$?

→ Reply

riadwaw

4 years ago, # ^ |

yes

→ Reply

4 years ago, # |

+45

Thank you all for participating! We did the best to fix some issues and to prepare good problems.

https://contest.yandex.ru/contest/22052/ -- one can register to look at problems or to upsolve. Hope to add both rounds into gym shortly.

Congrats to winners ksun48, Um_nik and voidmax

Special thanks to tourist for great performance (there only three persons in Yandex Cup who has already been a winner twice). You are the champion in our hearts and minds ;)

→ Reply

Hamza_Hassan

4 years ago, # ^ |

Will there be an editorial ?

→ Reply

4 years ago, # ^ |

Sorry, we have not prepared it yet. We'll publish it in some time on cup's page. Now community can help you I think.

→ Reply

Petr

4 years ago, # ^ |

+13

Thanks for the great contest!

→ Reply

Egor

4 years ago, # ^ |

← Rev. 2 →

+20

91 seconds of penalty time :(

I liked the tasks though, thanks

→ Reply

4 years ago, # ^ |

← Rev. 2 →

+51

The problems were great but please don't change the rules during the contest. Some people could have waited with submitting the next problem till 2:00 for frozen standings. And maybe there should have been an announcement that tourist doesn't fight for prizes, because this might change strategy for people in the top. That being said, none of that affected me because I didn't do that well :D

btw. here are highlights of my screencast (10 minutes with commentary): https://youtu.be/ifsVDBOg39E

→ Reply

Yandex

4 years ago, # |

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

→ Reply