Baltic Olympiad in Informatics 2023

Codes for which I fullscored

19 месяцев назад, # |

How to solve day2 p2?

→ Ответить

19 месяцев назад, # ^ |

Idk, but the first query is probably $$$(b, b), (b, -b)$$$, do you have a solution for $$$w=3$$$?

→ Ответить

19 месяцев назад, # ^ |

No, I have $$$k \log k$$$ query and my first queries are also that (but in two times).

→ Ответить

19 месяцев назад, # ^ |

I think you need to query something with $$$x$$$ or $$$y$$$ coordinates of the candidate points

→ Ответить

19 месяцев назад, # ^ |

← Rev. 3 →

+16

If you have a point with a maximum $$$x$$$ as a candidate, you can query $$$(x+d,y)$$$. Delete this candidate, and ban all distances $$$d$$$ between this query point and candidates.

if you find $$$d$$$ in the distances you can delete that candidate and the distances to the query points.

For full points, choose the smallest $$$d$$$ that is not banned and check for which candidate $$$(x,y)$$$ distance $$$d$$$ is unique for one of the points $$$(x+d,y), (x-d,y), (x,y-d), (x,y+d)$$$ which are inside the box.

You will always find it since $$$d\times k = O(k^5) < 2\times10^8$$$

→ Ответить

iLoveIOI

19 месяцев назад, # ^ |

May I ask how do you do this in two queries?

→ Ответить

19 месяцев назад, # ^ |

Do $$$(-b,b)$$$ and $$$(b,b)$$$ in one query and the thing I described above in the other query

→ Ответить

19 месяцев назад, # |

I think the easier 4 problems are very standard, but I won't say much because the participants may feel differently.

For day1 p1, maybe I'm wrong, but I don't think there is any sort of participant in the world who likes such problem...

→ Ответить

SNX03

19 месяцев назад, # ^ |

What are some key points/ concept one must know to tackle Day1, P1, in general how can it be solved for N points, it is really hard since the trade-off between choosing a good radii or moving some distance with a bad radii.

→ Ответить

jeroenodb

19 месяцев назад, # ^ |

I like the problem, but I haven't competed in the open contest.

→ Ответить

19 месяцев назад, # ^ |

+33

Yes, you are wrong :) I think this problem looks very fun and I take it over almost any DS problem :p

→ Ответить

19 месяцев назад, # ^ |

+33

Wish 6 geom in next AGC

→ Ответить

Antila

19 месяцев назад, # |

← Rev. 2 →

When will the standings be shown?

→ Ответить

snowysecret

19 месяцев назад, # |

Anyone have insights for day 2 problem 3?

→ Ответить

SNX03

19 месяцев назад, # ^ |

Can you provide hints for day1 P1?

→ Ответить

snowysecret

19 месяцев назад, # ^ |

I didn't do the day 1 contest, sorry

→ Ответить

19 месяцев назад, # ^ |

+13

Imagine the sequence backward: it starts from $$$N$$$ and it "spreads out", in the form of $$$N - 1$$$ or $$$x, y$$$ such that $$$xy = N$$$. Let $$$DP(S)$$$ be the minimum cost to create a sequence that contains the set $$$S$$$. Transitions are: Decrement one element, or divide one element into two smaller ones. Complexity estimation is tough, but using unordered_map makes it pass.

→ Ответить

kozliklekarsky

19 месяцев назад, # ^ |

← Rev. 2 →

I should learn how to read

→ Ответить

19 месяцев назад, # ^ |

+21

Is that a "very standard" problem to you lol xd?

→ Ответить

snowysecret

19 месяцев назад, # ^ |

I never thought of something like that (I was stuck on the $$$s_1 = s_2 = \dots = s_n$$$ subtasks...), so in my opinion, either I am too inexperienced or this isn't standard lol

→ Ответить

19 месяцев назад, # ^ |

Hmm, I think the hardest part is to learn how to hash vector.. I don't know. "write brute and pray it don't mess up for random reason" isn't too standard, maybe

→ Ответить

19 месяцев назад, # ^ |

Using stl map worked just fine for me

→ Ответить

19 месяцев назад, # ^ |

Lol, you chose literally the most standard and least important part of the problem and called it the hardest part xd (I assume you are aware of standard hashing of words and words<=>vectors, though standard set hashing seems even more appropriate, i.e. hash of the set is the xor of random values associated with every element of our domain)

I admit that this problem falls under "write a (seemingly?) exponential solution and pray that the number of reachable states is low" type, which is probably not the most exciting type of problems in the world, but IMHO it is much more than just that. At least for me, this looks like a random textbook backtracking problem with no sensible solution and the thought that this could potentially be solved polynomially seems completely ridiculous. During the process you need to consider states that are sets of integers of unbounded size. It is very uncommon that something like this will lead to a polynomial solution and what is more — the solution turns out to be almost-linear, i.e. $$$O(n^{1 + o(1)})$$$! Proving this (or any other polynomial bound) was not required to get 100pts, what might have caused people who solved it "yolo way" to underappreciate its beauty

Also, in order to get 100 points, you need to have some clever idea anyway and come up with some solution that cleverly forgets about irrelevant sequence parts (what may include guessing these if you choose to solve it forwards). It's not like the simple bruteforce has any chance of solving the problem. And even if you have that idea, it is highly nontrivial to understand why such solutions have any chance of solving that within reasonable time

→ Ответить

19 месяцев назад, # ^ |

Man, I got 85 point at 14 minutes after contest, and after constant optimization got 100 in 25 minutes. You should grind ds to gitgud

→ Ответить

19 месяцев назад, # ^ |

-28

Lol. I understand that this problem turned out to be easier than expected, but you seem to either misunderstood or just ignored my main point. Also, you have 3500 rating (camping on it though), so it's not like you can't solve hard problems fast from time to time. You're lucky that it did not require knowing how FFT works though ;)

→ Ответить

19 месяцев назад, # ^ |

For the handwaving, I noticed that for a set with fixed product there are not many worst case, for example 2*3*5*7*11 or 2^14. And this is a number theory stuff, random shits work

→ Ответить

kozliklekarsky

19 месяцев назад, # |

+48

Also why does it take so long for results to be published (in both mirror and official contest)?

→ Ответить

RunMIT

19 месяцев назад, # |

How to solve Day 1 P3?

→ Ответить

19 месяцев назад, # ^ |

Let $$$DP[i]$$$ be the minimum time to leave the shelter $$$i$$$, given that you intend to avoid periodical damage from there. $$$DP[i] = min(DP[j] + \lceil (x[i] - x[j]) /p \rceil (p + d))$$$ plus something.

If we can replace the fractional part to $$$\lfloor x[i] / p \rfloor - \lfloor x[j] / p \rfloor$$$, then the problem is easy. But If $$$x[j] \% p < x[i] \% p$$$ you have an error term of $$$1$$$. Therefore, those cases should be done separately.

To do this, you can maintain an RMQ with key $$$x[i] \% p$$$. If the queried part has a smaller modulo, add an error term, otherwise just do it normally. Remember to do coordinate compression over $$$x[i] \% p$$$.

→ Ответить

At https://boi23.kattis.com/contests/boi23day1open and https://boi23.kattis.com/contests/boi23day2open.

19 месяцев назад, # ^ |

+20

I think maintaining a decreasing stack in a map works better since it's either a prefix or suffix queries.

→ Ответить

Dominater069

19 месяцев назад, # ^ |

an alternate solution with a less clean implemenation but a more obvious dp definiton than ko osaga's :

define Dp[i][j] = minimum time to reach the shelter i at time t, such that t % p = j

then, there are 2 types of transitions :

1) Dp[i][(j + x[i] — x[i-1])%p] = Dp[i][j] + damage taken in interim

2) dp[i][j] = min(dp[i][j], dp[i][(j-1}%p] + 1) (because you can wait before leaving a shelter)

This gives an easy n * p solution.

To improve it, you note that the 2nd kind of transition is just a range set on dp[x] — x, and the first kind of transition is range add (ill leave you to figure out the details).

Then, you just store the dimension of p in a segment tree with range set and range add, and do n * log p updates

For full, use dynamic segment tree

→ Ответить

icosahedron

19 месяцев назад, # |

+16

where can I upsolve problems?

→ Ответить

zii.hrs

19 месяцев назад, # ^ |

← Rev. 2 →

→ Ответить