Привет, Codeforces!
Я очень рад пригласить вас на Codeforces Round #843 (Div. 2), который пройдет в Jan/10/2023 14:15 (Moscow time). Этот раунд будет рейтинговым для участников, чей рейтинг ниже, чем 2100.
Моя искренняя благодарность:
Wind_Eagle, BaluconisTima, kartel и Aleks5d за идеи задач для раунда, а также Wind_Eagle, BaluconisTima, kartel, VEGAnn и Vladik за разработку задач.
andrew, gepardo, 244mhq, vilcheuski — остальную команду авторов области, без которых этот раунд бы не состоялся.
BaluconisTima за прекрасные картинки, дополняющие все задачи.
MikeMirzayanov за платформы Codeforces и Polygon.
Вам, за то, что участвуете в этом раунде.
У вас будет 2.5 часа на решение 6 задач, одна из которых будет разбита на простую и сложную версии. Раунд основан на задачах первого тура третьего этапа республиканской олимпиады по информатике в Беларуси. Просьба всех белорусских школьников, участвовавших в третьем этапе, воздержаться от участия в раунде и обсуждения задач публично до конца раунда.
Я надеюсь, вам понравится раунд!
Тестировали раунд: MathBoy, FairyWinx, nnv-nick, K1ppy, olya.masaeva, Septimelon, PavelKorchagin, 4qqqq, kova1.
Разбалловка: (500+1000)-1000-1500-2000-2000-2500.
UPD. Разбалловка была изменена: (500+500)-1000-1500-2000-2250-3000.
UPD2: Поздравления победителям!
Проголосуйте за вашу любимую задачу!
Задача F: Лаборатория на Плутоне
UPD3: Наконец-то готов разбор: тык сюда
omg subtasks for A round
NOTE THE UNUSUAL TIMINGS!! Wish you positive delta!!
omg no green circle
I hope this round will be better and more interesting than before.
Which is better: Div. 2 or Div. 3 for those whose rank is higher than rookie?
Div.2
omg subtasks for A round
omg subtasks for A round
omg subtasks for A round
omg subtasks for A round
omg subtasks for A round
omg subtasks for A round
omg subtasks for A round
omg subtasks for A round
omg subtasks for A round
omg subtasks for A round
omg subtasks for round A
omg subtasks for round A
Just curious what's the meaning to reply this message recursively
omg subtasks for round A
I think (500+750) is better than (500+500).
Thank you, AHMADUL.
what is your age bro ?
My birthday was some days ago and now I am 13
I wish Belarusian students good luck on Belarusian Regional Olympiad.
I hope tasks will be interesting for you :)
Thanks for inviting
Please no more problems like edu 141B
Delete this they will surely give it then
That's was a good constructive problem. I like those problems because even newbie can solve it and i have seen even master are sometimes not able to solve them. Try till you get the right approach.(It's just how i see them haha).
could u try to post a blog about this server recently i got to know about this server where mass copiying happens https://discord.gg/6RskCNmG
could u post a blog about this server i recently got to know about this where mass copiying is happening https://discord.gg/6RskCNmG
bruh imagine advertising cheating
is there anything we could do?
they will create new accounts after bans anyway, so best we can do is not advertising them
As a tester, I'd like to say that problems are interesting imo and I recommend you to participate!
hope this time problem statement is clear :/
Bro there is now way you are now reaching pupil after 1 year. You are surely doing something wrong. Please analyze it quickly or else it will be too late. 3 months are more than enough for pupil if you are serious that is.
thanks bro.
https://codeforces.me/blog/entry/110965.
Hope This blog helps you Sir.
First time see a problem A with hard version
WOW Problem A 1500 point
long time since A had a subtask
now could you imagine if it was interactive as well :D
Omg! Yellow round.
Omg! Yellow round.
Amazing.
So it seems like from the score distribution, the whole problem A has the same difficulty as B right?
Dont include Mathematical Problems please.
Will this contest be as beauty-full as the last one.XD.
Finally a contest with friendly time to Chinese coders! Gl, hf!
Actually, 22:35(UTC+8) is not TOO unfriendly for who are used to staying up late. It's better called friendly time to Australian coders.
I remember that once there were two contests held at about 15:35(UTC+8) and 18:35(UTC+8) on the same day.
Of course it's a very friendly time.I can't stay up late because my father don't allow me to do that:)
Div2 A with subtasks? Sounds interesting,but I don't know if it will be a good problem.
OMG unusual starting time and subtasks for A!! Wish you positive delta!!
Finally, the opportunity presents itself. I will become a newbie again.
Hello can you upvote me to help me with my contribution.
No! I prefer Downvoting you.
Ok as you like but i don't think i did something that i should be minused
You act like a girl while being a boy
I down voted you, to show world doesn't work that way. :)
Plan to take part in this contest. Hope $$$\Delta \gt 0$$$ for me, and you too!
OMG, subtasks in problem A!
OMG, subtasks in problem A!
OMG, subtasks in problem A!
OMG, subtasks in problem A!
NOTE THE UNUSUAL TIME
Good time for Chinese.
Why some hacks are still in queue.
wow
wow
wow
OMG, subtasks in problem A!
My GPA is crying out
prove your loyalty to codeforces
8 pm is best time . We have classes at college .
nice u got a reason to skip classes :)
Hope it will be a wonderful contest with fantastic problems!
As a Chinese,I usually have to stay up late for the cf round, but today I can go to bed earlier, so enjoy it and have fun!
I suggest to do more A , B subtasks in the future
True Mate.
After this contest, I have to disagree.
Problem A2 is scaring me. I wouldn't have participated if I cared about my rating.
orz 244mhq
Why Delay 10 min Sir ??
Why Delay 10 min Sir ??
I have the same question.
Same question
Maybe rating update
Contest start time changed?
10 minutes postponed!
Yes, postponed by 10 mins. Good luck!
Thanks! I thought my country decreased its standard time by 10 minutes
bruh, save your logics for the contest lol
10 min. delay!
DelayForces
Now it's delay-master-forces.
Will there be second delay if the rating update of last contest still uncompleted?
Чёт так жалко белорусских школьников стало.
I love this world.
Love this contest! As I expected from CF Round #741's author.
Mee too :D
Thank you for participating! Round 842 was great too!
F is 100491E - Expedition to Mars on higher constraints but it's possible to adjust the intended solution to 4e5.
Actually, I agree with you it's just a matter of time to solve this version if you have a solution for that gym problem and 144 participants solved that problem already I guess so it's easy for them.
Tbf $$$n$$$ up to $$$500$$$ allows a lot more different approaches. When my team and I were solving that gym contest, we went for a solution that isn't really viable for $$$4 \cdot 10^5$$$. Well, at least I failed to fix it :(
The most balanced contest
true
I kinda feel bad for spiders with one leg(
You are not worried about $$$3\cdot10^5$$$-legged spiders, right?
legend says that spider is still tying his shoelaces.
For C when i run the code in my system it was giving correct output for testcase 1 , but its giving wrong output when run on codeforces for testcase 1 . Any Idea why so ? https://codeforces.me/contest/1775/submission/188754539
Nice problemset..
How to solve C?
If $$$x = n$$$, the answer is trivially $$$n$$$ itself.
If $$$x = 0$$$, this means that the most significant bit of $$$n$$$ must become 0 at some point. If this is the $$$a$$$-th bit from the right, then the first number to flip this bit is $$$2^a$$$ (single 1 followed by $$$a$$$ 0s). So the AND must include $$$2^a$$$ and we can see that $$$x$$$ AND $$$2^a$$$ is 0, so the answer is $$$2^a$$$.
Now $$$x$$$ must have at least one $$$1$$$. Find the last $$$1$$$ in $$$x$$$, and let's say it's at position $$$\ell$$$. Because bit $$$\ell$$$ is a 1, this means it was never flipped while incrementing the numbers, suggesting that all bits to the left of bit $$$\ell$$$ remain unchanged. So the prefix of $$$x$$$ up to bit $$$\ell$$$ must be equal to the prefix of $$$n$$$ up to bit $$$\ell$$$. If there is a mismatch, the answer is $$$-1$$$.
We can now write $$$x$$$ as some $$$prefix$$$ (which ends with a 1) followed by all 0s, and $$$n$$$ as the same $$$prefix$$$ followed by some $$$suffix$$$ (whose length matches the block of 0s at the end of $$$x$$$). There are two further cases to consider:
If the $$$suffix$$$ begins with a 1, then we have a problem. Since this bit is 0 in $$$x$$$, it must be flipped at some point. But flipping this 1 will also flip the 1 to its left, i.e., the last bit of the $$$prefix$$$. But we know that the $$$prefix$$$ cannot change, so this scenario cannot happen, i.e., answer is $$$-1$$$.
Otherwise, find the first 1 in the $$$suffix$$$. Let's say it's in position $$$c$$$ (from the right). This bit is 0 in $$$x$$$, so it must be flipped at some point. When this bit is first flipped, the bit at its immediate left (position $$$c + 1$$$) becomes 1, and everything after it becomes 0. This number is $$$x + 2^{c + 1}$$$, i.e., the common $$$prefix$$$ followed by all 0s except a 1 in position $$$c + 1$$$. Conveniently, applying AND between this number and $$$n$$$ will already yield $$$x$$$ (the only $$$1$$$ after the prefix is at position $$$c + 1$$$, which is a 0 in $$$n$$$), so this number is the answer.
My submission: 188732906. I converted the numbers to binary first, and worked from there, converting back when printing the answer (except when the answer was $$$n$$$ or $$$x$$$ itself).
"I converted the numbers to binary first, and worked from there, converting back when printing the answer."
Conveniently for me, my computer stores numbers as binary internally so I never need to convert back and forth.
lol, yeah, I know I can use bit shifts to process them faster, but binary strings are more readable imo. I don't have enough experience with bit shifting to be confident that I can code the correct solution with lower thinking + typing time.
Answer will always lie between n and INT64MAX and bitwise and from n to k >= bitwise and from n to k+1 therefore you can apply binary search . To find bitwise and from n to k you can search on net and get method easily .
"Time limit exceeded on pretest 12"
no need to look at one prime number more than once during bfs (this helped me with test 12)
I hate A so much that I mistook subarray for subsequence in B.OMG I didn't read this in problem A
The name of each capybara is a non-empty line consisting of letters "a" and "b".
Problem A-D is interesting.
How to solve F?
I suspect giant casework.
Actually, no. The short idea is that all the possible answers are just rectangles with their angles cut somehow. You need to make a DP on how you cut the angles and iterate over the possible rectangles.
For example, if $$$n=7$$$, then the optimal perimeter is $$$12$$$, and you need to try out the rectangles $$$3\times3$$$, $$$4\times2$$$ and $$$2\times4$$$ and cut their four angles somehow. A cut of an angle is just removing a stair-like figure, so it's calculated with DP.
Ah got it, problem seems interesting now!
The idea is actually obvious, can you tell how to calculate the DP?
You may precalculate $$$dp_{n,k}$$$, that is the number of stairs from $$$n$$$ blocks which are $$$k$$$-block tall. This DP can be computed in $$$O(n^2)$$$, but, since the number of blocks to be cut from angles is no more than $$$O(\sqrt n)$$$ in total, it's OK.
Then, you just need to write another DP which decides on how much blocks to cut from each angle. It's $$$d_{i,j}$$$ where we have decided about the first $$$i$$$ angles and have already cut $$$j$$$ blocks.
Note that all these DPs can be calculated in the beginning and used to answer all of the testcases.
Got it, thanks!
But how do you check that the stairs in different angles do not intersect while calculating $$$d_{i, j}$$$?
You don't have to check it.
If they are going to intersect, then the perimeter is just not optimal.
Oh yeah, fair enough. It was the only part I was struggling with and this observation is so easy (( Thanks a lot!!
They will not intersect. Because if it is possible, you can decrease the perimeter of your figure.
Any idea of B? I've tried many times but always got TLE
Also please update the rating of last educational round quickly
What I have done, is to count the no of occurrence of a bit throughout the whole array. Then for each element in the array if any bit which is set for this element is also set for any other element, Then the ans is always yes otherwise no
Let me explain the reason with an example ,consider a no whose bit 2 and 4 is set. Another no whose bit 2,1 and 3 is set and another no whose bit 4, 5 and 7 is set. Since For First No, every bit that is set for this, also set for either b and c, so we can always take Or of every no in the array and Or of every No except that No(First one in this case). In Other words f(a) = Second No | Third No, f(b) = First No | Second No | Third No. Hence Ans is always possible.
Here is my submission 188728251
If bits set in one number is a subset of another number , then the answer is always possible.
what about 4 number {1,2} , {4,3} , {1,3} , {2,4}
Yes in that case also the answer is possible.
We need to check for every number if the occurrence of all the bits in this number is > 1. If it is satisfied, then the answer is Yes.
Looks like you cheated in this round.
Nah dude , I just failed at explaining my idea xD.
Did you by any chance used a fixed-size frequency array? freq[200001] * n <= 10e5 = TLE... I should know from having fallen for it 5 times this contest.
So we need to use map for frequency?
Yes, I changed to map for frequency and got AC with 300 ms
OHHHHHH I just skipped B......
Yes, map for frequency.
I've thought Double linked-list and priority-queue could solve E, but got WA.
when I used vector to store the frequencies I got the TLE, but then changed to unordered_map it passed. not sure why vector[i] is slower than map[i] :(
I used int[200001] and got TLE 5 times because I forgot n <= 10e5 so I was doing 200000 operations per test case just setting up a frequency array.
now I get it, thanks
Hint: the first subsequence is the whole array, the second is the whole array except only one number.
I've noticed that but my approach got TLE
It seems that we need to store frequencies by map instead of array
You can use array, but it should be global. Furthermore, you should only set the elements you touch to 0, not the full array.
How to solve E?
Let $$$s_1$$$ be the maximum sum over all subarrays and $$$s_2$$$ be the minimum sum over all subarrays, then the answer is $$$\max(s_1,-s_2)$$$.
Lower bound
Clearly you can change the sum of some subarray by at most 1 per operation, so the answer can't be lower than $$$\max(s_1,-s_2)$$$.
Upper bound
For simplicity we suppose $$$s_1 \gt -s_2$$$.
Consider the following rules:
Adjacent positive elements are automatically merged into their sum. (The same for negative elements)
Zeros are automatically removed from the array.
It can be shown the answer won't change if we apply the rules.
After merging, we can repeatly try to change every element closer to 0 and apply the rules after each operation. It can be shown it's optimal. The sum of the greatest subarray will always reduce by 1 after each operation. (If we can't at some moment, then it's not the greatest subarray.)
If the answer is greater than $$$s_1$$$, then there exists a subarray with sum greater than $$$s_1$$$, which is a contradiction.
currently, your comment helps pretty much noone except those who just who want to see a AC and be done with the problem.
What was the idea? how did you come up with it?
Errorgorn's solution makes much mose sense in that regards
The intuition is that after each operation, the total sum of the elements changes by $$$-1, 0$$$, or $$$+1$$$. So if the current sum is $$$s$$$, then the answer is at least $$$abs(s)$$$.
The second thing to note here is that the answer for the whole array is at least the answer for some consecutive subarrays. So the answer is at least the maximum of the absolute value over all subarray sums.
Seems like this is achievable. But I currently don't have a proof for this. I have solved it using the same approach that errogorn used in the next comment.
Sorry, it's my bad. I've added some details.
We will process elements left to right. When processing some element, we either create new operation or extend some old operation.
Intuitively, it makes sense that we would not have to using operations to both add and subtract from an element. So a simple $$$O(n)$$$ greedy works.
Thank you very much!
Is there any formal proof? (or an outline of a formal one)
The red and blue are different operations. If we delete the middle operations in the green box, we can merge the left red operation with the right blue operation and also merge the left blue operation with the right red operation.
This way, we will never both add and subtract from the same element in an optimal solution.
Think about a sequence of prefix sums and observer how such operation affects this sequence of prefix sums.
If you analyze carefully enough, then you'll see that one of the operations just adds $$$1$$$ to any subsequence of prefix sums, and the other operations just subtracts $$$1$$$ from any subsequence of prefix sums.
So, AFAIK you just need $$$\max(0, \max(p_i)) + \max(0, \max(-p_i))$$$ where $$$p_i$$$ is the array of prefix sums.
Thank you for the second solution!
I take back my words, it was a nice round.
F: Why did you set two types of questions as one problem? The difficulty levels of the two questions are different, so I think they should be set as separate problems.
A problem of calculating the number of ways was very interesting!!
I think subtask 1 is as easy as problem A...
You are right probably, it should be split.
By the way, the original contest is OI-style, so there two problems were combined as one, with different groups for each of the subproblems. For Codeforces, the problem was just retained as-is.
can we use binary search for Problem C? since & is decreasing function, bitwise and of all number from n to m will be higher than x initially. We need to find first position where bitwise and of all number from n to m is x
Problem E almost = This Problem
Yes, you are right, sorry for that :(
It's interesting that the round with the similar problem is also of Belarusian origin, but the authors came up with the idea independently AFAIK, so it's an unfortunate coincidence.
Very nice contest! Congrats to the authors!
lol, img when i got wrong ans on test 15 problem D and it was only 5 minutes left
bruh I feel like a total loser, but at least I'm trying and participating lol
if i solved a problem correctly in contest and later during contest , by mistake i submit wrong code for that problem then is question point are added or not to my points
In problem B, I read "exclusive or" instead of "bitwise or" and was thinking how to find out if the set of sparse binary vectors is linearly independent and why it is Div2.B
I did this too xD...
String consists of letters 'a' and 'b' only :) could have written it in black :)))
Wow, now I do remember that I did read that line, but after reading that whole description, I actually forgot about it :)
Moreover, the divided strings were ofcourse named
a,bandc,which even cut the possibilities of me thinking about the string only consisting ofaandbfor once :)Well, I just knew about it know.....
I think B problem cannot be solved by people who use JAVA because my O (n * k) solution is getting TLE even after using the fastest I/O operations. Link to my Submission :- https://codeforces.me/contest/1775/submission/188733443
Fixed-size frequency array is unsafe, n <= 10e5 so setting up a frequency array for each test case will instantly TLE you. USe map/hashmap because k constraint is guaranteed to be <= 10e5
You are saying that as t <= 10^5, so the freq array of size 2 * 10^5 (max p) will be iniatialized for each t which will give TLE and everytime initializing a fixed length array is not good beacuse there may be a case when max p is very small but still I am iterating till 2 * 10^5 every time which is unnecessary and the reason for TLE. But HashMap will not give TLE beacuse when we initialize a HashMap its initial size is very small due to which it will not give TLE. Right?
Yes
if i solved a problem correctly in contest and later during contest , by mistake i submit wrong code for that problem then is question points are added or not to my points
how to solve problem b??
denote bitwise-OR of the whole array as S. if there exists an element x such that removing x from the original array won't affact S, the answer must be an "yes"
if there isn't such an x, the answer is "no". figure out why.
In task A, either the string b is lexicographically not smaller than the strings a and c at the same time, or the string b is lexicographically not greater than the strings a and c at the same time. @authors kindly look into the language
Screencast with commentary
didn't read "The string consists of English letters 'a' and 'b' only." this part in A, So I solved it for every character and I had to use Z function for prefix comparison XD
Task is easily solvable for the greater alphabet. Soon we will post the editorial.
Now that I have though about it more, you're right
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
realized a b only after reading this comment
I didn't read that either. Here is my solution: 188713747.
Upd: it is wrong
Accepted in last 4th sec.
Can't understand why for B:
answer is YES?
Next follow ki distinct integers pi,1,pi,2,…,pi,ki (1≤pi≤2⋅10e5)
Lol, didn't see that.
Ki integers are guaranteed to be distinct
This input is not valid, since the set bits must be distinct. For example, in the line
3 8 2 2, the given set bits are 8, 2, and 2, which is not a valid input. In the line3 8 3 3, the given set bits are 8, 3, and 3, which is also not a valid input.If you actually meant the following:
then the answer is NO.
Nice problems. Hope to see more contests like this in the future
Will this round be rated for who has reached 2100+ from 2100- in the last educational round?
Overlooking "the characters are A or B" from A2 took me 1hr...
I can't proof my solution for A2 (but it's allowed to use A-Z) so please hack it: 188722831
This is actually a correct solution, if I'm not mistaken. For an arbitrary alphabet, if answer exists, then there exists such answer that |b| = 1. You can now solve task by bruteforce in O(n).
I saw the A or B part, but didn't have a very good proof, so I solved it the most stupid way imaginable.
submission: 188710406
I also overlook the a or b term which waste my 1.5 hours. And if am not wrong, the sentence which told that specific a or b term in A2 is added later on the contest. I have solved this through an observation that excluding the first and last character, if there exists an a then if I take it as the second word then it remains the smaller or equal the other two word which are the left and right part of the taken second word. If excluding the first and last character, there not exists an a then it should be the occurrences b and if I take those consecutive b as the second word and the first and last character respectively as the first and last word then the second word remains bigger or equal than the first and last word. In such these way, under the constraints of the problem there always exists a valid answer.
And if am not wrong, the sentence which told that specific a or b term in A2 is added later on the contest
You are wrong and just try to justify yourself.
Intrestingly, this is the original problem that was given in the olympiad. It took me 1h40m to solve it, and when I saw codeforces standings, I was absolutely shocked by amount of people who solved it that quickly.
didn't notice the unusual timing :facepalm:
For C when i run the code in my system it was giving correct output for testcase 1 , but its giving wrong output when run on codeforces for testcase 1 . Any Idea why so ? https://codeforces.me/contest/1775/submission/188754539
In my system, your submission is giving wrong answer only for the last test case.
what about the output here . https://www.onlinegdb.com/online_c++_compiler
That's weird ;)
You're doing
ll rem=(1ll<<i)-(i?pre[i-1]:0);inside a for loop whereican equal0, meaning you're trying to dopre[-1]which points you to other memory. This is why the code doesn't work or works differently on different machines.But i am checking for the case i==0
Oh, how did I not see that. Sorry.
Maybe an overflow is happening. Change LONG_MAX to 1e18+1
And don't forget, that in the case of n and x being both zero, your pre will be 0 sized, which gives an error
Thanks Bro .I changed LONG_MAX to 1e18 and it worked . But any idea why so ?
It seems, that LONG_MAX doesn't work on cf. It returns 2147483647(int_max) on cf, and 9223372036854775807 on onlinegdb. This wasn't an overflow then
Best ever standing and solved problem C in Div. 2 the first time! But I didn't have any clue of problem B :(
See the count of the i-th bit appears in the input.
Check if for every number there exist a bit that appears in the input count is 1 than the answer is "NO" else "YES".
but how are we sure that if we cant remove any element such that or of remaining element is same then answer will not exist?
If for every number there is a unique bit that only appears into that number than to make the difference in the sequence you need to not take this one. If all the numbers contains a bit that is unique in them you have only two options either take all of them or nothing. To make them different we take both as these are the only options but there OR is not same.
It seems that we should check every number in array c, if there exists one i, every bit in c[i] appears 2 times in the whole input, then the answer is "YES", otherwise "NO".
poor English :( Obviously the maximum set is a1 or a2 or ... or an .So let p is this subsequence.
To find q, the number of elements in q must be at least 2.In this case, without q the p has no elements left.
The set is in binary system.（二进制）
Some discussion for E:
The main purpose of operation is to decrease the value of sum(|ai|) (the sum of the absolute values of ai), to achieve this purpose, we need to subtract from positive numbers, and add to negative numbers.
So every time when we choose subsequence, we can assume we always choose it with alternative sign (which like {+a1, -a2, +a3, -a4...} or {-a1, +a2, -a3, +a4...}), because if not, we can remove 2 adjacent element with same sign, and the total change of sum(|ai|) remain the same.
Therefore, we can always choose the longest subsequence with alternative sign. We can regard some consecutive elements with same sime as one element, and regard zeros as not exist. So we can rewrite the initial array as some non-zero numbers with alternative sign, each element represents the sum of a maximal block with same sign.
So we can get the answer: In each step, we do min(|ai|) times of operation, and all |ai| will be decreased by that value, then we remove zeros from the array, and merge adjacent elements with the same sign. However, this naive approach will be O(n^2) and get TLE. How to optimize it? Notice that if we do min(|ai|) times of operation, some elements will become 0, and it's adjacent elements will be in the same "block with same sign" now. So we could store the initial array into a double linked-list, whose node is like (long:value, Node:prev, Node:next, boolean:valid) and put each node in a priority queue. Each time we poll out a valid node from the priority queue, we merge it with node.prev and node.next to get a new node, link it with node.prev.prev and node.next.next, add it to the priority queue, then mark node.prev and node.next as invalid. Then we could get an O(n*log(n)) solution. (Also do not forget check nullity)
Update: Now my submission:188766704 has got AC. Unfortunately, I've not implemented it properly during the contest. Sad!
Mmmmmm
Mmmmm
Right after the contest :D
Wonderful round with great problems, it seems they all have clean solutions, but require "cute" observations. A2 is harder than E for me though (failed system testing on A2).
To problem B: Why is this case no？ 1 3 2 1 2 2 3 4 2 5 6
Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!
But the rating of last educational round has not updated yet! Please update it first! I should have been div1 in this contest......
Oh, sorry for that, our fault. Will fix soon.
Thanks very much (for saving my rating)!
fixed, you got your rating back :)
I might be wrong, but I think whether the contest is rated for you or not depends on which rating you had at the time of registration. Even if the rating for the edu round was updated before this contest but after registration, this contest would still have counted for you.
In fact, this is why some users deliberately register for as many contests as they're able to when they're close to the border, so that they're all counted even if they cross the border sometime in the middle, e.g., earning Div2 rating boosts even after reaching Div1.
So regardless of when the ratings are updated, it should not change the fact that this round will be rated for you. In the future, please consider your rating at the time of registration before you decide to register for a contest, since rating changes that were not yet applied would not be considered for the contest you're registering for.
Huh, thank God I took this div2 seriously :) Otherwise my M would have lasted less than 24 hours.
Problem D was nice.
I agree. It was a very nice combination of Sieve and BFS.
Wait, can we use DSU for problem D ?
I don't think so as DSU can tell about the connected component but we need shortest path.
very good round. problem are so interesting.
I liked the problems themselves, but I have two minor issues with the presentation:
For Problem B, the input format was rather unusual, so I think it would have helped immensely if there was an example of a line in the given input format with an indication of what number it represents (preferably in both binary and decimal). As it is, I think the problem looks rather intimidating, despite actually being very simple, especially since participants do not even need to be aware of how to code bit operations to solve this.
For Problem C, specifying that the answer is guaranteed to be bounded below $$$5 \cdot 10^{18}$$$ is rather misleading, and notably suggests that a standard 64-bit signed integer type (like
long longin C++) is insufficient. However, the actual upper bound is much lower (I think it's $$$2^{60}$$$), so 64-bit signed integer type would actually have been fine. But having the constraints specify $$$5 \cdot 10^{18}$$$ can scare away participants who memorized the upper bound for 64-bit signed integers before they could figure out that the upper bound was highly overestimated or that an unsigned 64-bit type would have worked regardless.These are minor issues, but I think they serve as obstacles for less-experienced programmers who might otherwise have been able to solve these problems more smoothly, and I don't think early problems like B and C are good places to punish them for these kinds of little details.
The max value of signed int64 is 2^63-1=9.223*10^18, which is definitely larger than 5*10^18.
Oops, sorry, you're right. I was mistaken in thinking that was the unsigned upper bound. That being said, I don't think I'm alone in making such a mistake, so I do still think the overestimated upper bound can be intimidating for many, regardless.
Most problems I see that involve
long longcalculations use an upper bound of $$$10^{18}$$$, or (more rarely) $$$2 \cdot 10^{18}$$$ if intermediate values are not expected to overflow. An upper bound of $$$5 \cdot 10^{18}$$$ is quite unusual, especially for a C problem.How to solve C?
Find a way to compute the value of x & (x+1) & .... &(x+m) in O(lg n).
Binary search
what is wrong with this submission 188779455 for problem C. Time limit exceeded.
TLE is due to
1 << msb_p1, it is fine for32bit numbers but not for64bit numbers.You may see my submission
Thanks coderdhanraj
you can either use binary search or can use maths!
check this
How to solve D? I tried to construct and graph using prime factors and then apply DFS but got WA.
DFS ? I think you mean BFS
Use BFS to get the shortest path. DFS is not for shortest paths.
I believe dfs (or DP) can be only used for Directed Acyclic graphs to find shortest path between nodes. anyone correct me if I'm wrong.
Actually both are used to find the shortest path in DAG. First using DFS for finding the topological sort and then according to topological sort apply the dp.
Is the jiangly's answer corrent for this case of problem A?
1 abcbbc
The string only contains letters 'a' and 'b'.
The string only consists of "a" and "b".
String consists only of letters 'a' and 'b'.
I think this solution 188779455 works in O((log(n))^2) for problem C
Time Limit Exceeded on problem C
You should do
ll msb_val = (1ll << msb_p1);instead ofll msb_val = (1 << msb_p1);in yourandOperatorfunction. Also you should initialisehivariable in your binary search to a much larger value(2e18 should work).Thanks for the help. It is now accepted.
Hello, Why is this giving TLE?(Solution for B) When I replaced the vector cnt with map, it got accepted Solution for B
Hi, Why is this giving tle?...When i replaced vector cnt with map it got accepted Solution for B
this is a multi-testcases problem, every time you create vector cnt(2e5+1);
10^5 * (2e5+1)
Holy fk!!! IT's so obvious.... THanks man I forgot that there is no upper bound on sum of n values over all testcases
C can be solved in $$$O(\log n)$$$ without binary search. Here is how.
Notice how a zero appears periodically at a certain digit in the binary representation. For the last digit it appears every two places, for the second to last digit it appears two in every four places, and so on. Now assume $$$n$$$ had a 1 on a certain digit, but $$$x$$$ had a $$$0$$$ on that same digit. We can exactly find the next value that will have a $$$0$$$ in that digit using arithmetic progressions. Alter $$$n$$$ incrementally using this method on every digit. Check if the range AND matches $$$x$$$, and output the answer.
Submission: 188740550
It can be solved in $$$O(\log \log n)$$$. You just need to find the most significant bit that differs.
Wouldn't that still be $$$O(\log n)$$$ with a very small constant (or with minor improvements/pruning)? I don't remember
__builtin_clzbeing $$$O(\log \log n)$$$.I believe you meant binary search on numbers around 1e18. The point of my message was, that it can be solved asymptotically faster. Though it uses binary search on bits ($$$\log 60$$$).
Excuse me, I wonder to know how the functions nextbitoff and rangeand work. I simulated it, but I still don't know why it is correct.
One of the best round! Loved it!
Wind_Eagle Hello. Nice round with cool problems. I think the testers happened to miss out on big powers on B despite the pretests on B including big powers some solutions passed due to UB nature of C++.
My solution is pretty straightforward so I feel the testers were just unlucky not to find a possibility of such a FST.
That's my only bit of feedback. D is a nice implementation problem.
OMG. I misread B's statement thinking the problem is about XOR even after rereading a couple of times
and in C I did the same..
I hate your profile picture
Have you downloaded that cool vscode extension?
so is it possible to solve if it is XOR?
I couldn't come up with a linear solution
In the first test case, the only possible way to split the line s into three lines is "b", "bb", "a".I'd been wondering for over half an hour why the first test case has only one solution. I thought I misunderstood the problem and kept on re-reading the description in case I missed something. But then I realized that the statement had been secretly changed...
In the first test case, one of the possible ways to split the line s into three lines is "b", "bb", "a".I believe it would be better if contestants receive notification after any problem statement change.
can anyone tell which test case i am missing here is the link of my code code
why would you even do that? just had to check for the presence of duplicate elements, please check here
thanks
This was a great round involving interesting bits . No pun intended. I found them interesting and made editorial videos on these, you can check them at this channel- here
Still can't believe the implementation of a div2E problem could be as easy as "find the difference of the maximal prefix sum and the minimal" which could be implemented by anybody. What an excellent problem. I just implemented a complicated O(n*log(n)) algorithm and couldn't debug it before the contest ended.
The proof is simple. Let $$$sum_{i}=a_{1}+...+a_{i}$$$, $$$sum_{0}=0$$$, $$$f(a)=max(sum)$$$, $$$g(a)=-min(sum)$$$. In the final state $$$f(a)=g(a)=0$$$. And because after any operation, any prefix sum could change by at most $$$1$$$, the value of $$$f(a)$$$, $$$g(a)$$$ can be reduced by at most $$$1$$$. And if $$$sum_{i}=f(a)$$$, $$$sum_{j}=-g(a)$$$, $$$i \lt j$$$, and in an operation $$$sum_{i}$$$ was decreased by $$$1$$$, then the change of sum of range $$$[i+1,j]$$$ could only be $$$+1$$$ or $$$0$$$ (because $$$+1$$$ and $$$-1$$$ appears alternatively), so the change of $$$sum_{j}$$$ could be $$$0$$$ or $$$-1$$$, which means $$$f(a)$$$ and $$$g(a)$$$ cannot be reduced simultaneously. (Situation when $$$j \lt i$$$ is similar) Therefore, $$$ans \le f(a)+g(a)$$$. To make sure in every operation $$$f(a)+g(a)$$$ is reduced by $$$1$$$, WLOG we can assume $$$f(a) \gt 0$$$, then let $$$i_{1}, i_{2}, ..., i_{m}$$$ are all indexes where $$$sum_{i}=f(a)$$$ and $$$a_{i} \gt 0$$$, we reduce such $$$a_{i}$$$ by $$$1$$$. Because $$$sum_{i_{1}}=sum_{i_{2}}=max(sum)$$$, and $$$a_{i_{2}} \gt 0$$$, there must be a negative number in range $$$[i_{1} + 1, i_{2} - 1]$$$ (otherwise $$$sum_{i_{2}} \gt sum_{i_{1}}$$$), so we could increase it by $$$1$$$. For every pair $$$(i_{t}, i_{t+1})$$$ we find such a negative number to put into the subsequence of the operation, then $$$f(a)$$$ will be reduced by $$$1$$$. Also this could make $$$g(a)$$$ increase, so we also need let $$$j_{1}, j_{2}, ..., j_{r}$$$ in the subsequence, where $$$sum_{j}=-g(a)$$$, $$$a_{j} \lt 0$$$. Similarly, there must be a positive number between $$$(j_{t}, j_{t+1})$$$. Now we find that $$$f(a)+g(a)$$$ could be decreased by $$$1$$$ in any operation. So $$$ans=f(a)+g(a)$$$.
.....Wait, simple? How I've typed so much......
Well, I read your proof 5 times but could not understand a single sentence ;-; Any simpler explanation? O-O
Umm… It's better to waiting for official editorial…
operation + — + — + — is just +1 on some intervals in prefix summ array ..... (+1 +1 +1) ..... (+1 +1 +1) .... (any set of intervals you want)
operation — + — + — + is just -1 on some intervals in prefix summ array ..... (-1 -1 -1) ..... (-1 -1 -1) ....
and you want to make array of prefix summ = [0, 0, 0, 0, 0, 0, 0, 0, 0]
and its not actually max — min its max(max — min, max, abs(min))
for case with every pref summ > 0 or every pref summ < 0
A Great Round!
But I failed to become Master as I had promised. : (
I have question for problem B
What subsequences are proper for such arrays?
I think it is impossible to find such sequences to obtain the same OR result. This is 7-th token for test 2.
https://codeforces.me/contest/1775/submission/188813071
$$$[1,2,3]$$$ and $$$[1,2]$$$ are valid.
if you take the OR of all three and then only of first two they are the same
Oh! chromate00 told already
Problem setter was bad. Still they do not add a dislike button for each problem. What a strategy! Shame on you!
Were the problems mathematical?
Problem setter is apparently a big fan of observation problems : Have a Look
Ah it hurts man!
Its too hard to live with 1399 rating
Abito can relate this very well.
Ikr. It really sucks
Is the new test data for question D an attempt to get dijkstra stuck?
Hardest task A i've ever seen (div2)
For problem C, many have used this logic. Can someone explain this logic with proof, and with an example
for(ans=n;ans&&ans!=x;) ans&=n+=n&-n; ans==x?printf("%lld\n",n):printf("-1\n");
For integer x,if x&y ( y < lowbit(x) ). For example, x=101000B, y=100B, m=x&y, the last 3 digits of m have to be 0, it means that the last 3 digits of m won't change. To change the last 4th digit of m, x must be added an integer which is greater than 1000B, and then x=110000B,it can make the last 4th digit of result equal to 0.
Where's the solution or editorial?
Thanks!
It will be posted soon. We need to translate it from Russian.
Russian analysis of the solution to the problems as well please put it out.
I got a delta of +77 in Educational Round 133 with initial rating of 1333 and rank of 3959.
But I only get a delda of +36 this time with initial rating of 1392 and rank of 2185.
I thought I might get a delta over +100, it's far from my expection :(, and I'm confused.
Problem F is about partition number, which need to prepare the partition number up to sqrt(n) (partition number of n is the number of unordered tuples of positive integers (a1, a2, ..., a_k) where sum of a_i is n), and calculate it's 4th convolution power (by doing self-convolution twice). Although the unknown mod number disabled FFT, we can calculate it directly since sqrt(n)<640 is small enough.
Why convolution gives correct result?
Assume that the minimal rectangle contains the rectangle is a*b, we need to remove a*b-n=k blocks and remain the perimeter unchanged. First consider the situation which we only remove from the upper left corner. Let r1,r2,r3… is the number of blocks we'll remove from the 1st, 2nd, 3rd… row. We can observe if the perimeter is remained, r1 >= r2 >= r3… must hold. Thus number of ways to remove k blocks from one corner is p[k] where p is array of partition numbers. If we need to remove from all 4 corners, let for each corner we remove k1, k2, k3, k4 blocks, where 0<=k_i<=k, sum(k_i)=k, the total number of ways to remove k blocks is sum(product(p[k_i])), where {k_i} iterates over all 4-tuples which satisfies the former condition. That's the definition of convolution (the convolution of array a and b is conv(a,b)[n]=sum(a[i]b[n-i]), which is equivalent to sum(a[i]b[j]) where i+j=n).
Thank you. How we make sure that removed blocks don't intersect?
If the upper left corner intersect with the upper right corner, then the top row will be completely removed, which means the perimeter will be lower, so the initial perimeter is not optimal. Therefore, if the initial perimeter is optimal, the blocks removed in corner will not intersect.
While the problems A-E were nice, problem F blew my mind, huge props to authors! It is the best problem i have solved in 2023 so far. My friend and i spent around 2 school days on this one and we had a blast :).
Deleted.
Deleted.
Deleted.