[Discussion Thread] RMI 2020

→ Обратите внимание

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
12:00:24
Зарегистрироваться »

*есть доп. регистрация

→ Трансляции

Leetcode BiWeekly Contest 144 — Solution Discussion

Shayan

До начала 13:30:22

Codeforces CodeTON Round 9 (Div 1 + Div 2) — Solution Discussion

Shayan

До начала 15:00:22

Всё →

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

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

[Discussion Thread] RMI 2020

Автор lior5654, история, 4 года назад, По-английски

Opening this thread to discuss Romanian Masters of Informatics (RMI) 2020 Problems & Results.

Hope everybody had a great competition!

http://rmi.lbi.ro/rmi_2020/

rmi, rmi2020, discussion, olympiad

lior5654
4 года назад
35

Комментарии (35)

Написать комментарий?

lior5654

4 года назад, # |

← Rev. 3 →

+23

My results:

brperm — 83

floppy — 27

peru — 49

total (d1) — 160 (49th/198th)

zerosum — 61

nicelines — 11

arboras — 24

total (d2) — 96 (58th/198th)

total — 256 (??th/198th)

→ Ответить

shejibri

4 года назад, # ^ |

+13

Wait, How do you know your place today?

→ Ответить

lior5654

4 года назад, # ^ |

+13

One of my coaches sent me the table from the system some time after the contest ended. ofcourse, second day is not final because of jury. these are unverified results, but most likely wont change.

→ Ответить

lior5654

4 года назад, # ^ |

+15

Update: 20 points off from silver medal -_-

High bronze.

→ Ответить

TheScrasse

4 года назад, # |

← Rev. 3 →

My results:

brperm — 0
floppy — 100
peru — 0
total (d1) — 100

zerosum — 22
nicelines — 88.76
arboras — 24
total (d2) — 134.76

total — 234.76

→ Ответить

lior5654

4 года назад, # ^ |

88.77 on nicelines is megaorz

btw what happened on the first day that made you not take testcases on q2 and q3?

→ Ответить

TheScrasse

4 года назад, # ^ |

I was trying to get 100 on brperm, but I failed.

→ Ответить

lior5654

4 года назад, # ^ |

+21

That problem is fucked up, 83 is n^2 bruteforce, broken testcases

→ Ответить

TheScrasse

4 года назад, # ^ |

I knew it only at the end of the contest.

→ Ответить

lior5654

4 года назад, # ^ |

how to 88.77 on nicelines

→ Ответить

TheScrasse

4 года назад, # ^ |

← Rev. 4 →

Let $$$k = 20001$$$.
The graph of $$$query(k, y+1) - query(k, y)$$$ contains $$$n+1$$$ horizontal segments; a new segment begins if there's a line that goes through $$$(k, y)$$$. So you can get all $$$a[i]$$$ and $$$b[i]$$$ with binary search on the endpoints of those segments. That's around $$$3000$$$ queries.

→ Ответить

dorijanlendvaj

4 года назад, # ^ |

+25

It's not about 1500 queries. My solution uses 2400 queries and gets about 93 points. My idea is the same as yours but I did some constant factor optimizations on the binary search which allowed me to squeeze 5 more points.

→ Ответить

taulant

4 года назад, # |

+27

My results are:

brperm 83, floppy 100, peru 0 -- 183 day1

zerosum 100, nicelines 0, arboras 24 -- 124 day2

307 total

→ Ответить

lior5654

4 года назад, # ^ |

+13

floppy 100 with a cartesian tree? I wish I knew what that is before the contest. on the go I invented a similar concept but wasn't full and good enough :/

→ Ответить

TheScrasse

4 года назад, # ^ |

← Rev. 2 →

+13

I generated the max stack (1 = insertion, 0 = removal), then a "valid" permutation with a topological sort on the graph generated by the max stack.

→ Ответить

lior5654

4 года назад, # ^ |

I thought of saving the results of running maz stack but that was nlogn. not the insertions and deletions themselves. smart idea!

→ Ответить

taulant

4 года назад, # ^ |

+13

To save the data in 2n bits, I found the highest value and used it as the root of a tree, then I divided the array recursively into left and right subtree, always choosing the highest value of the interval. Then, for each node of the tree in bfs order, I would save two bits, one is 1 if the node has a left child, the other is 1 if the current node has a right child. I would then reconstruct the tree, knowing that each node has a higher value than its children and its in-order traversal gives the original order of the array. For range max queries, I used a sparse table. I can send you a picture of the code if you want.

→ Ответить

Sedmoklasnikut

4 года назад, # |

← Rev. 4 →

+43

My results:

bperm — 83; floppy — 28; peru — 18; total(d1) — 129

zerosum — 22; nicelines — 11; arboras — 24; total(d2) — 57

total — 186 (bronze)

Just to clarify — I am 14 years old (7th grade)

→ Ответить

johutha

4 года назад, # |

← Rev. 3 →

+36

So during the contest I came up with this solution for Arboras. However, I couldn't code it in time, so I don't know whether it's correct of not, so if someone could comment who knows the solution, would be appreciated.

First, it's not hard to see that all the values that change in a query lie on a path from the changed edge upwards. So let's apply heavy-light decomposition on the tree. For each chain, we keep a set of positions, where the longest path to a leaf starting from this vertex doesn't go through the heavy edge. Let's call this positions breaking-points.

When updating a vertex, go upwards from the changed edge. Call a vertex interesting if it is either the vertex where we change the chain when going upwards, or if it's a breaking-point. We can calculate the value-change on this points seperately. The value-change of the points between these interesting vertices can be updated easily, since the value-change of all of them is the same.

There are $$$\mathcal O(log \, n)$$$ interesting vertices of the first type on the path upwards. But we may encounter many vertices of the second type. Now comes the insight: Each time we encounter a point of interest of the second type, we either remove it from the set, or there isn't any value to change above it (since there is another longer path we could take). In the beginning, there can be at most $$$\mathcal O(n)$$$ breaking points, and in each update, we only add at most $$$\mathcal O(log\,n)$$$ breaking points, because we only change the chain (of the heavy-light decomposition) at most $$$\mathcal O(log \, n)$$$ times, and we can only add a breaking-point in an update when switching the chain. So, amortized, we check at most $$$\mathcal O(n \, log \, n)$$$ interesting points. With a segtree, the values can be maintained in $$$\mathcal O(log\,n)$$$, giving us a total complexity of $$$\mathcal O(n\, log^2 \, n)$$$

→ Ответить

dorijanlendvaj

4 года назад, # ^ |

+39

An arguably easier way to get 100 on Arboras: Code an $$$O(q \cdot height)$$$ with various constant factor optimizations and breaks, most notably using hld dfs order to only have $$$O(n$$$ $$$log$$$ $$$n)$$$ cache misses and the unroll loops pragma. My first submission that wasn't WA only TLEd on test 8 of the last subtask, which I fixed by removing 1 array and slightly reducing the number of operations I do which allowed me to pass it in 2.871 s.

→ Ответить

aZvezda

4 года назад, # |

← Rev. 2 →

+24

How to solve day1 problem3 Peru?

→ Ответить

lior5654

4 года назад, # ^ |

-10

If you know a data structure that supports:

insertion from 1 aide (like a stack) deletion from both sides (like a doubly linked list) max query

in O(q) then I have 100

→ Ответить

tvan

4 года назад, # |

how do you solve day2 problem1 ZeroSum?

→ Ответить

Kaey

4 года назад, # ^ |

+12

First of all, you must notice that the subarray between $$$a_i$$$ and $$$a_j$$$ has sum zero iff the sum of the elements between $$$a_1$$$ and $$$a_{i-1}$$$ is equal to the sum of those between $$$a_1$$$ and $$$a_j$$$. Hence we can reduce our problem to an easier one. We replace our array with its prefix sums array, i.e. $$$b_i=\sum_{j=1}^ia_j$$$. What we must do now is, for each interval, finding the maximum amount of pairs $$$f_i,s_i$$$ such that $$$b_{f_i-1}=b_{s_i}$$$ and the segments $$$f_i,s_i$$$ and $$$f_j,s_j$$$ don't intersect for every $$$i,j$$$ such that $$$i\neq j$$$. This is a quite known problem and can be solved greedily, by simply taking the pairs of equal elements which has the leftmost right element and repeating this process over and over until we reach the end of the queried segment. Although, this has a time complexity of $$$O(N)$$$ for each query, which gives TLE. We can speed up this procedure. For every index $$$i$$$ we store the minimum index $$$j>i$$$ such that $$$b_i = b_j$$$. This can be done easily in $$$O(NlogN)$$$ using a set. What we can do next is building a sparse table on those values and binary search the answer for each query. Unfortunately, using a standard sparse table causes MLE, so you must use a sparse table with a base greater than 2 (My solution using base 4 uses 20.0 MiB of memory, which is just enough to get 100/100). If you have any doubt feel free to ask.

→ Ответить

tvan

4 года назад, # ^ |

Thanks, had a similar idea but somehow messed it up for the query part

→ Ответить

Matteo.Verz

4 года назад, # |

+24

You never know true pain until you get 13 on bperm because you didn't try N^2 for subtask 2

→ Ответить

Magi

4 года назад, # ^ |

+13

Missed bronze because of that =(

→ Ответить

Pety

3 года назад, # ^ |

I feel you my man

→ Ответить

oleh1421

4 года назад, # |

+29

My results: floppy — 28
bperm — 100
peru — 49
zerosum — 100
nicelines — 11
arboras — 100
total — 388

Personal opinion: I like problem bperm, but it completely ruined the contest. There are way to many people, who solved it with some O(N^2) solution + optimizations for subtask 3.

→ Ответить