upd.: why so many downvotes?(

New ratings should soon be returned

More like :^

I am really struggling to solve bitwise questions. Any tips?

Well, I guess that xor is an uncommon topic for beginners, so appearing on div2A would be a bit scary to them. But I don't think they were that bad, after a few rounds I got used to those problems and it was pretty fun solving them too

Don't even see how you needed XOR here — there's only 3 cases:

• 2 opposite corners, so the answer is 2;
• All spaces are empty, so answer is 0;
• Answer is 1 otherwise.

Edit: I misremembered the question, the answer is 2 only if all the spaces are filled.

<2100

That means your code is not correct.

Can it be solved by heap?? just asking

If $$$\lfloor \dfrac{i}{a_i} \rfloor$$$ is equal to $$$b_i$$$, it means that $$$a_i$$$ should be in some segment of integers. For each $$$i$$$, generate this segment, and then match each value from $$$1$$$ to $$$n$$$ with a segment greedily.

Looking at the solves, probably my solution is way too complicated and there is something simpler..

First decompose each element into the ranges it can exist if the answer is k (which is i+1 to n if it is 0, i/(k+1) + 1 to i/k otherwise).

Keep these ranges grouped by starting position (and also sort by length). Now, for the i'th turn do the following

1: Add the smallest range by length from the i'th group (i.e. all ranges that are of the form [i,?]) to your processing group. 2. Remove the smallest range from your processing group. Place the index of this range at position i 3. Whichever group the range you just removed was from, add it's smallest range to your processing group.

Submission:

163296621

Dang really nice solution.

Hmm maybe it would be easier just binsearching min and max for each segment :D?

x>=k*y and x<=k*y+y-1 if x/y=k. Using these two inequalities you can find range of y.

I had zero trouble with the formulas, but I struggled for ages with coming up with some range assignment algorithm...

Yeah so you know that floor(i/ai) = x, i/ai <= floor(i/ai), i/ai <= x, ai <= i/x,

floor(i/ai) + 1 > i/ai, x +1 > i/ai, ai > i/(x+1)

and that's how you do it

$$$\lfloor{\frac{i}{a[i]}} \rfloor$$$ is $$$i \; div \; a[i]$$$. And $$$i \; div \; a[i]$$$ is the $$$max$$$ number $$$v$$$ such $$$a[i] \cdot v \le i$$$, but $$$a[i] \cdot (v+1) > i$$$.

Couldn't find the formulars but managed to binary search it :3.

Advanced Binary Search (like Book Allocation Problem) will do for C.

Binary Search Approach will work

it's not too easy to implement — eg i was thinking about it for a half an hour, then i just wrote binsearch, which was really easier than the greedy solution

Assign all 1-tasks to the workers, maintain the assigned tasks per worker in a list.

Also maintain the last finish time of each worker in a queue, or sorted set.

Then take first/earliest worker and last/latest worker from the queue, and asign a task from the latest to the earliest, put both again with the updated values onto the queue.

Repeat until first and last differs by at most 2.

Just assign all workers to tasks they can do with max efficiency.

Now place them all in set. As long as largest element and smallest in set differ by >=3

Reduce 1 from your largest element

add 2 to your smallest element

(you're simulating giving a task from one worker to another)

In the end output the largest element in set

If you have a multiset of workers' task durations, repeat the following until the min duration >= max duration - 2: subtract one hour from the highest duration, add two hours to the lowest.

This happens because of the integer overflow.

Oh, I'm really sorry about that. I thought to make it 512MB but when I was calculating something like "5000^2 integers", I found that it is only about 100MB, so I decided that even two such matrices will fit and I decided to keep the memory limit as it is. :(

UPD: Though, I just replaced all int matrices with short matrices, and your solution passed with 157MB peak memory used. I'm not blaming you, just informing that you could do something like that in the future. Because, for example, in this problem you couldn't meet any numbers greater than $$$O(n)$$$, so short is more than enough.

Consider the segments in sweepline fashion. In all the segments that are currently open you should assign the current value to the one that closes the earliest. If you assign values in the manner you said then this wouldn't happen.

what if n=3 and the ranges are (1,3) (1,3) (2,2)? I had also encountered the same problem but then realised that you have to sort by right boundary. I may still FST tho idk.

range of values is [ (i/(a[i]+1)) + 1, i/a[i] ] or ( i/(a[i]+1), i/a[i] ]

1
7
0 0 0 2 0 6 2

Should be [X,X,X,2,X,1,3] (remaining numbers can be anything greater than their index)

You should actually say that to your brain :)

around 1400 I believe.

1300

Binary Search the Answer. See this and this

Binary search is fine but overcomplicated.

Think of it more simply. Assign all tasks to the skilled person initially. Under what circumstances can you continue to make improvements?

To give a hint: if someone is idle for 3 hours and there are tasks ongoing in that time, they could have done a 2 hour task and taken it from someone else.

You guys just downvote for my protesting the contest??

bruh imagine you're a vendor and tell that the project can be finished in 343599 hours

and then the next vendor finish it in 2 hours xD

The problem are actually the large test cases since q and p can become very large. Make q and p long long and your solution should be correct.

your rest can be negative number, and it can be less than INT_MIN.

Had a similar error, try this:

3 7
1 2 2 2 3 3 3

1

2 6

1 1 1 2 2 2

Your code gives 4, answer is 3.

1

5 15

5 5 5 5 5 5 5 5 5 5 1 2 3 4 5

Correct answer: 5. Your answer: 6.

You fail this case:

1

6 9

1 1 1 2 2 2 3 3 3

Ans = 2, yours = 3

https://codeforces.com/contest/1701/submission/163281220 Here is my shitty but AC for now solution. Binary search is probably easier but I still can't solve any binary search problems that aren't leetcode easy so it never occurred to me during the contest(should probably start practicing it lol) plus I am addicted to using priority queue. I saw some people use multiset though which also seems way easier. I initially tried multiset but switched to priority queue. It is not the multiset fault though, I just had wrong idea at the time. I also don't know how to analyze algorithms but I am pretty sure my solution is $$$O(n \cdot \text{log} N)$$$ which is fine for 200000. Hopefully I don't get hacked lol.

**Update : ** I resubmitted my solution with comments and removed some extraneous code which should make it clear what the code is doing.https://codeforces.com/contest/1701/submission/163322218

This, This, and This

Думай быстрее) В целом это вполне нормальная ситуация. Невозможно идеально балансировать по сложности каждый раунд. В этом, вероятно, Д была сложнее, чем должна быть. Хотя по количеству сдавших этого не скажешь.

Ну и вообще это особенность формата ICPC.

One of the implementations stores a $$$3 \times 3$$$ matrix in each segment tree node, and the operations are like "multiply by a $$$3 \times 3$$$ matrix on segment". I decided I didn't want to cut it off.

1. There is one useless operation type.
2. It`s better (general) to delete symbols while going right to left not left to right.
3. You can solve task with O(n^2).