Thank y'all so much for participating! Code will be added soon.
cpp
When comparing two numbers that are initially not equal, the only way they can become equal after some number of operations is if at least one of them has an operation performed on it when it is $$$ \lt 2$$$.
If two elements are equal at some point, they'll be equal no matter how many more operations are performed. Therefore, it suffices to look at the end behavior of each element.
If a $$$-1$$$ is in between two $$$1$$$s, it would only hurt the answer to make it a $$$1$$$.
If a $$$-1$$$ is not in between two $$$1$$$ s, the $$$-1$$$ would only be included in a subarray satisfying the conditions if it was an endpoint.
cpp
If there is only one $$$0$$$ in the array, then exactly one set will have a mex greater than zero
$$$MEX(A) = MEX(B), MEX(C) = 0$$$ satisfies the constraints.
cpp
2259E - Treasure Map Destruction (Constructive Version)
If an element $$$x$$$ at index $$$i$$$ is not equal to $$$-1$$$, there must be a treasure at either island $$$i + x$$$ or $$$i - x$$$
If an element $$$x$$$ at index $$$i$$$ is not equal to $$$-1$$$, there must no treasures in the exclusive range of indices ($$$i + x$$$, $$$i - x$$$)
cpp
2259F - Binary Bubble Sort Inversions
Look at performing some bubbles and reverse bubbles on small arrays. How many elements are moved?
A bubble will result is the leftmost 1 being moved all the way to the right. Similarly, a reverse bubble will result in the rightmost 0 being moved all the way to the left.
Since prefix zeroes and suffix ones don't matter, if we continuously remove them, then a bubble removes the last element of the array and a reverse bubble removes the first element of the array. Is there a way to remove the first and last elements of an array in constant time?
cpp
Ignoring indexes 1 and $$$n$$$, if we remove index $$$i$$$, if we perform an operation on index $$$j$$$, all elements between $$$[i, j]$$$ will also have an operation performed on them.
If we remove index $$$i$$$, and we have to reduce the element at index $$$i+1$$$, $$$i+2$$$, etc, what will we subtract it to?
cpp
2259H - Treasure Map Destruction (Counting Version)
Read the solution to problem E first
Let's consider all locations that we have not restricted: we can separate them into 3 categories: the position is forced to be a treasure, the position has no undestroyed that depend on it, and all other positions.
The islands that are considered "non-restricted" form a chain of locations, with each non-restricted chain having a treasure between them. What must be true of the locations in this chain such that no condition is violated?
For every pair of adjacent locations, there must be at least one treasure at one of those locations.
cpp
Auto comment: topic has been updated by nik_exists (previous revision, new revision, compare).
good contest!
tysm!
nice round thanks !
tysm!
good problems, C was kind of annoying to implement
I personally think C wasn't so annoying
Amazing round. Ty king
tysm!
Maybe you are missing the space after
[tutorial:2259B]?It works for me:
nik_exists
yep, that was it, thank you so much!
W contest
2259E code ... cpp :skull:
model actually isn't that long
The editorial isn't working because it doesn't use the announcement format /j
C is harder than D. But still orz round by nik_exists
For me D is harder
Here is my two agree
E can be solved with 2-SAT
Can you explain more
i thought of 2SAT and then went for other solution (because i think we don't need 2SAT at all).
Basically if a[i] == 0, then there should be treasure at position i. Otherwise if a[i] > 0, there should be a treasure at i — a[i] OR i + a[i]. So you just need to add a OR clause and let 2SAT solve it.
if i — a[i] <= 0. Then i + a[i] MUST be treasure. if i + a[i] > n. Then i — a[i] MUST be treasure. otherwise either of them can be a treasure.
It Was a fun contest , but i got struck at E for almost the whole contest :-(
I cared too much about my rating. That's why I wanted to solve C as fast as I could and made many silly mistakes
Felt that.Same thing happened to me on D
Thanks for the contest! I enjoyed it
should i try to upsolve E? current rating is 1072 and max is 1100.
Yes
good cumtest
Nice contest!
i dont know why i found it hard to understand E statement otherwise amazing round!
Please elaborate more on the editorial of $$$E$$$.
let the given array be v and the final string be s for each v[i]>0 the closest island to it should be at position i-v[i] or i+v[i] if there is an island (v[j]=0) in the range ]i-v[i],i+v[i][ then that element j will be closer to v[i] which will be a contradiction so you should output -1 then for each -1 outside of the union of these ranges you can consider it as an island (set it to 1 in s and its valid given that it does'nt influence other elements) the -1 inside the union of the ranges will be set to 0 in the final string because they cant be set to 1 after that you need to check for every element i with v[i]>0 if there is an island in i-v[i] or i+v[i]
The problems were amazing and realized I need to improve myself, java was kind of problematic at times
Why does the system testing so long?
good contest, but G is too easy in Div.3
I liked this round a lot, but B felt easier to implement than A xd. And G was really easy compared to E for me.
Good work!
E took me longer than F and almost had G on time but still it was a great round!
Amazing contest, A-D was very easy.The jump from D to E was pretty big for a div 3.
Question F was really fun!
i got WA on test case 2 which was n=3 -1 1 1 i got answer as 1 0 0 Placing a treasure at island 1 (100) gives: Distance from island 1 to nearest treasure = 0. Distance from island 2 to nearest treasure = 1 (which is >=1). Distance from island 3 to nearest treasure = 2 (which is >=1). As question has clearly stated that ai means treasure is 'ATLEAST' distance away from ith island so my answer should be valid why jury's answer is -1
nik_exists explain this
As question has clearly stated that ai means treasure is 'ATLEAST' distance awaythis is not what the question says
ai indicates the minimum number of islands that Bessie would need to travel throughThe minimum distance that Bessie would have to travel from Island 3 to reach a treasure is 2, not 1
so 'minimum' no of islands that bassie would need to travel from island 3 to reach treasure is should be 1 .. in my solution it is 2 which is (>=1) i think that meaning is also valid it should be accepted also please do consider this perpective as well.
nik_exists
if the questions asks for the minimum and you give an answer greater than the minimum your answer is wrong
ai indicates the minimum number of islands that Bessie would need to travel through
so Bessie has travlled minimum distance of ai so it should be valid .. i don't care about getting accepted but just think of this sentence and valid solution for it .. if we wanted that distance to be exactly ai we should have mentioned it that
ai indicates the exact number of islands that Bessie would need to travel through to get treasure
nik_exists
the distance of the nearest treasure from j should be exactly b[j] (if b[j] is not -1). not >=b[j]
where did it mentioned 'exactly' brooo it says minimum ai that means it can be greater than ai aslo but minimum ai so i solved it like that..
nik_exists
AMAZING E and F! I had a lot of fun solving them :3
My contest discussion stream here for ABCDEFG