Hi Codeforces!
I welcome everyone to participate in Codeforces Round 882 (Div. 2) which will start on Jul/06/2023 17:35 (Moscow time).
The round will be rated for participants of Division 2 with a rating lower than 2100. I would encourage Division 1 participants to participate in the round unofficially.
You will be given 6 problems and 2 hours to solve them. One of the problem is interactive, so please read guide for interactive problems if you are not familiar with it.
All the problems are prepared by me and StArChAn.
We would like to thank:
- darkkcyan for going to Lebanon and doing Quality coordination.
- Alexdat2000 for translating problem statements.
- socho for helping with the initial stages of the round.
- astoria for giving problem idea of one of the problem and helping with the initial stages of the round.
- Spensa for grey testing.
- meghahegde for green testing.
- anuzrella, ak2006, ghosty, Trumling, Qualified for cyan testing.
- alwyn, nishuz for blue testing.
- Xc4l16r3, blue for purple testing.
- maomao90, vinfat, Mike4235, Dominater069, aryan12, 74TrAkToR, satyam343, AquaMoon for yellow testing.
- Umi, kshitij_sodani, Kuroni, thenymphsofdelphi for red testing.
- MikeMirzayanov for the great codeforces and polygon platform.
- You for participating in the round.
- Lastly, me for gong to Yemen and doing Treelike problem setting and writing this Thunderous blog.
Also, the editorial video for all the problems will be available on my channel right after the contest ends
All the best everyone!! Eager to see you going All Around The World and being Unstoppable in climbing the ranklist.
UPD: Scoring distribution — $$$500 - 1000 - 1500 - 2000 - 2750 - 3000.$$$
UPD: For video editorial of the problems, you can find it here
UPD: Editorial is out.
Finally a contest after almost a week!
Worst contest I have ever seen!..
The queue at the beginning and the statement of the problem D was awful.
What happened with me was when I submitted a solution it showed Runtime error on pretest 1 where as my IDE was not showing any errors. After that when I randomly commented a line which was not useful it started showing TLE. Also for another problem it was showing wrong length of output where as my output was a single int.
-Deleted-
Just wanted to deliver the idea that authors try their bests ,so we shouldn't comment "Worst contest ever" every single contest
Please stop saying 'stop crying' to someone who speaks right things.
please stop saying "Please stop saying 'stop crying' " to someone expressing their opinion.
It is too offending to say to someone "Please stop crying."
Please Stop Making "LINKED LIST"
NULL
If You don't think I am right check this out. https://mirror.codeforces.com/contest/1847/submission/212493731
Solution to C
All that matters is how fast you can google. HATE SUCH CONTESTS,
Message for Authors — At least make some new problems instead of useless & BULLSHIT stories. Codeforces pays you for a reason.
If you used your head you would realize that due to the small constraints that you can brute force instead of googling an algorithm. Not only did you reveal you are not very good,
but also that you were cheatingGoogling isn't cheating; it's allowed in the CF rules
oh, I did not know
yeah and that brute force TLE's for some people because of the trash constraints , exact same sol as my friends and im the only one TLEeing
you got TLE because your implementation is sucK man (O(T * MAXN)). Don't blame.
nah i meant the very first submission its clearly implemented the same way with my friends and they got ac there is the sum of n thing wdym T
Dear friend I got to know after contest that the solutions are available as it is on internet. I'm not like you who starts googling, after trying for 5 minutes. Also, No offence to setters, The questions were good but The language framing was a piece of shit rather shittiest piece of shit, That's why I was so frustrated. Also doesn't matter if you downvote it 100 or 1000, THAT'S WHAT IT WAS
I do not know what I did to suggest to you I was googling. The statements were good and I read them without trouble. In fact they were fairly typical statements. Maybe you can improve reading.
I guess it's hard to create an easy problem that wasn't already on CF or anywhere else just because every contest has a lot of easy tasks. I think you might be able to google A, B is just another "go through array while maintaining some values"
Creating d2B harder than creating d1F.
All these submissions have a same function for problem C 212411474 212408231 212415822 212444362 212445049 some of them have removed comments otherwise the functions and structs are same.
I went nowhere and did based testing.
I surely hope problems are good.
I went to Antarctica and did kinesthetic testing.
Wishing for the ratings in Antarctica to stay afloat and not sink.
I went to Narnia and did soulful testing.
--Deleted--
Is one of the problem named Treelike?
since this is being set by indians my guess is there would be problems on graph and bits.
Is one of the anime Vinland saga?
As a fan of [user:darrkcyan], I recommend you to participate this contest:))
As a fan of darkkcyan I recommend you to check the spelling of his handle :))
Oh sorry if I have a mistake in my sentence.
Finally I'm going to be rated!!
Let me guess, is the anime Horimiya?
No, it's obviously going to be "Do You Love Your Mom and Her Two-Hit Muti-target Attacks?"
first time seeing a grey tester! hope the contest is good.
tibinyte : Am i a joke to you?
In terms of his rating — absolutely :)
I hope one of the problems is related to One Peice .
I went to Alaska and did master level testing.
Atekichan Finally your time to shine!!
i have a bad feeling about this round...
Nothing's too hard if you are prepared and god willing.
plus, what are you so worried about. Non-rated people like me will always have their rating increase, cause your rating can't go down if it's your first rated competition. :thinkies:
Enjoy every competition
Anime Prediction List :
0) DeathNote, (Involves mental games )
1) Code Geass ( Considering the theme is Coding, this one fits ),
2) PsychoPass
3) Naruto ( So many fans )
4) Black Clover ( So Many fans )
5) Demon Slayer,
6) One Piece,
Keep the list going :D .
More likely it will just have cute girl(s). :)
Attack on Titan left the chat
I was right
I went to Antartica and did gawky testing.
Is anyone left for taking part in the contest?
As a tester,tasks are nice and wish everyone good luck (〃•ω‹〃)♡
score distribution when?
I wonder why MikeMirzayanov has more contribution than anyone but doesn't show up on the leaderboard for Top contributors...
Indian setters and testers means contest with bits questions :)
D:
You have some soothsayer powers
Its time to purple again :)
congo bruh
Hope to get to CM!
+1
Balanced score distribution
I will become specialist :)
My unmatched perspicacity coupled with my sheer indefatigability makes me a feared opponent in any realm of human endeavor.
You're not GM yet?
I have enough time left to reach GM. U need no worry about it. :wink:
Huge gap from D to E. Interesting!
I'm not sure, but he mentioned scoring distribution instead of rating, so it's difficult to determine the gap between D and E, right?
Yeah I guess that, anyway, enjoy the problems ^^
I'm sorry, you are right. It seems that a high contribution can indeed indicate some issues.
Please remember to add a space after +!? in interactive questions.
excited to participate!
There seems to be some issue with the queue. Solutions submitted later have been judged, but the ones earlier in queue are pending.
Same here for problem A :)
You thought it was a programming contest but It was I, Dio
W Contest
You though this would be a normal spoiler, BUT IT WAS ME ! DIO !!
there are few bitwise operations today thx
Bitwiseforces
this contest very very very hard
just keep in mind we don't have time to keep searching for your ANIME things :(
GFGforces
As the contest ends
here is the link : https://www.geeksforgeeks.org/find-the-maximum-subarray-xor-in-a-given-array/
Should all setters try so that answer should not pop up if you search "MAXIMUM XOR SUBARRAY".
Don't know if other problems had the similarity. But for problem C, this isn't a fair criticism.
Because for this problem C, figuring out we need to find the maximum XOR subarray is the main part. After that, One doesn't need to use any Trie or anything. Constraints on values are so small, one can check for each position for all possible previous prefix sums till now.
stop using your alt-account whining about false things
how to come up with the idea for the problem c for the first time if you have not used(implementation) trie before and is there any other solution?
I dont know, in my room there are like 5 solutions with same structure "Trie". I begin with C, and send it in 5 minutes after. Just use that numbers are small:) You can see my easy submission
You don't need trie
using the two properties of xor :
a^0 = a
a^a = 0
hence we can choose any subarray we want by choosing first r to m then l to m , hence the problem becomes finding the subarray with maximum xor
yep but didnt know how to calculate it in O(N) without trie
It can be easily solved in O(2 ^ 8 * n) which passed tests
Just support all possible xor of segments ending in i'th element. Because a[i] < 2^8 then xor also < 2^8.
Any value which you will append is going to be xor of any subarray. And you can append any xor subrray in 2 operation. So you just need to find maximum xor of all subarrays
If you can find the pigeonhole principle in the prefix XOR values, then you will have to look forward to only 256 indices for an index i. So, it can be solved in O(256n)
I think , the best way to deal with such questions is to , to do the operations specified in the questions by yourself. Like if you randomly do some operations you start getting hints about the problem and patterns emerge . That's atleast the way I do for such problems . Hope it helps
You may notice that due to constraints number of different prefix-xores is small (not greater than 257), so if you sort them and apply the 'unique' operation, you can use brute-force to find a maximum xor of all pairs.
LtoR forces bitwiseForces SpeedForces jojoforces
Can we solve F like that -: We have to find the smallest subarray with or greater than v. Now if we fix the start index say l, then there can be at most 32 index r, such that or of subarray a[l..r]changes. So we store all these 32 indexes for all l from 1 to n and use prefix minimum for the query?
Yes, i solved it like this 212446074
Thanks, I could have solved it, but wasted a lot of time after misreading D.
In problem D, second sample, query 2, why is the answer 3? After flipping a3, a5, the only ones which are in t(s) are a3 and a7, ans <= 2. What am I missing?
I think the answer is 3 because:
Swap pos1 (1) with pos2 (0)
Swap pos4 (1) with pos5 (0)
Swap pos6 (0) with pos7 (1)
Dude I swear I wasted 30-50 mins because of this similar doubt and was unable to solve D fast enough. But the thing is that there are some 1s which are not in t(s) and we can use them
Even I didn't realise that we can use the 1s that are not in t(s), I realised it after contest :(
I bricked C hard. I could not for the life of me figure it out until like the end of the contest. :/
Anyone else misread D's statement, thinking we swap elements in T(s) instead? :( wasted an hour
Yes same, I also wasted around an hour.
same TT
Damn. This comment made me realize this!
yup, realised when I had 5 minutes left
What's the idea for the solution to Problem F? I have gotten a bunch of insights but haven't been able to formulate the complete solution.
I liked the ideas of the problems, but my request to you, since there are many religious people that love to participate in CF contests, is to not use phrases like "The Man who became a God" in the problem title or description. Thank you.
What is this obsession with Bitwise operators and GFG ? Make some original problems.
As I understand it, in problem C, you need to find a segment with the maximum XOR. Is there any well-known way to do this? Two pointers don't work here.
212397289
It uses Tries.
GFG Article for the solution
I see, that too many ppl just copy all code there. Seems all of them can get "cheat plag".
Nope. You can copy code published before the contest has started
Of course you can. But the plag system is now a human, if like 1000 solutions are really the same(with the same comments:)), they can be plag. I am pretty sure, that anyone will not unplag such 1000 ppl:)
A solution without tries- First find the prefix xor array. for the given constraints on ai, you could just iterate the prefix xor array from left to right and maintain a 256 sized boolean array which stores whether a certain number has been seen before in the iteration or not. Hence at every iteration just iterate over this boolean array, if a number has been seen then just xor that number and the current value of prefix sum and take max of it with the current best answer!
This works with ai<=2^63. This is maximum xor pair but it can easily be extended to maximum xor subarray.
Yup I did this. I used a set to store all the visited prefix XOR's tho
Oh, I was a bit paranoid about this approach cuz this can in the worst case add a factor of log(2^8) to the time complexity
Runtime error on test 13 at problem D. Really sad, I was getting close to purple.
Nice round! I enjoyed how Problem C masked the well known problem of maximum subarray XOR, but I think it might be unfair for people who tried to come up with the solution on their own rather than Googling, since the most common solution uses a Trie which would suit Problem D more.
Cool contest! though i had troubles since i haven't written contests in a while
I saw my friend solve D in 25 mins, and rushed to solve D before C, came up with the solution quickly but implemented it too slowly, ac-ed, got a low score for it 30 mins before the end, and solved C 3 mins before the end. Happily the contest was prolonged for 15 mins:)
Was the last submission considered over the first? I thought that it is so, only if first submission failed FST :(
Any hints for D? I'd like to try solving it on my own
I thought about assigning priority to each index, ig this might serve as a hint if this is in the correct direction, can anyone confirm this?
Give priority to each character, according to their first appearance in $$$t$$$. Then if you have a lower priority character as $$$'1'$$$ and a higher priority character as $$$'0'$$$, swapping them will be better.
$$$t(s)$$$ can be annoying, can you solve it when the goal is to make the following string as large as possible?
string $$$s$$$ itself?
a fixed permutation of string $$$s$$$?
a fixed length prefix of a fixed permutation of string $$$s$$$?
Once you have that, you have solved half of the problem, can you solve the full problem?
Any good hints to solve F?
Don't like C at all. It's just duplicate of https://cses.fi/problemset/task/1655. Furthermore, I was suprised by the quantitiy of people could solve it in the contest after 1 hour passed, since Trie is not something most people could know and implement.
Yeah, honestly I just want to imply that the majority copied and pasted the solutions. But i think the main point here is about problem setters. It's okay to use some of small problems , but not to use the whole of them adding to a single C.
You can solve it just by brute force because ai <= 256
I wonder where they got the idea for Problem-C:
https://www.geeksforgeeks.org/find-the-maximum-subarray-xor-in-a-given-array/
Try to make beautiful problems not a beautiful blog.
HAHAHAHA, FUCK ME, TL ON D CUZ OF THIS SHIT:
j = *upper_bound(st.begin(), st.end(), j);
INSTEAD OF:
j = *st.upper_bound(j)
HAHAHAH, ADORE PROGRAMMING))))))))))))
yep, got it accepted, after this and 1 more edit)
tilt...
I read the title of problem A, well that made me thought the contest's theme was DeathNote =))
A pretty bad contest, its difficulty is more difficult than the number in the problem.
A: Sort the array of {a[i]-a[i-1]} and choose n-k minimum elements.
B: Let A=a[1]&a[2]&...&a[n]. If A>0, then for all 1<=i<=n we have a[i]>=A, so if there are more then one groups, the bitand of each group will be at least A, and the sum will be at least 2*A > A, so there can be only one group. If A==0, we can build groups greedily from left to right (by choosing the minimal prefix of remaining elements with bitand==0).
C: By trying for some small cases we can find that all possible values of strength are the xor-sum of some ranges [L, R], we can find them in O(max(n^2, n+(2^8)^2)) = O(2^8*n).
D: For numbers in [L1, R1] we let a[L1]=1, a[L1+1]=2, ..., a[R1]=R1-L1+1, because s[L1] is the first element appears in t, s[L1+2] is the second element appears in t, and so on. For numbers in [L2, R2] and not in [L1, R1] we assign values to a[i] by the order s[i] appears in t. Using an ordered set we can process all m ranges in O(m+n*log(n)). Assume there are k numbers in any range [L, R]. For answering queries, let's assume there are x occurences of 1, then for all i such that a[i]<=min(x, k), we need do operations to make s[i]=1. Then we can answer the queries by fenwick tree.
E: untested problem.
F: If we let b[i]={a[1], a[2], ..., a[n], a[1], a[2], ..., a[n]}, then we can see all values appear in {a[n+1], a[n+2], ...} are some range-bitor of b[i], and for ranges with same right bound and same value of bitor, we only need to keep the smallest range. For each right end, there are most log(max(a[i])) different values of range-bitor, and we can find them by sparse table and binary search, so we can solve the problem in O(n*log(n)*log(max(a[i]))).
denote bitor(L, R)= a[L] | a[L+1] | ... | a[R] if L<=R
bitor(L, n) | bitor(1, R) if L>R
a[1], a[2], ..., a[n]
a[1]|a[2], a[2]|a[3], ..., a[n-1]|a[n]
a[n]|a[1]|a[2], a[1]|a[2]|a[3], a[2]|a[3]|a[4], ..., a[n-2]|a[n-1]|a[n]
bitor(n-1, 2), bitor(n, 3), bitor(1, 4), bitor(2, 5), ..., bitor(n-3, n)
...
bitor(n-k+2, 2), bitor(n-k+3, 3), bitor(n-k+4, 4), ..., bitor(n-k, n)
...
bitor(4, 2), bitor(5, 3), ..., bitor(n, n-2), bitor(1, n-1), bitor(2, n)
bitor(1, n), bitor(1, n), ...
"Using an ordered set"
I thought so too. Given that codeforces refuses to install sortedcontainers for Python, is there an alternative solution for D that works in that language?
For this problem we can use dsu instead.
Use a segment tree. That's what I did in Java.
https://github.com/cheran-senthil/PyRival/blob/master/pyrival/data_structures/SortedList.py
If you use a Fenwick array for the second part, you can also use it for the first part, assuming you have implemented a lower bound operation.
Or you can just use a binary search in the Fenwick array, which would be $$$\mathcal{O}(\log^2 N)$$$ instead of $$$\mathcal{O}(\log N)$$$, but I think it would be fast enough.
Anyone else overkilled problem A with dp?
I was literally thinking that how can problem A be dp and read the problem's constraints too many times before submitting
Wasted like 10 minutes implementing the DP solution, got annoyed, stopped to think, facepalmed, submitted the greedy — AC.
Lesson: Don't take breaks from CP.
For me implementing DP was easier than coming up with the greedy solution.
For the long time(about 25 minutes) I was thinking smth like: "Nah, it's the first problem, there should be easier solution". The result was just wasting these 25 minutes, 'cause I've written dp solution finally.
No written editorial?
hmm
bruh, its not same, there are more simple a[i]<256 u can just do N*256, there are no even need to think (if u know prefix arrays)
Also it fair
It's kind of hard to reduce the problem down to max subarray xor, so I think it's fair
Just not my day I guess.
Someone please help me with B, didn't we just needed to find the maximum segments that had the same "&" as that of the entire array, such that all segments have that same "&".
that's right when the and is 0 but when it is anthing else the answer is always one group as adding more groups will always give higher sum
We need to find the minimum sum of bitwise and. Suppose the full array has bitwise and $$$3$$$. If you find two subsegments, both with bitwise and $$$3$$$, the sum of those is $$$3 + 3 = 6$$$, which is more than $$$3$$$ and not optimal.
Let biwise AND of all the elements equal to k,
Case 1: k == 0 : Try to create maximum number of partitions such that AND of all partitions = 0.
Case 2: if k > 0 , it's always optimal to create only one group, i.e. the whole array. Reason :--> It's easy to prove Bitwise AND of any partition is >= k , hence more the partitions, more will they contribute to sum, so make just 1 partiotion with AND = k
problem c is a copy of these problems: https://www.geeksforgeeks.org/find-the-maximum-subarray-xor-in-a-given-array/ https://www.spoj.com/problems/QN01/ https://sairampenjarla.medium.com/maximum-xor-subarray-3b9e27bc302d https://mirror.codeforces.com/gym/103091/problem/A https://cses.fi/problemset/task/1655
should this round be rated?
If every round that had problem that after thinking is reduced to standard problem as most major component is unrated, almost every round would be unrated.
in problem C you need to make some observations before that, so no
easily you can see that the task is finding the max xor range it's obvious, everyone knows that a^a = 0 this is the only reduction you need and its also a well-known property of xor, if you just copy standard problems and rephrase them almost every round will be googlable! and worthless. it's okay to use standard ideas in a multitasking problem or make from them a new variation but anyone can just copy the code from gfg with no understanding of it at all and it will pass! , this is my opinion i respect all your points but it is just not fair.
You say it's obvious but in a 101 word comment you were unable to explain why it is obvious.
The fact that one can guess the task without proving it is the correct solution is not ideal and the most interesting problems make it hard to guess the idea, I agree.
Thankfully everyone has access to the internet, so it's an equal playing field when it comes to fetching code to solve standard problems. You can carry on and have fun with the remaining 5 problems in the contest instead of complaining.
Actually its rather obvious since operation on a index is performed only once(two operations will just introduce a zero) its simple to just jot some equations down and see the result that it always leaves a subarray xor
If you have to "jot some equations down" to convince yourself it is true, that's not what I call "obvious". But maybe we have different definitions of the word.
everyone knows that a^a = 0 this is the only reduction you need and its also a well-known property of xor
That's why it's obvious. you can take any suffix you want and delete from it(a^a=0) any other suffix and it gives you any subarray you want.
Thankfully everyone has access to the internet, so it's an equal playing field when it comes to fetching code to solve standard problems..
yes, but you don't participate in rounds to copy solutions, it's okay to copy some block of code that will help you in solving the problem but not the solution itself! , so when I participate in a round i trust in cf that it will give me original problems so i depend on myself, others maybe will go to copy the answer so you will have 5k+ solutions so its not fair to those who trust cf.
You can carry on and have fun with the remaining 5 problems in the contest instead of complaining
for sorry not everyone can solve the whole problem set, if someone can only solve till c it will affect him if c was a googlable so i has the right to complain .
Can you explain why can't we get any subsequence of the array? Or, at least, prefix + suffix? Why only subarrays?
As nifeshe implies, to me it is obvious you can get any subarray, but not so obvious you can't get any subsequence. Maybe for you it is, great, but it was not for many including me.
It is sad that many can just happen to guess, but that is true of arguably most lower level problems.
All of this frustration may be valid, but may I ask... Why are you complaining about a problem in a contest you didn't participate in?
In fact, according to your profile you haven't made a submission in a contest in almost 6 months. I wonder what the fuss is all about.
I mean if a problem is heavily disliked or liked one can have the curiosity to look at it
Heavily disliked by whom? Steven-_-AbuAlkhair was one of the first to comment about the problem, right after the contest ended.
Do you also go to the comments section to complain about how frustrated you are about the quality of specific problems, immediately after contests end? For contests you did not participate in? Really?
Yeah since I didn't participated in contest I cant dislike a problem that's true :), leaving all that nothing was wrong about problem C, it was just a another easy div2 C, most frustration from people is due to others using online code while they didn't(either for being absent minded or they didn't want to)
Again: how could they (the person who started this thread) be frustrated about others using online code to solve a problem in a contest that they did not participate in?
I'm done engaging here. Enjoy life.
DEF -> FDE
Codechef Forces.. gave me the vibes of their contest
My approach for C was to calculate all suffix xor. Then answer will be maximum xor of any 2 suffix in an array. I don't understand how it is equal to maximum xor in a subarray. This is my solution btw — https://mirror.codeforces.com/contest/1847/submission/212410188
Notice that the xor of 2 suffixes is equivalent to the xor of a subarray, example:
Suffix xor 1 = a^b^c^d^e^f Suffix xor 2 = d^e^f
Now if we xor these 2 we get a^b^c^d^e^f^d^e^f = a^b^c, notice how the intersection of the suffix xors get cancelled out. So when you calculate the xor for any 2 suffixes, you're actually just calculating the xor of every single subarray. Same with prefix xors.
yes, gotcha. thanks bro.
Problem C likely had so many submissions because once you recognize that ans is max xor subarray you just have to google the solution. The max xor subarray problem is a great classical problem but I dont think such classical problems should be put in cf. How many people who submitted the solution knew how the solution works using tries I wonder. Not a good problem
I did the trie part after thinking for like 15 minutes.
I didn't solve the problem with max-xor-subarray.
I didn't reach the this observation until you mentioned it. But still I managed to solve the problem.
Which anime was it?
jojo's bizzare adventures
Huge Jojo fan, but pretty bad contest
As a tester, I can say that the quality of the problems was very high. (especially C in my opinion)
How to solve D ?
Lets do 2 key obsertvations. 1) If we have 2 segments that overlap, we can subtract the overlapping part with the segment with less "priority" in the calculation of t(s). Where the less the position is in t(s), the higher priority. So now lets recalculate the segments this way, and now each index belongs only to one "segment", even though they could now be not segments. 2) Now lets do a trick: lets calculate t(s) and instead do all of the operations on t(s). Now, because of observation 1 each element from s can be found exactly 1 time in t(s). Now lets do a segment tree for finding the sum on t(s) and to recalcing the answer is obvious: the numbers of 0s in the segment [0; x] where x is min(number_of_1_in_t(s), unified_length_of_all_segments)
I did the priority distribution right, but couldn't come up with this idea that minimum operations is just number of zeroes that should've been 1. Thanks for your solution btw :)
Fun fact: C can be solved with O(nlog(max a[i])) complexity by using trie of prefix xor-sums.
trash round did the same thing as some of my friends in 1st 15 minutes and it TLE'd for me only so had to use a trie , just regretting i woke up for this cringey contest
Za Warudo toki wo tomare !!!
Yare Yare Daze
Star Platinum..Za Warudoooooo!!!!
d
can u pls write why this round is so bad?
clown round, testers not doing their job properly, not even clown level this contest is the whole circus
But what didnt you like particularly
A fun contest. But getting TLE 46 on D...... why me. But he solution was O(nlogn) so it should have gotten AC
EDIT WHAT I GOT AC NOW THEY CHANGED THE TL
I don't think using a mass segment tree is a good idea when you can use scanline
Thanks for the 15 mins extension. I solved F in the last 3 mins (going back to master yeah). F is a really cool problem and I love it!
Finally, the cheaters were exposed this round. Thanks Youtube for wrong solution in problem C :D.
Me when FST on E
Edit: TLE on 68 because I forgor to remove a cerr that printed 2^16 arrays -_-
Literally the worst contest ever
why?
never saw these many bitwise questions in a single contest and apparently solution to C is available on the internet
that doesnt mean round is bad plus u dont even need internet solution u can just do naive and check, no even need to think
can u check my didnt my naive sol pass? also i mean the first submissiong BEFORE A
delete long long, add fast i/o, idk about pragmas, i often dont trust them
Fact is that if you have little variety of problems the contest is a little boring in my opinion
Maybe a little bit less bits problem next time XD
proof for problem C please, why we can't do better than max subarray?
In XOR operation XORing the same number twice (or even number of times) negates it 1 ^ 1 ^ 2 = 2 so when Dio summons a stand user at index i, when he summons another stand user, stand users from i till the end will be negated so he can use this to negate numbers that lowers total XOR in the end of the array to negate the ones in the front he can just choose i to be equal to the element after them when summoning the last stand user for example if we have this array: 3 7 2 5 8 1 6 4 1 the maximum subarray xor answer is 15 which is 8 ^ 1 ^ 6 so he needs to git rid of 3 7 2 5 from the start and 4 1 from the end to get rid of the 4 1 he summons a new stand user with strength = 4 ^ 1 = 5 so now we have 3 7 2 5 8 1 6 4 1 5 to now summon the stronger stand user he can he need to negate 3 7 2 5, so he chooses i to be the index of 8 when summoning it so its strength is 8 ^ 1 ^ 6 ^ 4 ^ 1 ^ 5 and 4 ^ 1 ^ 5 = 0 so the strength is 8 ^ 1 ^ 6 = 15 which is the maximum XOR subarray
thank you, but I already solved it by finding "maximum XOR subarray" in contest time, I mean why "maximum XOR subarray" will be the max answer which we can get, why answer can't be greater than "maximum XOR subarray" ?
For each summon you only negate (or return already negated) numbers from the array, you don't add new number , so there is no way you can get an array with XOR larger than the maximum (It may be possible if you can add numbers from outside the array, but you can't) When you summon a user you its strength is equal to the XOR of the subarray which starts with i and ends with the end of the array to summon the strongest user you need to choose i that makes the XOR of subarray = to the maximum (i.e. the maximum has to be in the end of the array) if it's not in the end you summon a user that negates the users after the last user in the maximum subarray
C can also be solved with dp https://mirror.codeforces.com/contest/1847/submission/212455218
What can't be done with dp :D Nice solution btw
Sad you had to copy from geeksforgeeks instead of dp
During contest when I figured out the approach. I was pretty much sure there must be some implementation so I googled it and pasted that solution.
And after the contest while having my dinner I also figured out that it can also be solved with dp
BTW I solved problem A also with dp
Interesting to see that your initials are also "DP":XD
Nice solution using dp. I was unable to understand why maximum xor subarray works here, that thing is not intuitive to me. But seeing your dp solution, it helped me get that intuition!
Could u please explain your dp solution. I am not able to understand ur dp states and transitions
2^8=256 which is not large so we can find all the possibility using our array elements.
Also our aim is to find maximum xorsum so we will update the maximum at each step.
and also when we are visiting any index with some xorsum then we can surely say that we can find all the coming subsequences using xorsum from that index. So we will not visit that xorsum and index again as it will give the same output.
In c everyone just copies tries code form online, please check plagiarism.
prewritten codes on the internet wont get into plagiarism. You may refer https://mirror.codeforces.com/blog/entry/8790
sorry, who can tell me why wa? I generate permutation, where p[i] is priority of symbol in string. Next i compare sum on prefix and all '1'. this
I made your solution AC, 212462179
thanks!
Ratings updated preliminary, it will be recalculated after removing the cheaters.
I solved C by BFS. There are only 256 possible states to look for.
I found E quite interesting! (although the implementation is tough)
edogawa_something orz
Why C was giving pretest 2 wrong when solved with Kadane's Algorithm
Maybe because xor != sum... Interesting that you ask questions like this and you got AC with trie solution
Can we approach B by doing binary search on answer,if yes how ? Thanks in advance
I've waited for 4 — No, 5000 years for this
I was trying F by offlining the queries and divide and conquer during contest but couldn't finish implementation. I made the following observations:
If there exists some x in the infinite sequence then it must be the bitwise or of some subarray of the given array (consider the given array to be circular in mind).
Or value of smaller subsegments appear first.
So for each query we can binary search the length l of smallest interval s.t. there exists a subarray of length l (if its start point lies on or before n — l + 1, otherwise length l + 1 i.e. OR[start][n] | OR[1][l + 1 — (n — start + 1)]) whose bitwise OR value is > given query but unfortunately, this is too slow (O(nlog(n))
So instead of answering them online we can offline them so that we do the binary search thing for multiple queries at the same time.
Thus we use divide and conquer where we essentially do binary search on min length of such an interval. If among all the subarray of length mid, the max possible or value is x then all queries with value < x must recurse left (< x) and rest on right (> x)
Since for all elements recursing to the left, x is also an option, we update their ans.
However, I am getting WA on test 3 with this approach. And I cannot figure out where I am wrong. Any suggestions would be helpful. Thanks in advance. My submission
Okay, now I am getting TLE on test 15. Can't figure out why. Link.
CHEATFORCES!
In problem D, i misunderstand the statement and ended up trying to solve a different version of it.
Here it is :
In this version we do operation on t instead of s and try to make t as lexicographically as large as possible. i don't know if it is solvable with dependent queries or not.
But it can be solved if queries were independent.
we can calculate number of ones after each update and sort it in non decreasing order and go from left to right. Let's say length is $$$len$$$ than we need to compute some prefix of segments such that it's total size if equal to our $$$len$$$ and we update these segments in segment tree as $$$seg[l]$$$++ and $$$seg[r + 1]$$$-- and now for our query we can easily calculate number of ones in our $$$len$$$ range and can get result for current query. We than go right and again push our pointer ahead in our ranges as mentioned above and do same thing again. Here we don't need to start again from 0 as we have sorted length (number of ones after update) of each query and we can continue after we stopped last time and do same.
But if queries were dependent as in problem d it is, than how to solve it ?
note that in this version we are updating t instead of s.
for problem f:
i am thinking that we will first find an array say maxs(n), where
maxs(i) = maximum bitwise or of i consecutive elements then we can do binary search and get suitable minimum i where maxs(i) > v, and then for that particular i we can again do some binary search or something to find exact position.
but here i am not able to find maxs(n) in less than o(n^2), could some one please give some hints regarding that.
Absolutely, F is greatly easier than E.
why my dp for C doesnt work ?
https://mirror.codeforces.com/contest/1847/submission/212438627
Please Bring Editorial :/
Interesting round,but with too mamy bitwise operation problem XD
problem C :Easy solution without dp https://mirror.codeforces.com/contest/1847/submission/212554250
I can not understand the third output in problem C. Can someone help me pls :(
void process() { cin >> n; memset(f, 0, sizeof f); f[0] = 1; int x = 0, res = 0; for (int i = 0; i < n; i++) { cin >> a[i]; x ^= a[i]; for (int j = 0; j < 1 << 8; j++) { if (f[x ^ j]) res = max(res, j); } f[x] = 1; } cout << res << "\n"; }