Hi Codeforces!
I am pleased to invite you to Adhocforces, Mathforces Codeforces Round #832 (Div. 2), which will take place on Friday, Nov 4, 2022 at 14:35 UTC. You will be given 5 problems and 2 hours to solve them.
The round will be rated for participants of Division 2 with a rating lower than 2100. Division 1 participants can participate unofficially in the round.
All problems in this round were prepared by me and CoderAnshu.
I would like to thank:
- antontrygubO_o for coordination of the round.
- ffao, Everule, Andreasyan, koderkushy, nor, AlperenT, the_hyp0cr1t3, Runtime-Terr0r, sp005, 18o3, KingRayuga, Scythe and sus for testing this round and giving really valuable feedback.
- MikeMirzayanov for the amazing Codeforces and Polygon platforms!
- You for participating.
The score distribution will be announced shortly before the round (or earlier).
Good luck and have fun! See you in the standings.
UPD 1:
Scoring distribution: 500 — 1000 — 1250 — 1750 — 2500
UPD 2:
I am flying to dhaka so will post editorials later.
UPD 3:
Congratulations to our winners!
Overall:
Div 2:
UPD 4: Editorial for A to C has been posted, will post D,E soon.
UPD 5: Editorial for D is posted.
UPD 6: Finally editorial for E is posted.
As a tester, I can confirm that the problems are very interesting and would recommend everyone to participate in the contest.
All the best to everyone !!!!
sir big fan
Good Luck Everybody
.
umm... No?
Leafeon.
If it is not Adhocforces and Mathforces as mentioned above. I think It must be Observation forces
Hope its not Speedforces :C
What you didn't wanted has come true, how do you feel?
Its speedforces for low rating..
Turned out true
I feel Observation forces is good sometimes... not always
As a tester, I think my opinion on the problems is best kept until after the round, but I wish everyone participating fun!
Why does this feel like a "lol yer so screwed, enjoy tho"
LOL, this is me being a bit too self-conscious. I've tested maybe 10 rounds by this point and I can only remember recommending participation for one (https://codeforces.net/blog/entry/76777?#comment-613771 ), as I feel that testers recommending every contest feels insincere (not every round can be the best round ever, you know?)
But then I think people might read too much into me not saying anything, so probably just never saying anything is better, and I thought it would be best to announce this to the world.
Overthinking 101
I am waiting to hear your opinions
I think the contest is great, a little challenging but not too adhoc.
I thought E was very cool and none of the other problems looked particularly bad to me, but there was a very large amount of "guessforces" involved in A-D and I thought that would be a bit offputting.
I was hoping to gain some sort of insight but it turns out all your approaches for A-D were the same as mine and I'm not good enough to solve E (in contest anyways). Welp, back to upsolving I suppose.
Sorry, I might be red but it still feels like I solve things by stumbling around most of the time...
Guessing feels very dirty to me but it's fast and it tends to work for early problems in div2 rounds. When you get to harder problems you start being forced to analyze the structure to simplify the problem -- D is a problem you could have solved a lot more systematically than I did (basically looking for invariants) but that kind of approach was really only forced for E in this round, which is a very difficult problem that many reds failed to solve.
I found a awesome solution for stupids like me:
I finally pushed it to a convolution form, and then what should I do
I think questions with guesses is common in the Codeforces format.
We only have a little over two hours to solve the questions, and the faster you are, the higher the score you get. Therefore, when we find a guessing that might be correct, we will try to use it to solve the problem first instead of proving it.
But this is not without benefit to us. We practice our ability to guess the conclusion and perceive the correct conclusion with increasing accuracy. This is also true in many cases in OI competitions. Some conclusions need to be observed and guessed (the proof will be relatively easy), and some conclusions can be guessed and seem obvious but not easily proven (in which case the speed and correctness of the guess becomes important).
I think that guessing the conclusion is part of Codeforces that brings me surprise and growth when solving problems. Of course, it does get a little tedious if you need to do this for every question.
I used inclusion-exclusion to solve E successfully :) It turns out that after changing the order of sigmas, the formula can be calculated recursively. Great problem! Looking forward to the intended solution.
As a tester, I tested this so long ago that I forgot I even tested it.
ඞ
I see :-O
And why a green can be a tester I think you are LGM :)
As a tester, I tested this round because of the authors and I was not disappointed. Most problems are pretty cool and high-quality, good luck to the participants!
As a tester, the questions are very interesting
pls downvote me!:)
No thanks
As a participant I wish you guys a very good luck
You had me convinced to partake at antontrygubO_o
you play brawl stars?
no.
Hoping to cross 2100! Good luck!
As a fan of
karuizawa keiayanokoji i must participate in this round.Best of Luck everyone.
Hope everyone good luck!
I was looking forward to the problems of this contest, hoping to surprise me.
Can anyone explain me, why score distribution is always posted shortly before the round and not earlier?
As a Kanye west fan, I can confirm "George Bush Doesn't Care About Black People" and would recommend everyone to participate in the contest.
Find Minimum of Maximum Of Minimum of Maximum...............
Nice Idea
Binary Search of Binary search
That's just nested Binary search, adamant had wrote some blog on nested ternary search or smth.
Mathforces
Dekuuuuuuuu ^_+
I'm afraid of Mathsforces as mentioned...
Hoping to get back my color (-_-)
Hope to see indian names in problem statement,
another garbage speedforces
There are only 5 problems, so it's likely to have large gaps between C and D or similar.
yeah the round is so speedforces that you could not even solve D
I hate any problem contains alice and bob most of them are very hard and take much of thinking.
I love any problem contains alice and bob most of them are very hard and take much of thinking.
Huh, and here I thought thinking and stimulating your brain was the point of CP
And where is the other points of cp ? for example there is problems require programming skills and problems require usage of algorithms and the techniques of cp like dp. why I learned tens of algorithms if the kind of problems like that?
Codeforces problems with difficulty <= 2100 typically don't involve too complicated algorithms, but they require deep thinking and interesting math observations, and the solution is often short. In terms of learning, I think solving such interesting problems can help you better understand complicated algorithms. Personally I like those thinking-intensive problems and that's why I'm a user here.
For example this educational round really balanced and diverse ,it contains 4 problems under 2100 but if you look at it you will notice that problem C and D requires dp and graph algorithms and only problem A which about math and thinking .
In my opinion educational rounds is the most benefit for me.
Btw ,I like your profile picture ,it express the real:)
Thank you :-).
It requires taking lot of examples and finding which one gives answer
1)taking parity of minimum or parity of array length ? or parity of total sum ? or is it parity of some other thing like parity sum-(n-1) ?
I am bad at solving problems which require a lot of case work and I thought this problem was one of that kind
you are right this problem just thinking only and doesn't corresponding to algorithms and data structures . un necessary problem and any company interview doesn't contains garbage problems like this .
I solved C after 3 WA and more than an hour and I wish I could find a way Alice and Bob both lose .. man I suck I couldn't see the simplicity
Operation forces, speed forces.
I didn't understand E problem's second test case 1,2 how it is possible 26?
I found the 01 02, 011 002, 0011 0112, 0001 0122
Length 4 : (0001, 0122) || (0011, 0112) || (0111, 0012) Length 3 : (001, 012) || (011, 012) || (001, 022) || (011, 002) Length 2 : (01, 02)
POV: u hesitate to submit C's Solution due to its simplicity :""
So true. I submitted C only after partially proving it mathematically.
orz, I could not figure it out for 2 hours straight lol, I'm so terrible
Nahh You're not terrible :)
We sometimes don't do well in some contests due to lack of concentration ,being exhausted or just need to practice more :".. , so just keep in mind to continue in your journey till reachin' ur glory.
Thanks for your kind words, appreciate a lot :)
I don't think you need rigorous proofs for each question, I am sure you must have solved B as well without proving that there is no other optimal way. Proving greedy algos is very tough in most cases. In problem C, you can easily conclude that only the minimum element in the array and the first element are relevant, you don't even have to look at other elements. This intuition comes from the fact that at each operation one of the elements reduce by one and each player can choose a specific element and try to reduce it to zero.
Honestly, if I were to prepare a contest ever, I will random-shuffle the problems (not based on difficulties). Most people submit A/B/C without proof.
Difference between contests and actual math is that you have one more technique of proof in contests. Namely, this seems to be the right kind of solution for a problem worthy of being Div 1/2 A/B/C/D. This is why experience has a slight advantage over rigour and creativity in CP.
I agree, the idea seems nice.
After Every round & specially after reading editorials/solutions...Why I feel like noob?
i think most of the contestant solved problem C without prove.
I still didn't got the logic. Can u please, explain the logic after the end of contest.
The element that Alice chooses is the element that Bob has to check for 0 and decrements in the next turn, and the element that Bob chooses is the element that Alice has to check for 0 and decrements in the next turn. Furthermore, the element Alice chooses is guaranteed to be outside index 1 when it's her next turn, and likewise, the element Bob decrements is guaranteed to be outside index 1 when it's his next turn.
Therefore, the fastest way to get an element to 0 is to always pick the same element (and this is guaranteed to always be available). Specifically, it should be the smallest element available to them, since they want to have decremented to 0 first.
Let's refer to the first element of the initial array as $$$x$$$. Alice should pick the smallest element available to her, which is the minimum of all elements except $$$x$$$. Let's say this element is $$$y$$$.
What can Bob do? Everything except $$$x$$$ and $$$y$$$ was originally $$$\geq y$$$ and would now be $$$> y$$$ when it's Bob's turn to choose, so Alice would win this race if Bob picks any of these. Bob cannot pick $$$y$$$, because Alice claimed it. So Bob's only possible hope of victory is to pick $$$x$$$. If, at the original array, $$$y \geq x$$$, then Bob wins. Even when they're equal, Alice has to decrement $$$x$$$ before performing the swap, so Bob wins that race.
Overall, the solution is very simple: find $$$y$$$ as the minimum of all elements except the first element ($$$x$$$). If $$$y \geq x$$$, Bob wins. Otherwise, Alice wins.
if you have the first turn you can always force the opponent to decrease the minimum element from the array. How? It's easy, just move the minimum element to the a[0], now your opponent is forced to decrease the a[0] and swap, and you just repeat and force him again. However, if the minimum element is already at a[0] then you are doomed because your opponent will beat you with the same strategy
Here is my complete logic: Is 1 showing up somewhere? If showing up as a1, then Bob will always win. Why? Because after Alice operation, a1 will be 0 and swap with ai. So Bob can always take this 0 back to a1 in the next step. So Alice lose. Else if showing up as a2/a3…, then Alice will always win. Why? Because after Alice operation, she can take 1 as new a1, then following the first half of this paragraph, Bob will lose.Now what if 1 is not showing up? Let’s focus on 2. If showing up at a1, then we know after Alice operation, ai will become 1, then following the logic from step1, Bob will always win. Else if showing up at a2/a3…, following the logic from step1, Alice will always win. …we can observe that the location of the smallest value matters: if at a1, then Bob win, otherwise, Alice win.
Here's my draft:
$$$[1]\ [a_2]\ [a_3]$$$ — when you(player) see this — you are losing
$$$[a_1]\ [1]\ [a_3]$$$ — when you see THIS you are winning ($$$a_1>1$$$). Know how?
$$$[2]\ [a_2]\ [a_3]$$$ — losing
$$$[a_1]\ [2]\ [a_3]$$$ — winning ($$$a_1>2$$$)
etc.
Then we LOOK and SEE and WATCH.
That's cool! I use similar approach to solve game theory problems, writing small states as winning or losing helps a lot and usually the winning/losing strategy hidden becomes obvious :)
You have a nice explanation. I finally understand the problem! Thank you!
thank you guy
Does D implementation has lots of case work? I thought about D but It required me to do lots of things with prefix and suffix and also checking for 0's in the array. Was I in the right direction? I was just finding whether prefix or suffix on [L, R] can have 0 Xor if not then check whether atleast one 0 Xor subarray is possible in that range.
Odd range is trivial. For even range, yes, check whether prefix or suffix can have 0 xor. No need to check for subarrays. These are all the cases: 179253302
Bro, whats in Dhaka?
ICPC World Finals
oh wow
Yaaaay, another speedforces
Solution for D:
We notice the operation will not change $$$XOR[l,r]=a[l]⊕a[l+1]⊕...a[r]$$$.So if $$$XOR[l,r]≠0$$$,no solution.
Let's consider the case of $$$XOR[l,r]=0$$$.
If $$$a[l]=a[l+1]=...=a[r]=0$$$,$$$ans=0$$$;
Else if $$$r-l+1==2$$$,$$$ans=-1$$$;
Else($$$r-l+1>2$$$):
How to find $$$x$$$:
Use prefix xor-sum.Note $$$XOR[i]=a[1]⊕a[2]⊕...⊕a[i]$$$.
We just find $$$x$$$,which makes $$$XOR[x]==XOR[l-1]$$$ and $$$x-l+1$$$ is odd.
Store all positions where $$$XOR$$$ values and parity are the same in a linear table(or STL set).Then we just do binary search(or use lower_bound) to find $$$x$$$.
Yea, but how we are finding that x effectively?
Use prefix xor-sum.Note $$$XOR[i]=a[1]⊕a[2]⊕...⊕a[i]$$$.
We just find $$$x$$$,which makes $$$XOR[x]==XOR[l-1]$$$ and $$$x-l+1$$$ is odd.
Store all positions where $$$XOR$$$ values and parity are the same in a linear table.Then we just do binary search to find $$$x$$$.
Else,we need to find x,which makes a[l]⊕a[l+1]⊕...a[x]==0 and x−l+1 is odd.If such x exists,ans=2.Otherwise,ans=−1
How can you do this in log or smaller time? This is the only part where I got stuck in.
just maintain 2 sets
You can store all prefix xor values in a map
value : vector of indexies
and then take lower_bound for l inmap[prefix xor value of l-1]
that will give us the nearest next index with theprefix xor = prefix xor of l-1
and ifval^y=val
we know thaty = 0
so we can use it ify <= r
. We should also care about segment to be with an odd length — for this we can have two maps — one for even indexies and the second for odd. My approach works so.bro finding that x is the most crucial part of the question, rest is easy
Completely agree ... I wanted to know this part the most !
For finding the $$$x$$$, I used two maps of vectors, one that stores the odd indices of each prefix XOR, and another that stores the even indices of each prefix XOR. If an odd-length substring that begins at index $$$\ell$$$ has an XOR of 0, then the prefix XOR at the end of this substring should be equal to the prefix XOR at index $$$\ell - 1$$$. The map retrieves a vector of all odd or even indices (we want the parity to match with $$$\ell$$$) that have this prefix XOR, so we can binary search to see if any of them are between $$$\ell$$$ and $$$r$$$.
imo I think the bigger roadblock is on determining whether the output is 0 or not. Although understanding the objective is simple (all values in the range need to be 0), checking this efficiently would, I believe, require a range query structure like a sparse table or a segment tree, so those who are not familiar with such structures would likely be unable to solve D. Everything else can be solved with cumulative prefix arrays and an efficient way to find indices that have a particular prefix XOR value (like a map).
EDIT: I'm dumb, we can just a prefix sum to check if a range is filled with 0s or not, lol. I did not need to build the segment tree after all. Well, I got Pretests Passed regardless, so I have no regrets. I hope it gets AC though...
I understand, thank you very much ! Ps, I didn't know that we could use lower_bound on maps
I didn't use the lower_bound on the map; I used it on the vector. The map is of type
<long long, vector <int>>
. It maps the prefix XOR value to a vector of even/odd indices that contain this value. It's on this vector that I check if the first even/odd index after $$$\ell - 1$$$ that has the same prefix value as $$$\ell - 1$$$ is before index $$$r$$$ or not.btw if you want to lower_bound on map, you should use the built-in method, e.g.,
mp.lower_bound (target)
, which runs in $$$O(\log(SIZE))$$$ time by traversing the red-black tree. Do NOT uselower_bound (mp.begin(), mp.end(), target
, since this will try to perform a binary search as if it's a linear structure, incrementing the bidirectional iterator to find a particular "index", which would take $$$O(SIZE)$$$ time. It's not relevant for D, but please keep this in mind for whenever you do want to binary search on a map (or set).Lol just make a prefix sum array, if the sum of subarray $$$[l,r]$$$ is $$$0$$$. Then all elements are $$$0$$$.
Yeah, I only just realized that, lol. I guess D is a lot more accessible than I thought. I guess the logic can be tricky though, but it's nice to know that nothing more advanced than cumulative prefix arrays are required here.
Can You please eleborate . I didnt got how to find x ?
I have two maps of type
<long long, vector <int>>
. Let's call themevmp
andodmp
, denoting even and odd indices respectively.Let's use an example to help demonstrate this: [7, 0, 7, 7, 0, 2, 5, 7, 0]
The prefix XOR array would be: [7, 7, 0, 7, 7, 5, 0, 7, 7]
The maps would map a prefix XOR value to the even/odd indices it appears in. Specifically, we have:
Let's say our query is
3 8
, which has even-length and neither index 3 nor index 8 (of the original array) are 0. The only way to make index 3 become 0 is to get an odd-length substring that begins at index 3 which XORs to 0. We're using $$$x$$$ to denote the last index of this mystery substring that may or may not exist. Note that $$$x$$$ must have the same parity as $$$3$$$, i.e., since 3 is odd, $$$x$$$ must also be odd (so that $$$[3, x]$$$ has odd-length).If $$$x$$$ exists, then the combined XOR of index 3 to x would be 0, so prefixXOR[x] = prefixXOR[2] = 7. So now we find the first odd index after index 3 whose prefixXOR is 7. The odd indices with a prefixXOR of 7 can be found using odmap[7] = {1, 5, 9}. We look for the first index that's $$$\geq 3$$$ (can binary search for 3) and check if it exists and is $$$\leq 8$$$.
The binary search should yield 5, which is $$$\leq 8$$$, so $$$x = 5$$$ is a valid choice, i.e., apply the operation on the range $$$[3, 5]$$$ first to turn them into 0, then apply the operation on the remaining range $$$[6, 8]$$$ to turn those into 0.
Please let me know if you're still confused by anything. There may be better approaches than this, but this is what to came to my mind, which I implemented. My submission might not be clean (I messed up earlier attempts during the contest), but may be helpful to check out regardless: 179275716
Thanks you so much for such a detailed explaination .
Hey, seeing the solution, especially the last part
What about the array
[0, 0, 0, 0, 2, 2]
. Since, you will find $$$x=2$$$ and the partition —0 0 0 | 0 2 2
. You would report the answer as 2. But isn't the $$$ans=1$$$, as the subarray[0,0,0]
needs $$$0$$$ operations and the subarray[0,2,2]
needs $$$1$$$In this case,$$$a[l]=0$$$,so we just do operation $$$[l+1,r]$$$ ,the answer is $$$1$$$(see the previous line).
I also came up with exact same approach. But it took me like 2.5 hours. Here is my Accepted submission . ( I tried to make it very readable).
If such x doesn't exist, how do we know there is no answer? I got stuck wondering if there can exist arrays which need 3 or more operations to clear.
Consider an operation sequence: $$$[?,?], [?,?],..., [l, p] $$$, we can prove that the operation $$$[l, p] $$$is always equivalent to $$$a [l] ⊕ a [l+1] ⊕ ... ⊕ a [q] $$$, no matter what the previous operations are.
Somehow my solution for D passed 100 000 stress tests but could not beat the pretest 2 LOL. Im not even mad, just curious
Well, don't you hate it when that happens? xD.
Take a look at Ticket 16407 from CF Stress for a counter example.
Have you tried generating tests with few (<= 4) bits?
what will be the approach for problem C ?
Step1: find out the minimum element in the array (let's say mn is the smallest element in the array)
Step2: if( firstElement == mn) then Bob is Winner Else Alice Wins.
And YESSS it's freaking ad-hoc
Explanation: You can see that if the first element is equal to minimum then when Alice swaps this element, Bob can swap it back to the first place, and in the end alice gets 0 on first position so loses. Otherwise if the first element is not minimum, alice can choose always this minimum, so Bob loses.
but how to prove this solution?
It's optimal for a player to always pick the minimum element that's available to them. The element that a player picks will not be available to the next player in their turn, but it is guaranteed to be available again after that. Therefore, Alice can keep picking the same element, and Bob can keep picking the same element.
Alice picks the minimum element from all except the first element of the array. The only way for Bob to stand a chance is if this first element is initially less or equal to Alice's choice. Note that this first element decrements on Alice's turn, so Bob gets a head start and would win even if this first element is initially equal to Alice's choice. But if Alice's choice is strictly smaller than the initial value of the first element, then Alice wins.
Basically, if $$$a[1] > \min (a[2], a[2], \ldots, a[n])$$$, Alice wins. Otherwise, Bob wins.
Bob and Alice chose minimum number from numbers he/she can choose from and how quickly make that number to 0. Alice got advantage because she chooses first from a[1..(n-1)]
Video Solution for Problem C
It is optimal for both Alice and Bob to apply operations on the minimum element. Who wins is thus decided by the position this minimum element lies on.
if it's not adhocforces then i am fucked
Why do you set the time limit for E so tight? My algorithm is linear, but can only pass when choosing c++ 20, while c++ 17 gave me TLE. This has cost me three penalties.
My submission: Submission
similar question for D... https://codeforces.net/contest/1747/submission/179278961 failed pretests, but https://codeforces.net/contest/1747/submission/179283673 passed. only difference was handling all the IO together. not sure if it'll pass systests though. next time I will also submit in c++ 20 :P
EDIT: original submission passes in 800ms with c++20 grrrr
Great contest!!! I love it!
what is the topic i can use to solve c
if ur the winner, keep $$$minimum \neq a[1]$$$
you mean that it is just an imp problem?
game theory problem but not classical actually, you can solve those problems by observing the win/lose state
How to solve D? I can only think of this solution but couldn't prove: If segment is odd size, then xor the whole thing must be 0. If it is then result is 1. If segment is even size, then check if there is a way to split the array into two odd segment, each of which total xor is 0. Do this by finding the nearest index from r which is true. An exception is when there are zeroes on left and right side, which should be taken intp account since the result might be 1 or 2.
Is it correct or am i missing something?
you can also reduce even length segment into odd one if a[l] or a[r] = 0
true. But if they are not one then the answer is going to be 2 right? assuming we can split the segment into two part of total xor 0.
yeah, that's the hard part of the problem imo
Prefix xor, keep track of last index that had prefix xor value x?
then if at i the xor is x then we can find the index with last x
I got it but still failed pretest, because there is case with zero at the end of an interval. In this case you only need 1 operation
If the segment has only zeroes then the result will be 0.
If every element of the segment is 0, the result should be 0.
If the segment is even size, If a[L]=0 or a[R]=0, the result should be 1. If there isn't a way to split the array, it's -1.
Thank you
Can someone point out what's wrong in this code? Link
Take a look at Ticket 16408 from CF Stress for a counter example.
I often overthink and write needlessly long and complicated solutions for extremely simple questions, but you... You have surpassed me in every way possible, I am awestruck and bow down in the glory of the sheer 200-IQness of your solution.
The problem C isn't a classical game theory problem (like a graph win-lose), so I liked it ... but I think most of the contestants had emitted hypotheses and just coded it hoping that it would pass all the tests.
If Alice can choose a number which is less than $$$a_1$$$,she could always choose this number in every operation,and it is easy to see that Bob must lose.
Otherwise,Bob could always choose the initial $$$a_1$$$,and it is easy to see that Alice must lose.
wow I accidentally swapped numbers 1 and 2 in two places and that's why i got wa2 in D, sad
Can anybody explain the logic of Problem C that how the answer is Bob when the minimum value of the array is equal to the first array element
You can see that if the first element is equal to minimum then when Alice swaps this element, Bob can swap it back to the first place, and in the end alice gets 0 on first position so loses. Otherwise if the first element is not minimum, alice can choose always this minimum, so Bob loses.
Pure shitty round as always like all Indian rounds !!
Ok
How did people figure out if a[0]<=min element then Bob wins and it works for all cases? What is the observation here?
Optimal play is always taking the smallest number. I figured that out by looking at how a game ends and which steps need to have happened before that.
Why is TL quite strict in Problem E?
How to solve E?
that's all i found. i guess it could be solved by including-excluding principle.
What is wrong with my A task solution?
Try
llabs
instead ofabs
Why do you think this is the issue? The
abs
function defined on<cmath>
and<cstdlib>
has the overloads forlong long
, so it should be returning along long
, same as what they passed to the arguments.Because I got the same submission as them, just with
llabs
instead ofabs
. ¯\_(ツ)_/¯I don't know, my submission got passed just fine with abs.
I see a lot of the same solutions from other people and they use abs for long long. It works for them. I am really angry that my code doesn't work on second pretests and can't understand why it doesn't work
For C++, use std::abs instead of abs.
I reproduced your problem. It can be fixed by either changing the includes to
#include <bits/stdc++.h>
or by usingllabs
your submission: 179289807
llabs: 179290278
stdc++: 179290542
Edit: Or listen to the poster above me. That is good to know!
Oh, I see the issue now. You are not using std::abs. Either use std::abs or llabs.
My guess is that the overloading for the
abs
function withlong long
types is in a library that you did not include. I copied your exact code and replaced all the includes with# include <bits/stdc++.h>
(which, btw, includes all the libraries, so there is no need to include anything else with it ever) and it was accepted. Submission: 179294076Damn. I guess it should be ADL messing things up.
Deleted
Sorry, Sorry! i guess gopi bahu don't like emoji
Definitely great round, thanks!
Is your criteria for considering a round great based on you getting positive rating change from it?
It probably seems so
~~\yes~~
Also, on problems not being insanely stupid.
Considering number of your comments under this post, is your opinion about rounds based on not getting expected performance? ;))
Not really sure what kind of jab you're trying to make, but I have only other comment other than my previous reply here. Clearly, I'm depressed over only getting +69 (haha sex) rather than +70.
Anyways, to baselessly call this a great round is stupid. It certainly isn't a bad round, but nothing about it makes it anything more than average.
did you get a negative rating change?
No.
then why are you attacking him like that
Because his point is stupid and clearly biased. Also not sure where I attacked him in the comment you're referencing?
It's a scathing attack on TimDee, don't try and pretend that it's not
I reserve my scathing attacks for Saarang only.
Nice job, strong pretests!
Sir, why are you travelling to Dhaka?
To see other ICPC world finalists and take autograph from them.
No komments!
no komments is my certified trade mark, we will meet in a court
You mean Egypt?
Might be Bangladesh instead.
im not going to bang ladesh
That's not a girl and he's not named Ladesh
She changed her name.
@aryanc403 Bangladesh is host ICPC World finals in 2022. That why we will be gone there.
.
I guess the round could have been better if the problem E had an easier version with lower constraints...
That may be too easy I think. Like just *1900
I blundered
Smh WA on D because of the case with zero at the edge of an interval with even length.
just submit it is right
maybe u should use
long long llabs(long long x);
is there a way to solve D with a sparse table
You don't even need sparse table. All you need are cumulative prefix arrays and a dictionary/map.
Key Observation: Performing the operation on some range will not change the result of applying XOR on all elements of that range, i.e., the combined XOR for the range is always the same before and after the operation.
This should be easy to prove if you think a bit. From there, you should be able to figure out the solution. It involves several cases, which may require different techniques and different structures to solve, but none of the structures are too complicated. Try to think about it before inquiring further on details (which I wouldn't mind sharing).
EDIT: Yes, there is one particular case (checking if all elements in the range are already 0) in which a sparse table can help. But a prefix sum array would be a simpler way to deal with that case.
I couldn't believe C was just finding min element! Thought my solution will get hacked for sure
Can anyone explain why i am getting WA in test case 1 in problem B?
include <bits/stdc++.h>
define ll long long int
using namespace std;
int main() {
}
in case 2 : after applying operation (3, 4) string look likes : BABNAN so this string still contains "BAN" as a subsequence.
Great contest. C was cute. Enjoyed solving D.
How to solve E?
Rough solution, will post full later
First Let's try to count the number of lists possible. The above problem is equivalent to counting the number of ways to reach (n,m) from (0,0) such that you always move closer to (n,m). There exists an obvious n*m dp solution.
If there is only 1 dimension then ans = 2^n-1 (that is m=0). So we can try to break the grid into several 1-d paths. We can club every path by breakpoints, by breakpoints we mean points we will surely pass through and from them, we will turn right. There can be at most min(n,m) breakpoints. The number of ways to select i breakpoints is C(n,i)*C(m,i). Hence answer should be ans = sum(C(n,i)*C(m,i)*2^(n+m-i-1)) for i=0 to i=min(n,m).
In the same way, we can find formulas for the expected number of moves to reach from (0,0) to (n,m). Define f(i) as the contribution of paths with i breakpoints. f(i) = Number of paths with i breakpoints / Total Number of paths. Let d(n) be the expected number of moves in the 1-D version of the problem. d(0) = 0 else d(n) = (n+1)/2.
E(x) = sum(f(i)*(i+d(n+m-i))) for i=0 to i=min(n,m).
P.S: It was Expected value before, hence ....
Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!
Alice and Bob should just get a room.
gimme downvotes, because round need to be unrated :)
when will appear ratings of the problems?
E, nice problem, it's ok. Though isn't the time limit and memory limit too strict? I know you want not to make O(Nlog^2 N) (or maybe O(NlogN) which I don't know how to), but 2 sec is enough to and there is no reason to make memory limit 256MB.
In testing we had an O(n log n) solution that worked in 3 seconds for the given constraints. Given that the O(n) solutions we had were working in 150ms and using less than 100MB of memory, 1 second seemed like a safe place to confidently separate the linear and the FFT solutions. I think we may have been unlucky to have tester solutions that were a bit too fast, and looking at the runtime for the accepted solutions during the contest 2 seconds would have been a better choice.
Yeah! It is a wonderful contest and good problem .
i think no
What could be the possibly rating of Problem C ????
1200-1400 I guess
Can anyone please explain the logic of problem C?
Well this is not a formal mathematical proof but just an intuition:
Whoever gets access to the minimum element first can win the game no matter what. There are two cases:
If the minimum element is at a[0], then Alice does not have access to that element since she can only pick elements from i = 1 (0 based indexing). In this case, once she performs the operation on any index, the minimum element decreases by 1 and goes to that index. Notice that it is still the minimum element, and now it's Bob's turn, so Bob has access to that element first.
If the minimum element is at a[i] where i > 0, Alice has access to this element first.
After a player gets access to the minimum element, he/she can just move that element to a[0], which will force the other player to decrease its value on their turn. This will go on till a[0] becomes 0 and the other player can no longer make a move.
Hello everyone! In problem B for n = 3 my answer is: 2 1 5 7 8
So, it's obviously going to be like that: BANBANBAN -> AANBBNBAN -> AANBBNABN (no BANs)
Also, for n=4 my answer is 2 1 5 7 11
BANBANBANBAN -> AANBBNAANBBN (no BANs I guess?)
My solutions are: 179271785 (wa4) 179276239 (wa3) 179288511 (wa4)
I couldn't check the tests while competing and actually got very upset as I couldn't solve B.
1) n = 3 : if you'll delete elements with numbers 1, 2, 3, 4, 6, 8, you'll get BAN. 2) same for n = 4
meghna gupta bewafa h :)
what could be the rating of d?
I guess 1500 — 1600 ...
why not 800+ 900+... :)
The range 1500-1600 is 800+, so I don't really get what you are trying to say!
sarcasm to bin *_*
I think 1900. Maybe 1800-2000 but not out of these bounds.
1900-2000
1800+ I guess. Very few people solved the problem
I nearly dropped to pupil:(
Is there any proof for the answer for B? I kind of just guessed.
A is harder then E
45th ICPC World Final's all the participants Welcome to Dhaka. Best of luck. Hope you will enjoy Bangladesh.
Why are almost problems from A->C greedy? That is my observation about some current contests.
Has anyone used segment trees for D? To answer the queries I checked for the xor of segment l to r, If the xor is not 0 then the answer is -1, if it is 0 and all the elements of segment are 0 the answer is 0, if not then if length is odd then 1 else if length is even then 2, this approach fails on some testcases, but if anyone has approached the problem in this way, please share the solution.
179328551
For C,
Here is my complete logic: Is 1 showing up somewhere? If showing up as a1, then Bob will always win. Why? Because after Alice operation, a1 will be 0 and swap with ai. So Bob can always take this 0 back to a1 in the next step. So Alice lose. Else if showing up as a2/a3…, then Alice will always win. Why? Because after Alice operation, she can take 1 as new a1, then following the first half of this paragraph, Bob will lose.Now what if 1 is not showing up? Let’s focus on 2. If showing up at a1, then we know after Alice operation, ai will become 1, then following the logic from step1, Bob will always win. Else if showing up at a2/a3…, following the logic from step1, Alice will always win. …we can observe that the location of the smallest value matters: if at a1, then Bob win, otherwise, Alice win.
guessforces
guys in problem 2 BAN BAN
i submitted a useful answer for test case 2 where the number of BAN is 4 but my answer was still rejected the ideal answer was 2 1,12 4,9 giving and answer of NANNANBABBAB my answer was 2 2,6 8,12 resulting in BNNBAABNNBAA which is true but was rejected although the problem clearly stated that any possible output is accepted can u please tell me if this is an error in the testcases or not
BAN must not be a subsequence in the resulting string anywhere. The resulting string which you mentioned, contains BAN, eg. B in index 1, A in index 5, and N in index 8 (1-based indexing). You might have mistook subsequence for substring. A substring must be contiguous but a subsequence may or may not be contiguous. P.S. the definition of subsequence is mentioned in the first few lines of the problem statement too.
awww i probably missed it thank you
Is not true because from BNNBAABNNBAA if I delete NNBABNBAA from left to right then still BAN is left there! You have missed the definition of subsequence I guess. So you should swap all the leftmost A with rightmost N or B with N. Hope you get it
yeah I get it now thank you
In $$$D$$$, I was thinking for a while about the proof for the following part:
For a given query $$$L-R$$$, assume $$$arr$$$ is the subarray enclosed by $$$L-R$$$. If there is no odd-length prefix of $$$arr$$$ has $$$0$$$ XOR (and accordingly no odd-length suffix as well), then answer is $$$-1$$$.
We can prove it as follows:
Assume we do an operation on an odd-length subarray $$$l-r$$$ within $$$arr$$$. All odd-length prefixes of $$$arr$$$ (and odd-length suffixes) that totally enclose $$$l-r$$$ or do not overlap at all with it will not change their XOR.
For those that partially overlap, either all the partially overlapping odd-length prefixes or suffixes will overlap in even number of values. So the XOR of each one of them will change to the XOR of a smaller unchanged odd-length prefix (or suffix) XORed with $$$0$$$ (coming from the even number of overlapping values). So their XOR remains non-zero.
Editorial ?
When the flight will land XD
I need editorial for problem D
I don't know when the editorial would be posted, but I can try to help explain Problem D.
Key Observation: If we apply the operation on some range $$$[L, R]$$$, the combined XOR of the values in $$$[L, R]$$$ remains the same.
Proof: If the combined XOR for the range was initially $$$x$$$, then the operation replaces each element in the range with $$$x$$$. When calculating the new combined XOR, each $$$x$$$ will cancel out another $$$x$$$ until only one remains (note that the length is odd), so the combined XOR is still $$$x$$$.
This leads to the following cases. Note that each case assumes that the previous cases do not apply.
If everything in the query range is already 0, then we already achieved the objective without needing to perform any operations, so the output is 0. This case can be checked by pre-computing a prefix sum array. You could use Sparse Table (max), Fenwick Trees (sum), Segment Trees (sum/max) instead, but they're kinda overkill.
If the queried range does not already have a combined XOR of 0, then it is impossible to turn all its values into 0 (since that would require changing the combined XOR). Such cases have an output of -1. This case can be checked by pre-computing a prefix XOR array. Could use Fenwich Trees (XOR) or Segment Trees (XOR) instead, but still overkill
From this case onwards, the combined XOR for the range must be 0 (but there must be at least one non-zero value in the range). If the queried range has odd-length, we can apply the operation on the entire range to turn them all into 0s, so the output is 1. Checking odd length is trivial
Now the queried range must have even length. If the first or last element of the range is already 0, then we can apply the operation on everything except the first/last 0 element, to turn everything into 0. The output is 1. Checking endpoint values is trivial
Now the queried range has even length but the endpoints are both non-zero. Now let's look for an odd-length prefix of this range such that this prefix has a combined XOR of 0. If such a prefix exists, we can apply the operation on it to make them 0 (including the first element). Now we can perform another operation (like step 4) to turn everything else to 0. The output is 2. This can be tricky to check, I'll discuss this afterwards
If there is no odd-length prefix with a combined XOR of 0 within this range, then it's impossible to make the first value in this range a 0. Even if we try to perform other operations first, each operation will preserve the combined XOR values, so there will never exist such an odd-length prefix with a combined XOR of 0. Therefore, the output is -1. This is the last remaining case, so there is nothing to check here.
My approach for checking Case 5 might not be the best, but it works. If such an odd-length prefix exists, i.e., a range $$$[\ell, x]$$$ with odd length whose combined XOR is 0, then observe that the prefixXOR value at index $$$x$$$ must be the same as the prefixXOR value at index $$$\ell - 1$$$ (or equal to 0, when $$$\ell = 1$$$). Furthermore, $$$x$$$ has the same parity as $$$\ell$$$ (either both even or both odd) in order for $$$[\ell, x]$$$ to be of odd length.
So what I did was build two maps (dictionaries), each mapping a prefixXOR value to a vector that lists all even or odd indices respectively that have the same prefixXOR value. When I reach Case 5, I check $$$prefixXOR[\ell - 1]$$$ and pull up the corresponding vector from the corresponding map, and then check if any of these indices are between $$$\ell$$$ and $$$r$$$. This check can be done by binary searching (lower_bound) for $$$\ell$$$ and checking if the result is $$$\leq r$$$.
Runtime: $$$O(n\log n + q\log n)$$$. The $$$\log n$$$ factors are both due to Case 5 (both preprocessing and checking), so if there's a better way to deal with Case 5, the complexity might improve.
My Submission: 179275716 (it's not very clean since I changed a bunch of stuff while struggling in the contest, and yes, I did build two segment trees)
my solution also has same time complexity and it's giving me TLE on test case 3 :( 179565550
Your algorithm is efficient; the only issue with your submission is that the I/O is too slow. This is actually very well-known for competitive programmers in C++. Briefly, there are two issues:
When using
cin
orcout
, the default behavior is that they should be synced withstdio
(i.e.,scanf
andprintf
), e.g., if you read input withscanf
and then try to read input withcin
, the default behavior is thatcin
will read the next input that was not read at all (and should not read whatscanf
already read). This synchronization takes some time for each use ofcin
orcout
.When you want something to be printed as output, it is first stored in a buffer. The buffer is only emptied and displayed (aka flushing) when something triggers it. By default,
cin
andendl
would invoke flushing. Each buffer flush takes some time, so having a lot of flushes would slow down the program. When the program terminates with no errors, the buffer is flushed.Solutions:
To avoid synchronization delays, one option is that we can simply use
scanf
/printf
instead ofcin
/cout
. But if you prefer to usecin
/cout
, another option is to turn off synchronization (betweenscanf
/printf
andcin
/cout
) by adding one line of code to the program:ios_base::sync_with_stdio(false);
. Note that turning off the synchronization means that using bothcin
andscanf
or bothcout
andprintf
would allow them to overlap, so make sure you never usescanf
/printf
if you choose this (except for some rare scenarios where you can exploit non-synchronization). Your submission gets AC by adding this: 179941502 (but 920ms is dangerously close to the time limit)As for flushing, this can be dealt with by simple leaving all the output in the buffer without flushing. When the program terminates with no errors, all of the output will be flushed anyway. To avoid early flushing, you should never use
endl
and instead print\n
. Your submission now gets AC with a comfortable 374ms with this replacement (in addition to turning off synchronization): 179940064Your submission doesn't suffer from this issue, but it is often convenient to output the answer to the current test-case or query before we read in the next test-case or query. In this case, the following
cin
would flush the contents of the previouscout
. This can be avoided by adding a linecin.tie(NULL);
, so flushing is only done at program termination (if there are no errors). The latest submission includes this (but it doesn't do anything for your code because you decided to read all the queries early for some reason, before printing any output).A downside to
cin.tie(NULL);
is that if you interactively test your program, you would only see the output when the program terminates. You can temporarily comment this line out for such interactive testing. Otherwise, you can simply provide in the entire input before you receive the output to check.By the way, for interactive problems, you need to flush the buffer for the interaction, so for these problems, you should use
endl
orcout.flush()
after your query (but stick to\n
if it's in the middle of the query) before reading the response.tl;dr start every program with the lines
ios_base::sync_with_stdio(false);
andcin.tie(NULL);
and don't useendl
(print\n
instead), except after querying in interactive problems.Thanks for such a good explanation. I had seen blogs on this before but never tried to read it since I never came across a problem like this. Thanks again :)
-1 for no editorial, and another -1 for much comments on how simple solution to C is without explaining it.
Is D actually solvable on python?
sussy bucka
In Problem D. I am getting TLE on test case 3. I think my solutions's time complexity is O(q + nlogn). Many others have gotten AC on this complexity. Can some tell what's going wrong on this? 179541379