Hello Codeforces!
flamestorm, SlavicG, MikeMirzayanov and I want to invite you to Codeforces Round 849 (Div. 4).
It starts on Feb/03/2023 17:35 (Moscow time).
The format of the event will be identical to Div. 3 rounds:
- 5-8 tasks;
- ICPC rules with a penalty of 10 minutes for an incorrect submission;
- 12-hour phase of open hacks after the end of the round (hacks do not give additional points)
- after the end of the open hacking phase, all solutions will be tested on the updated set of tests, and the ratings recalculated
- by default, only "trusted" participants are shown in the results table (but the rating will be recalculated for all with initial ratings less than 1400 or you are an unrated participant/newcomer).
We urge participants whose rating is 1400+ not to register new accounts for the purpose of narcissism but to take part unofficially. Please do not spoil the contest for the official participants.
Only trusted participants of the fourth division will be included in the official standings table. This is a forced measure for combating unsporting behaviour. To qualify as a trusted participant of the fourth division, you must:
- take part in at least five rated rounds (and solve at least one problem in each of them),
- do not have a point of 1400 or higher in the rating.
Regardless of whether you are a trusted participant of the fourth division or not, if your rating is less than 1400 (or you are a newcomer/unrated), then the round will be rated for you.
Many thanks to the testers: _Vanilla_, badlad, Gheal, Phantom_Performer, Kita, Nihad_Nabelsi, prvocislo, keta_tsimakuridze, Bakry, RedstoneGamer22, tibinyte2006, KrowSavcik, haochenkang, myvaluska, sandry24, BucketPotato, Vladosiya, pashka.
We suggest reading all of the problems and hope you will find them interesting!
Good Luck!
UPD: Editorial is posted.
Hell yeah!!
Eat an ice cream for positive delta :D
Done Sir.
i did it and finally get a positive delta lol
Ate this too much!!, Hope to reach specialist in this round.. After performing like specialist in some rounds, there comes one round such that sometimes I am not able to perform as expected. It's all about consistency.. Will try my best in tomorrow's div 4 round. Wish me luck :)
As a tester, I suggest you participate!
As a tester, I enjoyed this round and I recommend everyone to participate!
As a newbie tester I recommend fellow newbies to participate :)
I want this round to be unrated!!!
Just don't participated live and give it virtually after contest. Ez Win.
first unrated
Also my first unrated!
It's not.
My rating hasn't updated yet, but any rating change I get from this round will be roll backed when they rate yesterday's round
How many times are you people gonna repost this
FOREVER!
As a tester, this is the best div4 I've tested so far.
As a tester, I want more upvotes than Gheal.
[ Deleted ]
Insha Allah.
As a tester, I enjoyed this round so much I forgot I was testing
Another round for fast code writing.
First, please update the rating of the two past tests!
Eagerly waited for unrated contest.
As a tester, i loved this contest too much but not more than
.
I am very excited for this contest, may be it will be a good contest for all the newbies like me, to become pupil or specialist
Finally my time to shine.
I let my rating sink to be rated for div4. Lets go!!
Good luck.
Same to u :)
Hope in this contest my rating will increase...who else is thinking.... Thanks Codeforces and mesanu,flamestorm,MikeMirzayanov for this contest...:)
THANK YOU SlavicG GUGUSTIUC
Will I be rated for this contest?
yes it will be rated for you. however, you will not be included in official standings because you have participated in < 5 rated rounds. this round is rated for all people with rating < 1400
Yes
At the end of the contest , some people will be happy and some will be sad, Be of the first kind
Can you please change the staring time of the contest? It starts after the Izho and info(1)cup contest. It would be great if you changed the time a bit later or to another day.
.
The world doesn't work that way brother.
)
omg keta_tsimakuridze tester
omg prvocislo tester
Let's Goo
omg mesanu and flamestorm setters
dude you forgot your signature
Marinush
Good weekend, good div.4!!!
It's been six days since typeDB round has finished still no problem rating update and no user rating update. Something weird there's been about the codeforces recently.
deleted
Good Luck contest For Every One
This contest must be successful for EveryBody
OMG SlavicG Round!
Finally, my first div-4 contest after becoming specialist
Will I be rated in this round cause the rating of last div2 round hasn't been updated yet and I am still a pupil,but if last round's rating update I will become specialist.
ratings roll back again of Last Div 3
I'm wondering how the rating will change for those who turned to be a specialist in the last div2 round, if it is rated.
or in any of the last 3 contests
The rating should be updated now
Does the Penalty start from the begin of the contest or my first visit to contest/codeforces?? like if the contest start on 2:00 and I enterd the contest 2:30 and solved a problem at 2:35. Then the Penalty equal 35 or 5?
35
congratulation SlavicG for becoming CM from expert
Woooahahshasfhazfz
Can't wait to see hmzqaq's performance in this round. (He's duck_pear)
..
You waste your mother's time for nine months.
Marinush
Stringforces!
Good Div4 round, like always!
G2 is quite hard for div4..?
Who's the cool Pikachu in problem B?
Nice problem set, solved all😊
how to solve F?? by not getting tle
Seems like lazy propogation on segment tree. Calculating the value is O(1) as sum of digits would convert to a single digit in 2-3 operations.
You have to realize that for any a[i] you really only do the operation a couple times, and then it becomes a 1 digit number, which won't change. So just keep track of the indexes that are 1 digit numbers and don't bother visiting those.
There's no need for lazy propagation. Range updates and single queries can be done with a normal segtree storing differences of consecutive elements. 19192561
Inspiring
nice, good trick
You can either solve it using Fenwick tree like I did, or there's an alternative approach as well which doesn't use trees at all.
The sum of digits operation will only be applied at most 3 times on $$$a[i]$$$. So, make an 3 arrays, the $$$1st$$$ one will be storing the numbers obtained by using the sum operation on all $$$a[i]$$$ once, the $$$2nd$$$ one is when the sum operation is used twice, and similarly for $$$3rd$$$.
Now, all you need to do is to check for all $$$i$$$ in $$$[l,r]$$$ how many times it occurs.
hmmmmmmmmmm,nice approach
Then it becomes a scanline problem? Or maybe coordinates compression with pref-sum? Or there are easier solutions?
Why 3 times?
After 2 operations only a number becomes single digit number right?
Take $$$999,999,988$$$ it will become $$$1$$$ digit number after $$$3$$$ operations
I solved it with dsu
I observed that a number will not be updated many times so that I let a number to be updated no more than ten times.
When the number of updates for a particular index reached >10 I will make the parent[i]= findparents(i+1)
Using the above approach whenever an index would be encountered for greater 10 times it will be skipped to the next index and then with the help of dsu I will reach the required index
My submission — https://mirror.codeforces.com/contest/1791/submission/191990981
time complexity will O(n*10+q)
Idk how u guys think of this solution during contest,but hats off to u guys..... I will upslove it tomorrow. Ok bye, Netflix............
I used DSU as well but solved it slightly differently. If any number is < 10 it will never need an update again and we can add it to the same set as the element at i-1.
No
I mean the number of operations applied on a number cannot be greater than 3 (which I randomly took 10)
Awesome contest.
Solved E and G1 in last 19 minutes of the contest!
Good problems this time, I had fun with F, first time using Fenwick tree by myself.
❤️ First time I solved A,B,C,D ✅ (in 32 min)
Can someone explain how the 9th testcase is possible in problem G2, or just how to do the problem in general
Screencast with solutions for all problems in case someone is interested.
A & B: implementaion.
C: 2 pointers.
D: Count the occurence of each different chars for every prefixes and suffixes. The answer is max(count(prefix(i))+count(suffix(i+1))).
E: Dynamic programming. Let dp[i][flag]=the maximum value we can get from first i elements, where flag is true if we've fliped the sign of a[i-1],a[i]. Similar with 1787C - Remove the Bracket.
F: A number can be updated of most 3 times (then it will have only 1 digit, which means, it will not be changed anymore) so we don't need to update a same element for more than 3 times. We can use segment tree to store the number of updates (although there can be simpler solutions, it's easier for me to copy a prepared segtree template).
G1: The cost of each portal is a[i]+i, sort them and we can get the answer.
G2: The cost of each portal is a[i]+min(i,n+1-i), but we need to add an extra cost if all the portals we've used are on the "right part" of the number line (which means they are closer to n+1 than 0). Therefore, we need to consider for 2 situations: First, consider we use at least one "left portal". We can use the left portal with minimum cost and sort the remain portals. Second, consider we only use "right portals". We also solve this situation by sorting, but we need to add min(2*i-n-1) to our total cost. First we use portals by the order of their cost, and when we can't use the next portal, we check all remained portals and try to use them.
By the way: MikeMirzayanov look at this please!
E was one liner after some simple observation.
Elegant solution for problem E:
- If number of negative numbers is even then maximum possible sum will be sum of absolute value of all array elements. - If number of negative numbers is odd then maximum possible sum will be sum of absolute value of all array elements except absolute minimum one minus absolute minium one.
can someone hack on problem F submission? I think it should TLE.
Done
Is mine hackable for F? submission
I think no if your segtree is ok
Solved F without segtree, is my submission hackable :) ?
Done
That means it must be solved with segtree? there is no other way?
You can solve it without segtree. You can see solution in editorial or you can see tops' solutions. For example Jiangly solved it with DSU
can you tell what is going wrong in my code in the same problem.(I am failing test case 3rd i have used fenwick tree tough).
UB if
mp[v[idx - 1]].size()is zero andoperationsis positive:I updated but still it is giving me same error.
v[idx - 1]still failed.
can I ask one question How are you so fast at debugging?(I also wanan be that fast that will help me a lot).
No, I'm toooooooo slow. I should notice this bug after second-third code reread, but I was reading it during 11 minutes...
Now I was just reading your code and comparing it with some others: your BIT seams OK, then bug must be in other parts of code
I've checked update: OK
I've checked query: found UB
What's left? Only filling of
mp, you just fill without check that this element is already in mapJust small advice: use local variables like:
Fun problemset. Managed to solve everything in 1:08, which I am quite proud of. E was very elegant, F and G2 were also nice.
F was some standard stuff after you know it will take atmost 3 op to reduce the no to the final form.
Yeah, it is. But I still think it was nice.
i was expecting atleast one graph question xD
me too lol.
Great contest. Thanks guys :-)
Very cool that F can be solved with set and DSU. I got stuck on BIT implementation because I don't have a template for it and have only solved a few CSES problems using it. Forgot about the limitation of 3 change operations. Thought G2 would be DP, but the binary search solution is quite elegant. 10/10 problemset overall.
My live screencast with explanations for all problems. I have tried to re-explain last problem in the end after I solved it. The problems were very interesting. I felt the last problem was a bit on the harder side for a Div 4 round.
What's wrong with this solution of E 192043725? Thanks.
The return value of your
solfunctuon isintinstead oflong long.Sir it was int overflow
F was straight-forward lazy propgation question once you figured out it will take atmost 3 operations. I just copy pasted some template.
I could not find the template for range update and point query. I could only manage to find for point update and range query smh.
can anyone hack my G2?I feel it not correct,even i pass the pretest https://mirror.codeforces.com/contest/1791/submission/192031288
ok, I hack it myself. this is my first hack >W<
Try to hack my solution with yours hack test
Uhhh~~~ I succeed
What is wrong with my solution for F? https://mirror.codeforces.com/contest/1791/submission/192046957
You are only calculating up to two operations for every number, while there are numbers like $$$999\ 999\ 988$$$ which become 1-digit numbers only on the third operation.
Can anyone tell me why my dsu based code is giving runtime error ! It's well under the time complexity and limit. https://mirror.codeforces.com/contest/1791/submission/191951510
What's Segment tree doing in a div 4 round ?
Look at the editorial. The intended solution doesn't use segment trees.
Segment Tree is one of the ways of doing it.
Is there any penalty for unsuccessful hacking attempt/reward for Successful hacking attempt?
no
Thank you
Very nice problems. Thanks for the contest. I managed to solve A,B,C,D,E,G1 within 50 minutes but could have had F as well if I knew segment tree.
Why G2 got a lot of hacks in first hour?
I can't understand how it works in Problem E. After all, we need to take exactly the neighboring elements and change the signs in them. If there are 7 numbers, for example -1 -2 -3 4 -1 -2 -3 the sum of 16 is not possible.
-3and-1as a boundary, then the array will become-1 -2 3 4 1 -2 -3-2and-2as a boundary, then the array will become-1 2 3 4 1 2 -3-1and-3as a boundary, then the array will become1 2 3 4 1 2 3You can make all the element in $$$[l,r]$$$ positive if $$$a_l \lt 0$$$ and $$$a_r \lt 0$$$ and $$$a_{l+1} \cdots a_{r-1}$$$ are positive, so it is not correct to take neighboring elements.
Select 2 neighboring elements and change their signs. That's what the condition says. I don't understand it.
Think it this way: '-' sign can just travel anywhere along array, bcoz if we do operation on 1 positive and 1 negative number signs of them will interchange, in this way we can make '-' sign travel along array.
Why my solution for problem D is wrong 191979249? and that is the code:(for single test case):
UPD: I solve it using this method and it is accepted
first loop should be upto n-1
This code is accepted
deleted
You can check my answer
Well, it was surprising to me to know how the code for G2 went TLE during the comp (Though I know it was tightly bounded, it passed the given TCs after the comp, THE SAME CODE)...
Can somebody hack it or let me know if it is still tightly bound on those TL?
Here's the code — #192051148 Python o_O
Your code hacked by me :)
Yes. Thanks. Thought it'll go TLE. :))
Can someone explain F?
I'll assume you read the editorial for F but could not understand that solution, so I'll go ahead and try to explain another approach.
For each position i, we need to know how many times that position was modified by the operation. For queries of type 1, we get an interval [l, r] and we need to apply the operation on every position i from l to r. But how do we do that?
We could have an array initially filled with zeros to maintain a counter of how many operations were done for each position. Say, for n=5, this array would start as [0, 0, 0, 0, 0], and if we got a query of type 1 in the interval [3, 5], our array would update to [0, 0, 1, 1, 1], as we did one operation on positions 3, 4, and 5.
Now, a simple way to maintain this operation counter array would be to iterate over each position from l to r, whenever we receive a query of type 1, and add 1 to each position. But straightforwardly doing that would TLE, as it would take O(n) (linear time) to process each query of type 1.
But what if we could do this update operation on our array of counters in O(logn)? That is where the data structure BIT (Binary Indexed Tree, or Fenwick Tree) comes in handy. We can do range updates (say, add 1 to each position from l to r) in O(logn). If this is your first time hearing about this data structure, I suggest you read a bit more about it. It can be a bit daunting to understand at first, but the code is really easy.
Well, now that we can process queries of type 1 in O(logn) time, now we're left with queries of type 2. To process those, we only need to read the value present in our array of counter, for the requested position. After reading this value, we can apply the operation in a straightforward manner, as it is really fast.
Here is my submission to make more sense of what I tried to explain. Please let me know if you have any more questions and I'll try my best to answer them.
The naive approach would be to iterate from $$$l$$$ to $$$r$$$ and apply the changes as mentioned in the statement. However, the time complexity is $$$O(nq)$$$ for this approach which will TLE.
Consider what happens when we apply the operation $$$a[i] := d(a[i])$$$ to an index $$$i$$$ (here $$$d(x)$$$ denotes the sum of digits of $$$x$$$). Clearly, $$$d(a[i])$$$ is $$$O(\log a[i])$$$, since there are $$$O(\log a[i])$$$ digits in $$$a[i]$$$, and each of them is upper bounded by $$$9$$$. So roughly the operation corresponds to doing $$$x \mapsto c \log x$$$.
Intuitively, the idea is that this reduction is huge, and the number of times you will need to apply this operation till you get a single digit number is quite small. At least you can show that every time we apply this operation on a number having at least 2 digits, the number of digits never increases after applying this operation, and in fact it decreases by at least 1 after at most 2 operations. So you need at most $$$18$$$ operations (which is a very loose bound, and the editorial shows that you can replace it by $$$3$$$) under these constraints to get to a single digit number, which satisfies $$$x = d(x)$$$. So after a small number of operations on $$$a[i]$$$, you end up with a single digit number, after which applying the operation on it doesn't change the number.
So let's do this mentally: maintain a (sorted) list of indices which have $$$a[i] \gt 9$$$. These are the indices on which doing the operation can potentially change the number. When you're applying the update on a range, you find the indices in this list that will need a change (the remaining ones are fine as they are). Let's not think about how we will find the indices at this point. For each index, we will process it at most $$$18$$$ times before it gets out of the list. So overall, the total number of indices considered is $$$18n$$$.
Now using a
std::setandlower_bound, you can find and update the (sorted) list in $$$O(\log n)$$$ time per operation.So, if we have list [1, 2, 3, 4, 5], and l, r = 2, 3, we start at a[1] = 2, then we check every other element <= r and if it's < 10, we erase it? So, if a[1] and a[2] will become < 10 after that, our list will be [1, 4, 5]
Yes
Ok, thanks
used the same concept but i got runtime error on test 3 whats the issue ?
code — https://mirror.codeforces.com/contest/1791/submission/192231836
You did
low = *it;after removing the iterator from the set. From here, iterators that are erased are not valid anymore. You should set the value oflowbefore you eraseit.Make an array (vector a, initialized to 0) for checking whether elements are less than or greater than equal to 10 (10 is because you cannot change values below 10). Take one number c(initialized to 1).
If values in input array v from [l,r] are less than 10 then you have [l,r] that you don't need to update in the future. So, keep this information in array a.
Update array a in range [l,r] as c. Then do,
While (l>=0 && a[l]!=0) keep decreasing l and updating a[l] = c(This helps to merge some other range where values are less than 10). Do the same thing to the rightWhile r<n && a[r]!=0 update a[r] = c and increase r. Increase c.Now if you find (a[l]==a[r] and a[l]!=0) no need to update this range.
191968339
It gives TLE. Ignore it
my first fst round... it teach me a lot.
Отличный раунд получился! У меня новый рекорд! 5 задач за раунд решил!
Anyone tell me why this got hacked for G1? Submission https://mirror.codeforces.com/contest/1791/submission/191967985
Rishabh_coder you used the condition : if(c < arr[i]){ break; } , it should be : if(c <= arr[i]){ break; }
Did they change tests for C. I had done a typo in my code, a <= was == but it went through during the contest and it was accepted, it was accepted after the competition as well, but just today it turned into being not accepted. From a positive rating change to a negative rating change, nice.
I didn't get the rating. Does anyone get ? **** NOTE: This is my first contest
not yet
I like how G2 has like 58 tests but still wrong greedy solution gets AC
i have some issues with the problem F I used https://cp-algorithms.com/data_structures/fenwick.html#finding-sum-in-one-dimensional-array they skipped my submisions
what can i do i get skipped my problems
Your code might have significantly matched with someone else's code then. You can check your talks or post about it on a specific blog about same.
Which blog?
My solution is skipped and i didn't Cheat we just at same university and think in same way
~ think in same way
hnmm that makes sense
I recently got a message from Codeforces team that my solution 191923515 matches with 192031691. But I used the segment tree code template from 188598221 which was used long ago in some contest and I usually use the same template as this one. MikeMirzayanov please check it once, I haven't copied the code from some other user, I just used a previously used template of code which I usually use for implementation of segment tree. We all study at the same university so we use the same template of code we shared once. I hope the plagiarism is removed and my solution is judged.
Произошло недопонимание. Я не копировал чужие коды. В самом деле, я просто отправил решение не с того аккаунта. Аккаунт _anuar_ является моим запасным аккаунтом для других соревнований. Я случайно отправил своё решение с того аккаунта, позже я заметил, что пишу не на том аккаунте. Этому доказательство то, что у _anuar_ посылка лишь на одну задачу — А. После этого, из нежелания писать код заново, я просто скопировал старый и отправил его.
По возможности, попрошу пересмотреть свое решение.
Соглашение участие: не используете несколько аккаунтов, а в соревновании принимаете участие со своего личного и единственного аккаунта.
Hopefully, this was my last rated Div. 4 round.
Хороший раунд с интересными задачами
I got a mail from the codeforces that my solution 191964891 for the problem 1791G1 significantly coincides with solutions heavierfire/191964891, abhinav.maurya202/191979043. It is a pure coincidence case and I have not copied it from anywhere. The variables used in the code are pretty common and there is a very high probability that it can be used by others. And also the logic for the problem was also very standard in my opinion.
So I request you to please have a look and consider my submissions for the contest.
flamestorm, SlavicG, MikeMirzayanov and mesanu
Thanks
Hello Codeforces and MikeMirzayanov
I recently received this message that my code (191979043) significantly coincides with solutions (191964891) of this another person code whom I don't know and have no single information about him,
Attention!
Your solution 191979043 for the problem 1791G1 significantly coincides with solutions heavierfire/191964891, abhinav.maurya202/191979043. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://mirror.codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.
I don't have no "conclusive" evidence. I didn't share my code with anyone, and I didn't even share my idea with anyone before contest finished. I use my local VS Code editor to write code, so my code is unlikely to leak.
This problem is simple, we just need to sort after adding the indices and anyone could have come up with this idea, and the solution is short. Also my way of writing code is also very simple. So coincidence can happened. So check this again please. And please give my rating back
Добрый день!
Получил предупреждение за попытку 191986416. В попытке использован широко доступный код, который был размещен публично до соревнования — https://www.geeksforgeeks.org/lazy-propagation-in-segment-tree/
I don't know why the code of my F question (191945896) and (191987078) in this competition is so similar. I didn't have anyone around me at the game and none of my friends that I knew were playing. That account is not my account, both of these accounts are not rated, there is no interest relationship between me and that person, and I do not need to provide the code to that person in div4 competition