LucaLucaM's blog

By LucaLucaM, history, 3 months ago,

Happy new year!!!!!!!

Inspired by this.

If you want to vote for somebody else, write a comment and I will add them asap. For now, I just added a few of the top contributors

Current standings

1. TheScrasse
4. awoo
5. BledDest
6. nor
7. WeaponizedAutist
8. errorgorn
9. Um_nik
10. vgtcross
11. maomao90
12. Qingyu
13. Geothermal
14. stefdasca
15. tourist
16. i_pranavmehta
17. kshitij_sodani
18. satyam343
19. Dominater069
20. jiangly
21. orz
22. YouKn0wWho
23. -is-this-fft-
24. BARAN_NABELSI
25. JagguBandar
26. Algorithms_with_Shayan
27. DenjellBoone
28. Lyde
29. mpb
30. sharmaharisam

And the winner is:

i_pranavmehta !!!!!!!!!!

• +68

By LucaLucaM, history, 5 months ago,

Does anybody know where I could find details about Balkan OI 2023 mirror?

• +14

By LucaLucaM, history, 6 months ago,

Will there be any other global rounds? (The last one was almost a year ago)

• +34

By LucaLucaM, history, 7 months ago,

Why aren't the rating tags added to the last contests? The last contest which has rating tags is this one which was over a month ago!

• +13

By LucaLucaM, history, 15 months ago,

For problem C, there is another O(n) solution which is similar to the one with O(nlogn). Let f[i] be the number of times the element i appears in the array a. At each test case, we make p[1], p[2], ..., p[n], q[1], q[2], ..., q[n] equal to -1. Now let's have a stack st of pairs of int, bool.

If st.top().second = 0, then p[st.top().first] has a value, otherwise (st.top().second = 1) q[st.top().first] has a value.

Now, if we iterate from n down to 1, we have the following cases:

If f[i] > 2 there is no solution. If f[i] = 2, let x and y be the positions such that a[x] = a[y] = i. We can easily precalculate these positions. If p[x] = q[x] = p[y] = q[y] = -1. Then let's set p[x] and q[y] to i. Now, we'll push in our stack the values {x, 0} and {y, 1}. Beacuse p[x] != -1, while q[x] == -1, same for y. If any of p[x], q[x], p[y], q[y] is -1. Again, we don't have a solution, beacuse we can't pus these elements such that they appear on positions x and y in the array a.

If f[i] == 1 Let x be the position such that a[x] = i. Now both p[x] and q[x] have to be -1, otherwise there is no solution (just like in the last case). We can simply set p[x] and q[x] to i.

If f[i] == 0

i should be in a position such that it's not maximum. Let st.top().first be this position. If (st.top().second == 0) then we make q[st.top().first] equal to i, otherwise we make p[st.top().first] equal to i. We do these twice beacuse i appears in two arrays (p and q). If st.size() is less than 2, then we have no solution, beacuse we can't distribute the values such that they do not appear in a.

But why is it that when we take the top 2 elements of the stack we have both permutations p and q (If they are in the same permutation, the solution is wrong). Well, how about we look at the case when we push elements in the stack. That's the case with f[i] = 2. We see that we'll put the first element in p, and the other one in q. Thus, when we'll get to the case when f[i] == 0, we'll first take the pair that we have pushed when we put the other element in q, then we'll get the element we put in p.

*forgive me for my poor english

• +23