Yes, solving the full tasks is likely in the Div1 difficulty range but that does not mean that you can't enjoy the problems. The problems are split into subtasks and the easier subtasks can be closer to Div2 problems in difficulty. You can also check out problems from previous BOIs if you are trying to decide whether to participate or not.

It is in the 'contests' menu, here. It starts in three days, so you don't need to worry now.

Even solve counts should be hidden in the dashboard ideally.

I've never seen that done for a mirror contest though.

Hi, it is requirement only for the official participants, if you participate in the mirror, you don't have to worry about it.

We hope so.

Да, условия в зеркале будут на английском и русском!

The submission with highest score counts. You can try to combine "subtask-specific" code for multiple subtasks in one solution, but if you don't you gain points equal to your best submission anyways. These are the rules of the official contest, I'm not sure if cf will mirror them entirely.

GPU is irrelevant here.

One of my friend had the same problem. Make sure there's no antivirus blocking the program's execution.

Please don't discuss the problem until the end of the contest.

My approach to A goes like this, first initialize ans = n, now answer would be the smallest number between 1 and n-1, which returns 1. Now let's set a cursor named cur. Which starts in some position (let's name it x). Now we will do a binary search on [1,n-1]. If in the ith step, we do cur = cur+mid, then in the next step we will do cur = cur-mid and vice-versa. This will surely lead us to the answer. Now the fact comes, what if cur cross the bound! So we need to choose the position x cleverly. It's not hard to understand the fact that the bigger the value of C is, the bigger the moves are. So the worst case is C=N. Now we can simulate this case with a binary search to choose the position x for cur. The interesting fact about this approach is mid becomes too large or too small to intersect with previous queries! I hope this clears the doubt!

Also is B just checking that the triangle contains the origin?

roughly speaking, that's exactly that.

I did what you say in B but it fails first subtask. Did you pass it with that idea?

Problem A : I tried it binary search, I guess the idea is correct, but the implementation was hard.

We are sure that C is between 1 and N, inclusive so let the lower_bound = 0 and upper_bound = N

You need to ask the middle value of lower_bound (0) and upper_bound (N)

P = (0 + N)//2

there are 2 possibility:

1. if the result is "1", you set the upper_bound to P and recur.

2. if result is "0" ,you set the lower_bound to P and recur.

so finally the upper_bound and lower_bound will be the same, which is the base case, the

C = lower_bound = upper_bound

NOT SURE about it

This happened to me on A. I guess test cases are weak.

I had the same problem for my first submission.

It seems that only the first two subtasks contain corner cases like $$$S_f = P_f = 0$$$ (two zeroes and one non-zero number). I had a small bug with it.

it could be used, but it's not needed. you can use DSU to do that. Also, myapproach for 4th subtask had time complexity $$$O(m\cdot L\cdot \alpha(n))$$$ where $$$\alpha(n)$$$ is the inverse of Ackerman and $$$L$$$ is the amounf of different $$$l_i$$$, and it gave TLE.

I tried to, but it was too slow (was using java tho).

It doesn't pass in c++ too.

The time limits were quite tight to distinguish between Mo's algorithm and the faster solution.

I know a solution with $$$O(N*\sqrt{Q}*\alpha(N))$$$ which uses dynamic dsu + mo's algorithm. I don't think it will pass the TL though.

If you have link cut tree template, then it can be solved quite easily: Go forward keep only important edges. Then go backward, remove those edges one by one, also maintain a pointer at the end. Try to add edges from the end that won't produce an odd cycle, possible remove some edges that can be removed when going backward.

You were on the right track. This problem can be solved in $$$\mathcal{O}(M \log(M) \log (N))$$$ with Divide and Conquer + DSU with rollbacks. Keeping the intervals as $$$[1, l_i) \cup (r_i, M)$$$ is more convenient, as it avoid the issue where edges that were added on the right and are removed on the left.

You are querying the same color multiple times, this is not allowed.

I cannot see your submission.

Yes, it is now.

It was voted by participants to keep the scoreboard hidden during the contest: https://codeforces.me/blog/entry/80321?#comment-665679

Note, though, that a relative comparison of problem difficulties doesn't really apply here (and competitions of similar format) since each problem contains multiple subtasks of varying degrees of difficulty. So in essence, you already know before-hand that focusing on subtasks is going to be easier than tackling the full problems.

Especially, for the case that multiple sulutions exist, how to find the minimal one?

I solved problem A today, by this method. First I choose a node to begin, and called it value A. Then in a DFS I updated every node to have an equation like k*A+c. k was always either 1 or -1. When a node had multiple equations, you could solve for A. When there were no restrictions on A, you had to find the best A. I did this by finding the median of the all the k*c.

For every component, choose an arbitrary vertex and let its weight be $$$x$$$. Then all vertices in that component has weight of the form $$$ax+b$$$ for some coefficients $$$a$$$ and $$$b$$$.

Our goal is to minimize

which is well-known that the best $$$x$$$ we should choose is the medium among $$$x_i = -b_i/a_i$$$.

Well, not exactly. In the problem you linked we are forced to use pairs (I at least found it non-trivial to prove we'll always want to swap pairs only, except for the last vertex).

Also here you need to reconstruct the solution which is also not exactly trivial (but not very hard either).

for problem B2 (second subtask) I made this greedy algorithm that seems work but it gave WA: pick the two farthest nodes, move from one to the other and the reverse, erase them from the tree and continue doing that. Stop when there are $$$0$$$ or $$$3$$$ nodes. In case when there are $$$3$$$ nodes, these nodes will form a chain, so move the first to the second, the second to the third and the third to the first.

Any case that breaks it??

It fails in test case 21.

https://www.spoj.com/problems/HOLI/

We have now published the analysis for Day 2.

Let's pretend everyone was protesting in unity against geometry ;)

Well, now that you've started it, I'll share a video I made yesterday as a joke. Hopefully, I won't offend anyone.

On a more serious note, I think that perhaps it wasn't an ideal task for subtask-structure. What I mean by that is I think it was way harder than usual to score points even on the first subtask (it's reasonable if you notice simplification to 2D, but if you keep working in 3D, good luck). Additionally, long testing queue during the first onsite day, made it a bit more difficult as well. Finally, pre-written code may have helped a lot in this task as well, so comparing onsite results to online mirror isn't exactly fair in my opinion either. So, while this is definitely an amusing situation, it was the hardest task in the set in my opinion, and I'm not overly surprised, especially since I feel that a lot of people kept working on other tasks as well instead. Which maybe, given the difficulty to score even some points here, was in most cases absolutely the right decision.

This diff would've yielded me 43p. Not even geometry, just a stupid bookkeeping error :P And since it uses floats, I got 100p in analysis after a little tweaking.

Not necessarily blaming the queue though, I got this done at the very end.

Why did you "set a problem" that you had already "seen/solved both parts multiple times" of before? Was that for a non-"serious competition"?

Jokes aside, all problems at BOI go through a review process involving multiple people, both from the official jury and the representatives of all delegations, taking into account aspects like difficulty, originality, amount/quality of meaningful subtasks, as well as all that in the context of the other problems. The problem in question may not be the most original one (heck, truly original problems are so rare tbh) but it was decided to (and ultimately turned out to) serve its purpose well.

+1

It's available now.

Keep in mind that there may be some differences between onsite and Codeforces tasks (e.g. colors became multi-test-case-per-input problem).