Impossible bro

You will get back to PUPIL

same goal in this contest

Congrats on becoming a blue

.

As a participant i am at a loss how this information is relevant to this contest

Same :)

Me too ^_~

but "do not have a point of 1900 or higher in the rating."

Transfer it to me

You get points like you submitted it 10 minutes later.

Bruh, you solved upto F but couldn't solve C :/

Why? Because of the problem’s statement? I don't see any problems and it's a good problem.

your profile picture reminded me of Sam Hogan. Good old days

nvm, looks like it's just checking all the cases. I thought it's some classic algorithm.

You can check out my solution for e, it's just maths :)

You can just precompute prefix sums for d <= sqrt(n), and for d > sqrt(n) just brute force the answer. In the first case a query takes O(1) and in the second case its O(sqrt(n)). Preprocessing takes O(n sqrt(n)).

Basic idea is precomputing answers for all d <= $$$\sqrt{N}$$$, which can be done by prefix sums in O(N*$$$\sqrt{N}$$$). For d > $$$\sqrt{N}$$$, simply iterate and get your answer.

why have it unrated for all, just the cheaters should be eliminated

play optimally means that if there is a winnig state for player A, then player A will play in such a way that will win.

No need to check every possible move if you find a general case for wich A wins

#define bin bitset<64>

Your bitsets only store $$$64$$$ bits, not enough for $$$10^5$$$ bits.

can you explain your approach for the problem F ?

Same lol :)

I kept tripping over the math for B and C.

Then for D, I was thinking it was a heap/priority queue solution, but I couldn't figure it out.

Was hoping to make Pupil this round, but oh well :_(

I found that D is extremely likely to be fakesolved for me. I cannot find the bug since my code pass all examples and got WA on test 2.

With 1 solve and your default expected performance being 1400 you should expect a huge drop in rating. However since you're unrated, there's a +500 bonus on the first round, so your rating will still increase.

You would need to wait for the system test to end, which would happen about 18 hours from now, since there is open hacking phase.

F can be solved in O((n+q)*sqrt(n)) , by dividing in two cases d <= sqrt(n) {for which you can use suffix sums) and d > sqrt(n) for which just sum directly. However , I believe taking d <= sqrt(q) , will be more better.

you can just simulate it !

Single if is enough to compare two intervals where two players could meet.

Maybe this can help

My solution (241838398) precalculated prefix sum of a[i] and prefix sum of a[i]*i, for all $$$d\leq\sqrt{n}$$$. It's $$$O(n^{3/2})$$$ time and $$$O(n^{3/2})$$$ space, which seems to just fit the time and memory limit.

Make diagonal prefix sums, like 2d prefix sum and try each of 4 possible directions in O(1) for n*m shooting squares.

I failed to implement it in time

Bruteforce every possible starting location. To move the starting position by one cell you need to add/remove subsegments of a row, column, or diagonal. From here it's down to your implementation skills.

There is a simple solution in $$$O(nm*min(n,m))$$$.

Assume WLOG $$$n \le m$$$, The solution is: iterate over every $$$(i,j)$$$ as the start location, iterate over every row $$$x$$$ that the $$$(i,j)$$$ will reach with the operation, find the sum of the elements of the row that is in the range of the operation with simple prefix sum.

This work in O(n^2 m), if $$$m < n$$$, just rotate the input. This is code: submission

I had a slightly different solution:

Solve the problem for the down/right diagonal only. Rotate the grid four times and print the best answer over each rotation.

To solve for the down/right diagonal, notice that a shot from point (r, c) of size k is equivalent to a shot from point (0, 0) of size k + r + c, minus the combined number of targets in the first r-1 rows of that shot and the number of targets in the first c-1 columns of that shot. This can be found using inclusion/exclusion and prefix sums.

So, we can enumerate the targets in order of their Manhattan distance from (0, 0) and check starting points for the shot using a sliding window technique.

Yes, we will fix it and rejudge all affected submissions.

Perhaps overflow?

Also, vector erase method is $$$O(n)$$$, so your code is $$$O(n^2)$$$ which doesn't fit the time limit. Instead, try to use a pointer int L = 0, and increment it to simulate erasing the first position.

my approach was to club max elements of A with min elements of B and Max elements of B with min elements of A.

And there will always exist an index i before with we'll club max elements of B with min elements of A and after index i we'll club max elements of A with min elements B

I brute forced it. It gave tle on tc7

Now i want to ask that if this can be optimized using BS. BS to find that optimal index i?

Can you explain the problem F

my thought process included noticing the ternary searchable array. But since we're trying to maximise the answer, optimal points will be on either left or right ends.Therefore no need to do ternary search. just have to check ends

Want to know the same

Yeah, your solution is O(n*root(n)), but your index in vector is [arr_index][step]. If you know, vector stored continuously in memory. When you refer to [ind1][step] you need calculate offset to [ind1][0]. If say simply, need to calculate [0].size() + [1].size() + [ind1-1].size() and it's not effective. But if you start iterate by first index and after by second index it's more faster, because your elements in memory was close. You can turn your vector and get accepted 241873500. Or you can use matrix, because program know size of every lines. 241875600

Div.3 and Div.4 usually take up to 24 hours after the end of the contest before ratings are published.

me

So you're saying this is easy to understand.

Got it.

Don't worry guys, the problem is solvable by one line. the line :

Hacking means finding bugs/testcases in other people's solutions that make the code fail.

congrats and u lacked 2 points T-T

How many did you solve?

I hope I also become pupil

I think the problem here is that sorting in Java 8 has $$$O(n^2)$$$ worst case time complexity. They fixed it in later versions