Привет! В 31.03.2022 17:35 (Московское время) начнётся Codeforces Round 780 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6-8 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.
Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Мы постарались сделать приличные тесты — так же как и вы, мы будем расстроены, если у многих будут падать решения после окончания контеста.
Вам будет предложено 6-8 задач и 2 часа 15 минут на их решение.
Штраф за неверную попытку в этом раунде будет равняться 10 минутам.
Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:
- принять участие не менее чем в пяти рейтинговых раундах (и решить в каждом из них хотя бы одну задачу)
- не иметь в рейтинге точку 1900 или выше.
Спасибо NEAR за поддержку этого раунда, подробности можно прочитать в этом посте.
Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.
Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацией нашей работы. Задачи были придуманы и написаны командой Университета ИТМО: MikeMirzayanov, MisterGu, myav, Gol_D, Aris, senjougaharin и Vladosiya.
Также большое спасибо: arvindr9, hocky, lucasxia01, Evirir, Sorting, 244mhq, yorky, Jostic11, sansen, leaf1415, Masha237, amr_abdelazim, coderbd, gs17005, nebula за тестирование раунда и весьма полезные замечания. Список тестеров будет пополняться.
Всем удачи!
UPD: Разбор
Very nice! Good luck everyone, I wish you high rating. Hopefully I can become blue after this round
Finally, div 3 contest. We waited for this 2 weeks)
First unrated div3 for me, yay noice :)
Suffering from success
Mee too :) yay
Same, except I’ve only participated in 4 rated contests.
Very interesing
As a tester, make sure to participate in this brilliant contest.
Always love a good old div3 round.
(line 1) You will be offered 7-8 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600.
(line 6) You will be given 6-8 problems and 2 hours and 15 minutes to solve them.
Is that a typo or you want to confuse us?)
not a typo, just inference. $$$x \in [7,8]$$$ and $$$x \in [6,8]$$$ implies $$$x \in [7, 8]$$$. so there wud be atleast 7 problems and at most 8.
Your interpretation is illogical, because if the number of problems is not mentioned in the first line, there is a possibility that the contest contains only 6 problems, while with its presence this possibility disappeared, This is what m_bolshakov pointed out.. lol
there will be at most 5000 interactive problems in this contest.
Good luck everyone!
div 3 contests on codeforces are as rare as tourist not getting rank 1.
It's my first contest since I recovered from COVID-19. Hope I can reach 1400 rating!
Hope this one's the rating booster!!
Excited for my first unrated round!
Same goes for me, Now I can try to solve like rainboy.
I am going to miss this contest after a contest streak of 22 months
Nice contest, but D should've been removed or at least switched with E.
what exactly is there to prove?
That you can take the first recurring character into the answer. See 151525744. Also it just came to my knowledge that some people did dp, then yes, there is nothing to prove.
what can be the approach for E
There are only $$$n$$$ possible diagonals, one can explicitly check them all.
Note that any shift, up/down/left/right, preserves the diagonals as they are (if you consider the diagonals as 'wrapping round' when they reach an edge). Find the diagonal with the most 1s on it, say it has X 1s out of a total of Y 1s on the whole grid. Then the answer is (Y — X) + (N — X): the number of 1s off main diagonal is Y — X, and the number of 0s on the main diagonal is N — X.
I observe that after any operation finally what you have to do is choose some row and move downward and check the cost. there are n rows and n operation to check each row.
my solution to f1 is taking 982ms runtime, i think it is hackable, can you please try to hack it Your text to link here...
I don't think that it is hackable unless 982ms comes from re-running your solution several times (CF does that to close-to-tle solutions). From my experiments, the worst case for your solution is simply 3000 minuses. Here is a generator that I used in experiments.
This is also visible in code, as it takes the longest to run if
p<mall the time and conditiony-(a*2)<mnever breaks early. This is exactly the case of 3000 minuses.Some reasoning for why this works fast may be that:
It follows that your solution performs roughly $$$n^3/18$$$ operations, or 1.5 billion, which is not that far off what is usually considered to be acceptable.
how to solve C with greedy?I can only come up with a DP solution
You can take the first recurring character into the answer. See 151525744.
you can solve it without dp like this:
imagine we want to maximize the # of characters preserved, instead of minimizing the # of deletions. Supposed we want to preserve a pair of some character c, which occurs at indices [i1, i2, i3 ... ] (in sorted order). We would never want to preserve the c's at i1 and i3, because (i1, i2) will give us the same result for fewer deletions.
So let's consider the adjacent intervals for each occurrence of every character. (i1, i2) (i2, i3) (i3, i4) ...
Note that if we choose to take some interval (i,j) it means we are preserving the 2 characters at i and j. This also implies, that everything between them is deleted. If that's the case, then the optimal answer which maximizes the # of preserved characters is clearly reduced to: the maximum number of disjoint intervals we can take.
If we stick all of these adjacent intervals, for each unique character, into a big array, we can run a greedy algorithm to compute the max disjoint intervals taken.
Here is code: https://mirror.codeforces.com/contest/1660/submission/152393885
I agree. Problem D took an hour out of me, and I ended up with an RTE on test 2. 151575805
EDIT: Thanks for pointing out the greedy approach for C. Like several others, I used DP. 151539005
I think D is a Directly Calculating..
thank for your ideas
I think F2 and D are both a lot easier to come up with than E
Maybe a severe intuition gap on my part
How to solve F2? I'm too weak :(
You can use divide an conquer in $$$O(Nlog^2N)$$$
Claim: $$$(l, r)$$$ is good if $$$\text{balance}[r] \le \text{balance}[l]$$$ and $$$\text{balance}[l] \equiv \text{balance}[r] \pmod{3}$$$, where $$$\text{balance}[i]$$$ is balance of prefix $$$s[0..i]$$$. We will count $$$(l, r)$$$ grouped by $$$r$$$. This means counting numbers greater than or equal to something with a given remainder modulo $$$3$$$. I used 3
ordered_sets for this purpose, with balance numbers grouped by remainder, but there is also a linear dp that uses discrete continuity.Thank you so much! Now I get it :) I thouht too much and didn't solve it even though I came up with the idea of $$$3$$$ QAQ
Why cant u a purple refer to Fenwick Tree??i dont think f2 a hard one since youve done f1
My solution to F1 was too complex so that I constrainted myself in that way :<
3 BITs solves in $$$O(nlgn)$$$.
I think the key observation is that if minus count > plus count + 1, you can always combine some minuses together to makes plus (since they would definitely be minuses adjacent to each other), which simplifies the question greatly because now you don't really need to keep track of the position of minuses and whether they can merge or not. When that idea struck me after trying for a while, the question became rather classic.
Same.
When I was solving F1, I forgot the limit of adjacent minus signs, but I got an accepted verdict. An interesting thing is that I have even not noticed that the limit is not necessary after that. Then I resubmitted the "corrected" code on F1.
This minor mistake took me more time to get the right idea of F2.
I made it $$$O(NlogN)$$$ with a segment tree(of course Fenwick tree can also solve it)
My approach for F1. Promising String (easy version).
Part 1: A necessary and sufficient condition for a string to be promising.
Part 2: $$$O(n)$$$ algorithm to check the previous condition.
Part 3: $$$O(n^3)$$$ solution to the problem using 2D DP.
Part 4: Optimizing the previous solution to $$$O(n^2)$$$ .
Consider a string of length $$$len$$$ with $$$x$$$ amount of $$$+$$$ and $$$(len - x)$$$ amount of $$$-$$$. How do we determine if it is promising in $$$O(len)$$$?
Performing the operation adds 1 $$$+$$$ to our string and removes 2 $$$-$$$.
Suppose a total of $$$k$$$ new $$$+$$$ was added to the string, after all the operations have been performed.
For it to be promising, we must have
If the numerator is less than 0, or if it is not divisible by 3, the string cannot be made promising. Else, we need to figure out whether we can perform the operation at least $$$k$$$ times on this string.
Consider the substrings of the type $$$+ - - - \dots+$$$.
The minuses form an island and cannot interact with other elements outside this island. From part 1, our goal was to find an opening to perform as many operations as possible. The maximum operations that this island can contribute is $$$\lfloor island\_size/2 \rfloor$$$.
So, we just need to count the number of islands, add their contributions, and check if the contribution is $$$>=k$$$. If it is, the string can be made promising.
Define $$$dp[i][j]$$$ to be true if $$$str[i \dots j]$$$ can be made promising. For each $$$dp[i][j]$$$, apply the linear time algorithm from the previous section to compute the answer in $$$O(N)$$$.
There are $$$O(n^2)$$$ states and $$$O(n)$$$ transitions, resulting in a complexity of $$$O(n^3)$$$.
The constraints imply an $$$O(n^2)$$$ solution. Since there are $$$O(n^2)$$$ substrings, we need to find whether a particular subtring is promising in $$$O(1)$$$.
Define $$$dp[i]$$$ to be the number of promising substrings starting at $$$i$$$. Comparing it from the previous 2D DP, we are just summing up all the entries of every row.
To compute $$$dp[i]$$$, notice that the substring starts at $$$i$$$ but can end at any $$$j \geq i$$$. Let us try all $$$j$$$, in increasing order, using our algorithm from the previous section. Sum up all the values obtained from these indices to $$$dp[i]$$$.
To reduce it to $$$O(N)$$$ for each $$$dp[i]$$$, notice that, while iterating through $$$j$$$, we are only interested in the number of islands seen previously. So, instead of starting a new scan for each $$$j$$$, we can keep one variable to track the number of islands seen so far.
Code
I suppose presenting the process of problem solving is often useful for adequate programmers..? Can not understand so many downvotes though some little mistakes in Part 3.
i think downvotes are just because there's an easier way under f1 constraints. Can just brute force it directly without any dp
alright, got it :)
How to do 'C'? I couldn't come up with any solution in two hours
I used DP. When you encounter a new letter s[i], you can either delete it and have dp[i-1]+1 deletions, or delete all letters between s[i] and its previous position j, and have dp[j-1]+i-j-1 deletions. UPD: you also need to track the previous position for all characters.
thank you & you are so strong
How do we now if the previous position of
iwas already coupled with other previousk:k < j < i?For example: "aaa". Here we couple 1 with 0. After that we can't couple 2 with 1 because 1 is already coupled.
You don't need to know that. When you try to couple the current position
iwith the previous positionj, you then look at the answer for the substring that ends atj-1. So for your example the solution will look like this:Thank you! Now I got it.
For any character at a position i , you can only do 2 things.
a) Remove the ith character b)Pair up ith character with the next index j , such that j>i AND s[j]==s[i].
Now , you can write a recursive function to do the same and memorize it for the constraints.
Greedily selecting pairs of same characters traversing from left to right to not be deleted, and removing the rest was what worked for me. My intuition was that it would never be better to remove the "closest" pairs of same characters, because in doing so we'd be removing 2 characters just to merge 2 other characters. I don't have a proof for this though.
if you're interested, you can solve it without dp like this:
imagine we want to maximize the # of characters preserved, instead of minimizing the # of deletions. Supposed we want to preserve a pair of some character c, which occurs at indices [i1, i2, i3 ... ] (in sorted order). We would never want to preserve the c's at i1 and i3, because (i1, i2) will give us the same result for fewer deletions.
So let's consider the adjacent intervals for each occurrence of every character. (i1, i2) (i2, i3) (i3, i4) ...
Note that if we choose to take some interval (i,j) it means we are preserving the 2 characters at i and j. This also implies, that everything between them is deleted. If that's the case, then the optimal answer which maximizes the # of preserved characters is clearly reduced to: the maximum number of disjoint intervals we can take.
If we stick all of these adjacent intervals, for each unique character, into a big array, we can run a greedy algorithm to compute the max disjoint intervals taken.
Here is code: https://mirror.codeforces.com/contest/1660/submission/152393885
what was the website showing smallest countertest to submission?
You called? :)
Will be adding the problems from this contest in an hour or two. Stay tuned!
any hint to solve C?
Let $$$dp[i]$$$ denote the minimum number of deletions to make string $$$s[0..i]$$$ even. Then you can either delete $$$s[i]$$$ (corresponding to $$$dp[i-1]$$$), or you can match $$$s[i]$$$ with another $$$s[j]$$$ where $$$j<i$$$ and $$$s[j]=s[i]$$$. Now how can find that $$$j$$$ by doing preprocessing?
Work greedily on segments When s[i] == s[i+1] increment i by 2 when i == n-1 increment res by 1 When s[i]!=s[i+1] Now try to search for two chars in a segment that are the same like here mbacb two b are there So we will remove mac here
Simply to search whether there are two same chars we can use set If we found one then res will be inc by window_size — 2 otherwise, res will take that entire window.
This was my approach. I hope it doesn't get hacked 151529755
greedy approach: if s[i]==s[i+1] you move to s[i+2]. else you choose to either remove the whole remaining string, or match two characters. To match two characters iterate through every character c from 'a' to 'z', then find the next occurrence of c and the next next occurrence of c and in order to match the two characters you will remove every character before the first occurrence of c and every character in between the first occurrence and second occurrence of c.
if you're interested, you can solve it without dp like this:
imagine we want to maximize the # of characters preserved, instead of minimizing the # of deletions. Supposed we want to preserve a pair of some character c, which occurs at indices [i1, i2, i3 ... ] (in sorted order). We would never want to preserve the c's at i1 and i3, because (i1, i2) will give us the same result for fewer deletions.
So let's consider the adjacent intervals for each occurrence of every character. (i1, i2) (i2, i3) (i3, i4) ...
Note that if we choose to take some interval (i,j) it means we are preserving the 2 characters at i and j. This also implies, that everything between them is deleted. If that's the case, then the optimal answer which maximizes the # of preserved characters is clearly reduced to: the maximum number of disjoint intervals we can take.
If we stick all of these adjacent intervals, for each unique character, into a big array, we can run a greedy algorithm to compute the max disjoint intervals taken.
Here is code: https://mirror.codeforces.com/contest/1660/submission/152393885
Were the problems too easy?
First time AK'ed any div3. contest.(Hoping I won't FST)
Thanks for the problemset.
Actually I only solved A and B
Far from it, I'd say. C and D were quite difficult by Div 3C and Div 3D standards. I solved C with dynamic programming and D with a relatively fiddly implementation. There may have been easier ways to do it, but I found them far from trivial. Then E and F1 were much easier. That was strange! A fun contest.
I don't get why most of the people solved C using DP, such solution looks so elegant, hope it does not fail https://mirror.codeforces.com/contest/1660/submission/151587350
The simple answer will be that it was the first (and safest) idea that came to people's minds. DP is often a safer approach than greedy.
You are right — that solution is elegant.
It feels so, because its the first time I also AK'ed a Div3 without a single wrong attempt!
Maybe E should've more harder.
Also my first AK.I think the difficulty of the questions is more average.ABC is not that easy and EF is not that difficult.
Why is the time limit for question d, can someone help me take a look, I think it is O(n)Your text to link here...
i'm sorry that your solution works in $$$O(n^2)$$$ because of the first line in f()
when a[] are all zero, l will run to n+1 and r will run to 0.
That costs O(n) each time, and it will process n times.
can you give me test case for problem D . https://mirror.codeforces.com/contest/1660/submission/151583999 I can't find why it gets wrong answer.
Failing testcase: Ticket 3077
В E-шке очень неприятное условие "4 операции сдвига бесплатно", я думал бесплатно можно только 4 раза сдвинуть бесплатно, а потом платно xd
What was test case 14 in D
Can someone provide me a corner case for this solution?
My approach was to calculate the maximum product subarray ending index then, remove n-that_index-1 elements from the array after that pop element and check their product when product == max product print size of the remaining array.
151575450
bro u cant just multiply the numbers as if we have 100 numbers 2 in our array so ur code will calculate 2 power 100 which is a very huge value and cant be stored so u should have calculate the frequency of 2 or -2 in spite of product because only frequency of abs(2) matters in the products
$$$2^{200000} = $$$ overflow.
I want to bang my head against wall :)
i also did the same mistake and got 3 wa in the starting
You can probably still do it this way using this property: log(a*b) = log(a) + log(b) to avoid overflow errors.
My solution to problem D:
It's easy to find that the final product must be positive,so we can divide the sequence by every $$$0$$$.
For each subsequence:
If the product is negative,find the far left negative number and the far right negative number,compare their results and shorten the subsequence. It is easy to see the product must be postive after this operation. When we compared the subsequences,we only need to pay attention to the $$$2$$$ and $$$-2$$$,so we can use prefix sum to solve it.
Finally we check all the subsequnces and find the best answer.
The solution is $$$O(n)$$$.
Pardon me for my bad English :(. You can try to connect the code to understand it.
tfw solved it but used a prefix product array and thus overflowed. Feelsbad
I tried that, but couldnt figure out the reason for tle
Definitely, one of the best contest i have given so far. Expecting to become specialist once again!!
Great questions by the setter and good strong test cases. Thank you!!
Love Aris
Is it possible to hack the slow solutions of problem F1?
I think problem C is the hardest problem. I use 22min on it.
I think this div 3 round should be declared div 2.
I think it is of medium difficulty in div3s.
Just the way the first 2 questions of div 2 are doable at least the first three questions of div 3 should be doable. But, the number of submissions is telling a different story.
C is hard for this position,this I agree.
If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table to increase/decrease the constraints.
I've also added a new feature to view progress of your judgement in near real-time. (For example, the current state of your ticket, how many inputs were evaluated, etc).
If you are not able to find a counter example even after changing the parameters, reply to this thread, mentioning the contest_id, problem_index and submission_id.
Learning From Mistake (Mistake 4)
Initially, After getting the usual wa on test 2, I tried another approach 151583179, which gave a runtime error on test 15. I went around stress testing as to why is giving Runtime error, and spent way too much time on it.
After the contest, I tried to print the error 151598207 and it was this
In python, int does not have an upper bound on size (It depends on the system), but float does. Float has an upper bound, which can be checked using
sys.float_info.max. I did not know it. It cost me an AC. After replacing the/with//, It 151598360 gave an AC. How foolish of me!Bruh... Managed to only solve B and A, failed at C. Now tried E and solved it within a couple of minutes. I think I am just a total disgrace at DP. Could anyone recommend me a way to master on problems of this tag?
if you're interested, you can solve it without dp like this:
imagine we want to maximize the # of characters preserved, instead of minimizing the # of deletions. Supposed we want to preserve a pair of some character c, which occurs at indices [i1, i2, i3 ... ] (in sorted order). We would never want to preserve the c's at i1 and i3, because (i1, i2) will give us the same result for fewer deletions.
So let's consider the adjacent intervals for each occurrence of every character. (i1, i2) (i2, i3) (i3, i4) ...
Note that if we choose to take some interval (i,j) it means we are preserving the 2 characters at i and j. This also implies, that everything between them is deleted. If that's the case, then the optimal answer which maximizes the # of preserved characters is clearly reduced to: the maximum number of disjoint intervals we can take.
If we stick all of these adjacent intervals, for each unique character, into a big array, we can run a greedy algorithm to compute the max disjoint intervals taken.
Here is code: https://mirror.codeforces.com/contest/1660/submission/152393885
Thanks a lot! Will have a deep look
when i try to hack a solution i received an Unexpected verdict, what it means?
First contest, big thanks to the writers and testers! For problems that I struggled with, what is the best way to get guidance? Thanks!
You can wait for the editorial thread or just ask here.
Or go here.
When do editorial threads post?
Within 24 hours typically.
Sometimes the threads are posted immediately after the contest but for Div3/Educational I think they wait at least after the hacking phase (12 Hours).
Also the ratings are updated at more or less the same time.
Great, appreciate you
I am getting TLE on problem D please help!! submission : link
My speedrun and video solutions to all problems is available here on my youtube channel for anyone interested.
Commemorating my first time to solve all tasks in a contest.
Please if someone can help me with Problem D, my code computes the first and last index of the subarray. I can't find anything wrong with it (Overflow shouldn't be a problem because Python supports arbitrarily large integers). Submission: 151614920
Nevermind: ...empty product has value 1. But still got TLE despite O(N). Guess large products are costly.
Python's large integer operation is slow when the integers are extremely large.Don't use that.You can express it as $$$\pm 2^x$$$ instead.(sorry for my poor English
Maybe the value of cur overflows.
Can anyone explain me the intuition of MAP solution in C prblm ?
I believe it comes from thinking of those elements left in the map as being unavailable for the upcoming letters in the string or that they shouldn't be matched with any of the upcoming letters as this will break the order of the string.
I am getting TLE on problem D please help!! submission : link
F1andCshould be interchangedIs it unrated really, can anyone please reply ?
I would also like to know
Hello. I have a rating under 1600, and I believe I am a trusted account. But last night, when I participated in this contest, my ratings didn't change. Can anyone help me understand what happened?
I satisfy the conditions too but my rating didn't change too idk what happened
What should we do? How do we attract the attention of CF authorities?
It seems that no participant got a change in their rating, idk if it is true If any samples which conflicts my opinion just reply me
Just wait. The ratings will be updated within few hours since there was a hacking phase after the contest that's why it's taking time.
Where is the solution?
You can read other people's code(in status) and try to understand the correct solution until the official solutions.
Can someone help me why am I getting wa on testcase 2? Here is my submission : 152264434
Approach : get all segment without zeros , and try to find the best answer from those segments .
any counter example would be so much helpful
Failing testcase: Ticket 3199
Pls help https://mirror.codeforces.com/contest/1660/submission/152302981 Thankyou
Failing testcase: Ticket 3289
P.S: You don't need to ping me. You can learn how to use the website using this blog and comment
Thanks a lot!
Someone has spammed the problem tags for F2 — if anyone has tag edit access and can undo it that would be good.
UPD: resolved, thanks
Why this submission TLE? I think it is right and I have submitted after the contest, however, it was Accepted. Could anyone give me a hand?
I have a problem with the problem D. In contest time I got "Accepted". But now I got "wrong Answer" in the same test case (Test case 2). So, why I didn't get "WA" in contest time. I still had 10-15 minutes. Please help me with this situation.
Maybe it's because in the hacking phase somebody else's solution was hacked and then that hacking test was added to the rest of the other D tests, and your solution fails the test
NO. It's not like that. The test case existed before. The test case was -
1 0
For this I printed "0 0", it got accepted in contest time. But now I am getting WA.
Maybe the original checker was wrong and got fixed.
From the problem statement:
0 0would mean to keep the only element, so the product for this array would be01 0or0 1would mean to delete the only element -> result is10 0->01 0->00 1->1(empty array is also correct:2 0,1 1,0 2)I know. But my point was if I got a correct verdict in contest time maybe I could solve the problem. But I didn't. I got the correct verdict in system testing. Why ? I am the one who suffered.
The world is not perfect. Sometimes mistakes happen.
Do not take it too seriously. Maybe you could have gained a bit more rating, but others would have been better too, so maybe not. Anyway, do a few more contests in the future and your "suffering" will be forgotten.
The test case was 2. It was already in the pretest. From my previous submission I can see that my answer for that case wasn't considered wrong.
exactly same happened with me, my code gave 0 0 on test case 1 0, which is indeed wrong ans due to a typo but during the contest it showed accepted, so i didn't checked it again, but now its wrong ans on test case 2, i had 10 -15 min remaining when i submitted D, i could have corrected my solution
Why haven't the rating changes been applied yet?
Me too.
I've waited for a long time! Is it a trick on April Fool's Day?
It's usual for div3 and educational rounds
when will I get my score
can anyone tell me the solution of C problem without dp
Work greedily on segments When s[i] == s[i+1] increment i by 2 when i == n-1 increment res by 1 When s[i]!=s[i+1] Now try to search for two chars in a segment that are the same like here mbacb two b are there So we will remove mac here
Simply to search whether there are two same chars we can use set If we found one then res will be inc by window_size — 2 otherwise, res will take that entire window.151529755
Greedy.
Make same letters into pairs $$$(l,r)$$$
For each time,choose the pair that the $$$r$$$ is minimal.
Pardon for my bad English,you can see the code to understand it better :p
https://mirror.codeforces.com/contest/1660/submission/151537948
can you please explain in more detail..i will be grateful
We turn the problem into choosing most identical letter pairs that the letter pairs don't be staggered (Formally,if the pair $$$(l1,r1)$$$ and $$$(12,r2)$$$ are in the answer set and satisfy $$$l1 < r1$$$,then $$$r1 < l2$$$ must be hold. ) You can simulate some examples to understand this.
Then we consider to work it out greedily.
It is easy to see,for each time,choose the pair that $$$r_x$$$ is the minimal must be the best choice.So we can sort the pairs by $$$r$$$,and traverse them to calculate the answer. It can be proved that the answer is correct.
I tried my best but my English is really poor QaQ
To not keep you waiting, the ratings are updated preliminarily. In a few days, I will remove cheaters and update the ratings again!
wtf no editorial till now!!
Today I received the following message: Your solution 151546638 for the problem 1660C significantly coincides with solutions xabialonso14/151529962, Mukundan314/151534091, harshgoyal185/151546638, skhan_org/151548513, rajeshpenugonda6/151566978, raushnn/151568699, Aksnov/151569233, RishabhVarshney/151570560.
But these solutions are different (eg. submission by Aksnov 151569233 and my submission 151546638). The reason for coinciding is the use of the Python FastIO template used by all the users stated above. But the use of the FastIO template is permitted as the template is publicly available and was published before the contest (template link). The main logic of the solution is different.
So, MikeMirzayanov please look into this and do the needful!
I received the following message. Your solution 151524331 for the problem 1660C significantly coincides with solutions ttttan/151524331, mayocorn/151541772.
The reason for coinciding is the use of AtCoder Library (ACL blog link). ACL is the official source code. I always use much of the ACL source code, and mayocorn also do the same thing. Please look at these codes(151524331,151541772). I used dynamic programming (dp) for the problem, but mayocorn solved differently. The main logic of these solutions are different.
Hey @MikeMirzayanov I have got a plagiarism for my solution for question C because unknowingly I used ideone.com for writing and compiling my code in the public mode. This led to the leakage of my code and thus my code matches significantly with many other people as mentioned to me in the mail. So, I request you to please rollback my rating changes as this happened to me unknowingly. I would really appreciate if you consider this for once and I can assure that this won't happen again.
Looking for your reply.
My solution 151559424 for the problem 1660C “langminjie/151559424”,I submitted it earlier than "Ac1dX/151581662".I do not know Why it be same,and I wrote this code by myself. Why it skipped me?
Attention!
Your solution 151570560 for the problem 1660C significantly coincides with solutions xabialonso14/151529962, Mukundan314/151534091, harshgoyal185/151546638, skhan_org/151548513, rajeshpenugonda6/151566978, raushnn/151568699, Aksnov/151569233, RishabhVarshney/151570560. 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 have received this message. If you have looked in the code, we all have used the same template from https://github.com/cheran-senthil/PyRival Also I have uploaded the same template on my github https://github.com/rishabhvarshney14/Competetive-Coding/blob/main/template/pypy.py. If you look at our main function, the code along with the logic is quite different.
I hope this can prove that I didn't cheat.
I've received this morning your message about identical solution with some other competitors of problem 1660C(my solution is 151529962), but I think it was just common use of greedy algothrim. It's not a cheat but a coincidence. Looking forward to your response.
About Round#730 Div-3 I got a message that my code is similar to Firewarden07. But iftakheralam01 and Firewarden07 both are my accounts. please check I also comment from that account.
This is my second account
Multiples submissions on different accounts during the same contest ... Trying to dodge some submission penalties...? (yep, I'm accusing you of cheating, and if you're not, why using two accounts for the same contest?)
In 780 div3,My solution 151559424 for the problem 1660C “langminjie/151559424”,I submitted it earlier than "Ac1dX/151581662".I wrote this code by myself.that means I do not copy anyone code, why my rating has dropped, it's not fair for me.I have sent a Message to the MikeMirzayanov and also sent a statement but no one told me how to fix this, can anyone tell me what to do?
can someone help me to solve F2 using ordered sets or segment trees I am not aware of Fenwick trees
How to solve F2 using fenwick tree?
Even though I did not use online IDE for the contest and neither did I discuss or send my solution to someone else I got a message from codeforces that someone has copied my solution for Problem C and I received a warning.How is this possible??
arvindr9, hocky,Evirir,Sorting,244mhq There was an issue of false plagiarism detection due to template.
"My solution 151568699 for the problem 1660C significantly coincides with solutions xabialonso14/151529962, Mukundan314/151534091, harshgoyal185/151546638, skhan_org/151548513, rajeshpenugonda6/151566978, raushnn/151568699, Aksnov/151569233, RishabhVarshney/151570560."
Can you please review and rectify it as soon as possible. It has been more than 10 days.
Thank You.
Testers are just random users being asked to try solving the round and have nothing else to do with the contest so we can't do anything. Tbh I don't know who you should ask to solve this problem though...sorry about that. I did look at the submissions and it does seem to be a mistake from the plagiarism detector.
As old as this contest is, I had difficulty with understanding why the greedy solution to problem C works and I've just now come up with an explanation that is intuitive for me. Hoping that it helps others in the same boat as me.
The reason why we always prefer to preserve the pair in nested sets of pairs that is finished off first (As in, if we were going over the string "abcdab," we would choose to keep the pair of a's and delete "bcd" instead of keeping the pair of b's as the second a is at index 4 while the second b is at index 5, or if we were going over the string "abccab," we would choose to keep the pair of c's and delete the ab's as the second c is at index 3 while for a and b, it's index 4 and 5 respectively.) is because it's always more profitable than the other options: If you bring the halves of the earliest ending pair together, then anything after that pair will be free afterwards, giving you the most freedom-- should you choose a pair that is closed off later, you might lose a potentially profitable link. The potential profit you make off of bringing together the earliest ending pair and any other is the same-- you save up on two characters, so why choose any pair that closes off more opportunities?
This approach reduces this problem into a derivative of what's known as The Activity Selection Problem, you can search for it if you'd like to read about it in more detail.
F1 with bs