Baltic Olympiad in Informatics 2023

Codes for which I fullscored

19 months ago, # |

How to solve day2 p2?

→ Reply

19 months ago, # ^ |

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

→ Reply

19 months ago, # ^ |

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

→ Reply

19 months ago, # ^ |

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

→ Reply

19 months ago, # ^ |

← 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$$$

→ Reply

iLoveIOI

19 months ago, # ^ |

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

→ Reply

19 months ago, # ^ |

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

→ Reply

19 months ago, # |

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...

→ Reply

SNX03

19 months ago, # ^ |

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.

→ Reply

jeroenodb

19 months ago, # ^ |

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

→ Reply

19 months ago, # ^ |

+33

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

→ Reply

19 months ago, # ^ |

+33

Wish 6 geom in next AGC

→ Reply

Antila

19 months ago, # |

← Rev. 2 →

When will the standings be shown?

→ Reply

snowysecret

19 months ago, # |

Anyone have insights for day 2 problem 3?

→ Reply

SNX03

19 months ago, # ^ |

Can you provide hints for day1 P1?

→ Reply

snowysecret

19 months ago, # ^ |

I didn't do the day 1 contest, sorry

→ Reply

19 months ago, # ^ |

+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.

→ Reply

kozliklekarsky

19 months ago, # ^ |

← Rev. 2 →

I should learn how to read

→ Reply

19 months ago, # ^ |

+21

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

→ Reply

snowysecret

19 months ago, # ^ |

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

→ Reply

19 months ago, # ^ |

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

→ Reply

19 months ago, # ^ |

Using stl map worked just fine for me

→ Reply

19 months ago, # ^ |

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

→ Reply

19 months ago, # ^ |

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

→ Reply

19 months ago, # ^ |

-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 ;)

→ Reply

19 months ago, # ^ |

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

→ Reply

kozliklekarsky

19 months ago, # |

+48

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

→ Reply

RunMIT

19 months ago, # |

How to solve Day 1 P3?

→ Reply

19 months ago, # ^ |

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$$$.

→ Reply

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

19 months ago, # ^ |

+20

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

→ Reply

Dominater069

19 months ago, # ^ |

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

→ Reply

icosahedron

19 months ago, # |

+16

where can I upsolve problems?

→ Reply

zii.hrs

19 months ago, # ^ |

← Rev. 2 →

→ Reply