LucaLucaM's blog

By LucaLucaM, history, 3 months ago, In English

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
  2. SecondThread
  3. adamant
  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
  31. Adam_GS

And the winner is:

i_pranavmehta !!!!!!!!!!

Full text and comments »

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

By LucaLucaM, history, 5 months ago, In English

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

Full text and comments »

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

By LucaLucaM, history, 6 months ago, In English

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

Full text and comments »

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

By LucaLucaM, history, 7 months ago, In English

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!

Full text and comments »

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

By LucaLucaM, history, 15 months ago, In English

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.

My solution: https://codeforces.com/contest/1768/submission/188147915

*forgive me for my poor english

Full text and comments »

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