It seems that Codeforces is flooded with spam bots now. Unrated spam bots have a long history on this site. The only difference is that now they work in an automated matter, instead of people who think like bots. So why are they able to write posts in the first place?
Enough rant, Baltic Olympiad in Informatics 2023 is held in Lyngby, Denmark. Good luck to all participants!
Day 1 mirror starts in an hour. Let's discuss the problems after the contest.
How to solve day 1 problem 2? I got 66/100 with randomization.
How to solve day 2 problem 4?
I got 78/100 by just DFSing. I chose all nodes that had only 1 edge as starting nodes. For the second task where there is an intersection, I did BFS to find the most distant node from that intersection and then used DFS from that node but that only works when there is only one intersection.
Possibly wrong task? I asked about staring contest (from day 1).
Sorry, I answered the Lex person who asked about the 1st problem in today's competition. I got the staring contest 50 points. Was pretty perplexed about it, how to do it in n + 25 queries. Sorry, I should have not answered him.
I just asked for D2P1 why are you downvoting :(
Codes for which I fullscored
How to solve day2 p2?
Idk, but the first query is probably $$$(b, b), (b, -b)$$$, do you have a solution for $$$w=3$$$?
No, I have $$$k \log k$$$ query and my first queries are also that (but in two times).
I think you need to query something with $$$x$$$ or $$$y$$$ coordinates of the candidate points
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$$$
May I ask how do you do this in two queries?
Do $$$(-b,b)$$$ and $$$(b,b)$$$ in one query and the thing I described above in the other query
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...
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.
I like the problem, but I haven't competed in the open contest.
Yes, you are wrong :) I think this problem looks very fun and I take it over almost any DS problem :p
Wish 6 geom in next AGC
When will the standings be shown?
Anyone have insights for day 2 problem 3?
Can you provide hints for day1 P1?
I didn't do the day 1 contest, sorry
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.
I should learn how to read
Is that a "very standard" problem to you lol xd?
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
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
Using stl map worked just fine for me
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
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
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 ;)
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
Also why does it take so long for results to be published (in both mirror and official contest)?
How to solve Day 1 P3?
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$$$.
I think maintaining a decreasing stack in a map works better since it's either a prefix or suffix queries.
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
where can I upsolve problems?
At https://boi23.kattis.com/contests/boi23day1open and https://boi23.kattis.com/contests/boi23day2open.
error 404
If you get 404 after submission, click the dropdown menu in the top right corner with your name and click "My Submissions". The list should contain the verdict for all of your submissions.
oh, I see. thanks
For Day2 P3 can someone give example where sorted sequence isn't good, but unsorted is? Thanks in advance.
Sorted sequence always better than unsorted
But when I submitted code with considering only sorted sequence it didn't pass, but considering also unsorted did.
I submitted code with considering only sorted sequence and it passed so most probably it's bug
Oh, ok. Thanks for help
Is there going to be any editorial ?
Is it possible to submit or reach test cases of the problems? I can't submit on kattis mirror.
Are you sure your problem isn't this?
If that doesn't work, the problems should be uploaded on CSES (hopefully) in a couple of weeks.
Yes, it was this :D. Thanks a lot