Hello! Codeforces Round 913 (Div. 3) will start at Dec/05/2023 17:45 (Moscow time). You will be offered 6-8 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.
The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks.
You will be given 6-8 problems and 2 hours and 15 minutes to solve them.
Note that the penalty for the wrong submission in this round is 10 minutes.
Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third 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 1900 or higher in the rating.
Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.
Problems have been created and written by pashka, MikeMirzayanov and me.
Part of the problems in this round were in the Cyprus Programming Challenge. If you participated in it, please refrain from participating in this round.
We would like to thank:
- peltorator, FairyWinx for red testing.
- Vladithur, Valters07 for yellow testing.
- stefanbalaz2, FBI, SlavicG, flamestorm, SashaT9, mesanu, trainerherp, Ush1su for purple testing.
- dan_dolmatov, Yousef.Osama for blue testing.
- Sergey140146659, Pa_sha, gas for cyan testing.
Good luck!
UPD: Editorial
hoping to return back the blue handle
As you wish
a ni pro
I hope to be the statements short.. i think this better
Yea I hate long statements usually problem setters try to make the problem in to a story and just extend it by 2 paragraphs which is annoying
Tomorrow is my birthday, and I hope to perform well in the contest. Wishing success for everyone.
Happy birthday, brother. I hope this round is memorable in your life.
Happy birthday!!
Happy birthday!!!
Happy birthday!!!
Happy Birthday!!
Happy Birthday! The first time I became blue was on my Birthday — 23rd Sept. I hope You have an amazing contest today.
Happy Birthday G
Happy birthday
Happy Birthday!!!
Happy Birthday
Happy Birthday!
Happy birthday brother!! Hope you did well!!
happy birthday :) Ramtin510
Happy Birthday!
happy birthday
Happy Birthday
Happy birthday!!!:)
hope problems are interesting .....
First time testing :D Good luck to all!!
It's been a while since the last contest written by pashka, glad to see him.
Inshaallah, In this round I will be Green.
inshallah
inshallah in this round i will be cyan .
Inshaallah
My first unofficial Div.3 contest! Hope it will be fun and good luck to everyone!
I hope statements are short and legible :D
I don't know why I'm not included, but it's my first time testing :D
Fixed, sorry for waiting!
No problem, thanks!
ممكن تفتح الرسائل ؟؟
اتفتحت
ok
As a tester, I enjoyed the problems, and I hope that you will enjoy them too
Nice !!!
As a person, who participated in the Cyprus Programming Challenge, I can say that problems were fascinating. Good luck to everyone!
As a tester, I can say that problems are very interesting
hoping to return back the PUPIL handle
if you wanna be expert and higher , upvote me.
sticking out your gyat for the rizzler, your so skibidi, your so fanum tax. I just wanna be your sigma
Good luck to all!!
I have a query about my account disable issue. Where to query? can anyone help me please.
Good luck everyone and I hope I could reach pupil after many contests I've participated in.
I might end up in top 100 in this contest.
I was wondering, why is that on some rounds (mostly educationals) the number of the problems isn't announced? Surely, authors know the number at least a day before the contest begins, and it's pretty inconvinient for the participants to not know that number (myself and I'm sure many others like to make files for the problems before the contest)
Good question, no idea why we're always given a range lol.
Will the round be delayed if this queue continue ?
Why is the round delayed by 10 mins?
i guess because of too much traffic the site was not loading
Hope to become expert.
Me too, Good luck to us ;)
Dreams come true
Hoping to get nearby ratings
Again! one refresh cost me ten minutes
please don't refresh any more
Mybad
if you open author list of this contest using dark reader, you end up with a color scheme of russian flag
What are you doing during the few minutes of the contest delay,it is so suffering
panicking nothing else
reading your comment :)
what does it mean — to be an any color tester?
Nice
why do i get HTTP Status 403 — Forbidden error after refreshing the page during a contest ? How do i get rid of it ?
cool problem G!
How to solve it ?
Let's construct the graph corresponding to. If we have a vertex of degree exactly $$$1$$$, then we either exactly take the edge coming from it, or exactly do not take this edge. We can do this one by one. Then we can prove that the remaining graph is a union of non-intersecting simple cycles. The solution for each of them is approximately the same. Let the cycle $$$v_1 v_2 ... v_k$$$. We have two cases: whether we take the edge $$$v_1 v_2$$$ or not. Each of the two cases is solved in the same way as the first part (if we take it, for example, then all other operations that are necessary are recovered uniquely).
Damn, what a nice explanation. Thanks!
hardest div3c I've ever seen.
regular greedy approach simply not hold.
I'm losing hope in cp
yeah i stuck at this problem for entire contest :(
any idea for this problem?
what if a majority of the characters is equal to the same character? what if not?
how did you come to this idea?
randomly trying stuff.
If I'm being honest, I found C harder than G...
If I had to improve on such problems, which topics should I practice?
There aren't really any "topics" to practise. Instead, you should just solve a lot of div2B-level problems which often revolve around this sort of idea.
look at his colour ;)
lol
Thx for the hint, that helped me to finally come up with the solution :-) I think if I was somehow able to convince myself that greedy won't work I would change my approach but I don't know how to do that (how to write such proof).
Consider what will be the remaining string, which will always be a string of the same characters. Because if there were more than one you could pair them and eliminate them. So the remaining question will be what will be the length of this string. It will be more than one if one of the characters is more than half of the length of the string.
I tried a solution of keep sorting the count array (Of 26 characters) and if I still can find the smallest and biggest count (Both are distinct and > 0), I will decrement them each by 1 unit
After that I just add all the remaining counts
It got accepted, I felt so dumb because I didn't try it during the contest lol
But that's a really neat idea nonetheless. Kudos!!
no TLE!? I thought test cases were too big and discarded that kind of approaches:(
If you look at the time complexity then at worst it would be O(n * 26 * log(26)) which is not that bad lol
t<=10^4, n<=2*10^5 O(n*t) no?
There is a guarantee on the sum of n over all test cases to be <= 2*10^5
Then what is the point of separate test cases ToT. It will take me so long to keep that in mind.
Ok, I get the point of seperate test cases.
My thought process of G: build graph i-ai. pressing a switch is flipping endpoints of an edge. each op is xor which is associative so order doesn't matter and no switch will be flipped twice so op is delete an edge and flip its endpoints.start with leafs. corresponding edges are fixed. we are left with a bunch of loops. now what ?? even no of 1s should be present in a loop. 2 possible ways of pairing find the min one.
Why does my solution for problem D not work? Any help is appreciated.
If you're sure that your binsearch is correct, then probably you haven't looked through all cases on how 2 slices can be related to each other(I found 6 separate cases)
don't the 6 cases degenerate into:
l = max(l — k, l2) and r = min(r + k, r2)
where [r, l] are the current valid range and [r2, l2] are the one we're checking to see if this k is valid.
Idk, I looked through 6 cases just to be sure. It doesn't take much time tho. But you're kinda right
I assume that means you passed? In which case congrats, mine didn't :^(. Clearly some edge case I'm not thinking of, shouldn't have been lazy. Please share your submission, if so.
You can see it, they're open now
1 10 0 17 7 9 8 14 14 19 5 8 2 14 11 14 2 16 2 2 7 9
Doesn't work on your code
How to do problem e?
Solution for n is the product of no of solutions for each digit of n. (So you only need to solve from 0 to 9)
Why is that? Could you explain please?
Since the sum of number and sum of digits is same. Let's say you change sum of digits on ith place by 1 then change in sum of numbers is 10^i. If you compensate this change in sum of digits at other place j then change would be -10^j. Net sum would be 0 iff i = j
For a general change in sum of digits you can view changes as numbers in base 10.
if sum of three didgits of the same rank >= 10, then the sum of digits of a, b, c > sum of digits of n, since n can contain only 8 digits
what is meant by rank here ?
1, 10, 100, 1000...
There is a bijection between the partitions of each digit of n into a sum of 3 numbers and the solution to the given problem. For Example n=26, the corresponding partitions are [[{0,1,1},{2,0,0}(and their permutations)],[{1,5,0},{2,3,1},{6,0,0},{2,4,0},{1,4,1},{2,2,2}(and their permutations)]]. Combining say {0,1,1} and {1,4,1} corresponds to a=01,b=14,c=11 and the tuple (01,14,11) for the solution.
Basically, the intuition is that we need a+b+c=n to hold in each decimal position as well for the digital sum property to hold. As a consequence, there must be no "carry-overs" while performing the addition a+b+c
Nice Problemset
Is G something like topo sort? My idea was to use topo sort until the remaining switches are in cycles, then see if every cycle has an even number of on switches. If so, then we are good.
Yes
f: https://atcoder.jp/contests/arc132/tasks/arc132_b
how did u find this, like how do u find the same problem in general?
it just happened that I had seen this before
This ARC B is much easier than current one because all numbers are distinct and also it is guaranteed that operation exist.
well, you are right
how does that make any difference?
C ruined the experience
235953756 Can't find the bug for code in C :(
what's idea of this solution
The idea is basically from finding 2-majority element of a array without hashing,
I am basically first storing the count of each charater occurance in hash array.
After that, we lets define a process to reach minimum length which will be :-
(We will take the current majority character x in string and we will remove any pair x adjacent to non-x in string.)
if there is 2-majority element in array(if a element occured >= n/2 times), It will remain 2-majority after any no. of processes.
else if there is not any 2- mojority element in array. After some no. or processes, if string length is odd than a element can reach maximum count of n + 1/2 elements and will remain 2-majority after that. if string length is even than a element can reach maximum count of n + 1/2 elements and will remain 2-majority after that.
So, execute the process we defined on string and you will reach the answer after some analysis.(the solution I mentioned may seem tough to understand but it is simple when you will understand)
I think it's because of vector of char instead of vector of int
The above comment is true — it's because of the vector.
Char is in range of [-128, 127] I believe, and the string can be up to 2e5, so if any character appears more than 127 times, char will overflow.
Thanks a lot! its a blunder
Same, sometimes those adhoc problems with the simple solution really stump me.
Hints for problem E? Thanks.
try to observe a pattern in the given test cases. There is simple formula hidden
Solved F 20 minutes after the contest ended.
At first I thought G is 2-SAT. LOL
me to just for a second.
Me too!!
I couldn't solve $$$C$$$ , have I really gotten that dumb!!!
Relax, I've solved the EFGA problems :)
Thanks man ! tbh I also felt like totally giving up. But both of your comments made my day !! :)
yeah when I first saw this problem I thought it was another easy problems.
RIP my rating
don't worry, I took at least 15min to mind-solve it and even then it was just trying random approaches until I found one that worked (then I proved it, of course). And I'm a master...
Hey, Can you just prove your solution for C
First assume that n is even. Then I claim that the answer is 0 if no character occurs more than n/2 times, and maxcnt-(n-maxcnt) = 2 * maxcnt — n otherwise where maxcnt is maximum number of occurrences of any character.
In the second case, we can see that the last remaining character is necessarily the one that occurs the most times, since it's impossible to remove all of them. (you can remove at most one per operation, and at most n/2 operations are performed so there's no way to remove all of them. The number of operations performed is bounded by the number of characters not equal to this most common character, which is n-maxcnt implying that at most 2*n-2*maxcnt characters can be removed. So the length is at least n-(2*n-2*maxcnt)=2*maxcnt — n. I claim that this can be achieved. Method: always try to remove exactly one non-most-common character per operation. This can always be done by choosing an occurrence of the most common character and one non-most-common character — it will always exist until all characters are made equal, at which point the length is 2*maxcnt-n.
We can show the first case by induction.
When n is odd, the reasoning is similar, but since the parity of the length is constant, replace "0" by "1" in the above.
For the case when n is odd, it is not true that removing a most frequent character with any other character will result in a string with no characters occuring more than (n-2)/2 times. Example: s="aaabccc". In fact, the end case 1 is in itself a counterexample. Fortunately, this only happens when the string has only 3 unique characters with first and second most frequent characters having the same frequency and third character having frequency of 1. This means that the final remaining string will also be of length 1. Moreover, the end case 1 suggests that this special case always occurs during removal of pairs under this algorithm.
You can always remove a pair which contains the most frequent letter, as long as all the letters are not the same...
Solved my first ever live contest problem. Thanks!
It's my first time to complete 4. Can I turn green?
nope ig , you are having delta +105
I'm confused,what “delt+105”?
Delta is a word used in physics to describe small changes. In CP it is used to describe rating changes. Delta +105 therefore means your rating increased by 105
I see.But how he can predict my delta so accurately? I thought this was calculated randomly based on rankings.
codeforces uses a rating system similiar to the chess elo system. Meaning they have a formula to calculate rating changes deterministically.
can you check my delta?
use This extension
Error is large in this extension
F implementation was tricky
it would have been interesting if e would have been not for triplets but n-plets (basically for n numbers rather than 3 numbers).
I could not think of E yet, still trying lol
did any one else solve problem F using Hashing ?
my solution
can u pls explain ur solution, I am new to using hashing for strings in cp
I suggest you read This blog, it will give you details about hash functions.
Here am using hashing to simulate the process of shifting in O(1) instead of O(n) , I achieve this by changing the current hash value in each iteration from :
currhash = ( a[0]*A^n + a[1]*A^n-1 + a[2]*A^n-2 +..... a[n]*A )%p
To :
currhash = ( a[n]*A^n + a[0]*A^n-1 + a[1]*A^n-2 +..... a[n-1]*A )%p
i.e currhash = (currhash // A — a[n]) + a[n]*pow(A,n,p) )%p
you can easily see how thats done in my code (using modular inverse and modular exponentiation) . The rest is just checking if the currhash matches the sorted (in ascending or descending order) array hash value.
thanks!
Nice idea!
thank you!
Can someone please explain problem D, how BS is working there?
we binary search on the answer. now for checking if a particular value can be a possible answer for the ranges, iterate in the ranges and maintain a start and end pointer to denote the range where you can be on the line during that time. That can be done in O(n). Hence, BS works here, u can look at my solution to understand more:
My Submission
[x,y] means interval from (inclusive) x to (inclusive) y.
We have to jump into these intervals: [0,0] -> [1,5] -> [3,4] -> [5,6] -> [8,10] -> [0,1]
We can check if this works if we fix k=3:
[0,0] -> [-3,3] //we can jump anywhere here
[-3,3] & [1,5] = [1,3] //this is the overlap. We can be anywhere here
[1,3] -> [-2,6] //we can jump anywhere here
[-2,6] & [3,4] = [3,4] //we can be anywhere here
[3,4] -> [0,7] //we can jump anywhere here
[-0,7] & [8,10] = [ERROR] //we have no overlap and nowhere to jump. K=3 does not work!
Code:
Thanks a lot for your explanation, bro! I knew this problem was BS but for a value k = mid, I couldn't figure out how we can win the game with k = mid or not.
Thanks brother, it helped me to find how to use mid,
Updating current to possible range is where i got confused, urs is Very good logic
Either brain's not braining or found the problem D much harder that usual don't know why...
How to solve G?
Construct the graph $$$i \rightarrow A[i]$$$, this type of graph is well known (Functional Graph). An important property is that it consist of several cycles and nodes that following the directed edges reach some cycle. So obviously if there is a 1 on a leaf you have to change it and switch the next node. In the end you will only have cycles left, some nodes will have 0 others 1. If the number of 1's in a cycle is odd, then it's impossible. Otherwise let $$$A_1, A_2, \ldots , A_{2k}$$$ the nodes that have 1, then you have two ways to convert them to 0. Grouping $$$(A_1, A_2), (A_3, A_4), \ldots , (A_{2k-1}, A_{2k})$$$ or $$$(A_2, A_3), (A_4, A_5), \ldots, (A_{2k}, A_1)$$$. Choose the one that minimize the changes.
Another way of doing it is by considering an undirected graph with edges $$$i \leftrightarrow a_{i}$$$. Now solve for each connected component individually. Notice that each connected component is a tree with one extra edge because there are $$$m$$$ nodes and $$$m$$$ edges, where $$$m$$$ is the size of the component. Try both using the extra edge or ignoring it. Now the problem becomes turning off all the lights in the tree, which we can just do using dfs.
Submission
Almost did it during the round, but didn't spot the trees and tried to find shortest paths to connect 1's instead
Could you explain the code a little more in detail please ?
We iterate over all the nodes. If $$$vis_{i}$$$ is true, we already processed the component containing node $$$i$$$. The first dfs call flips all the necessary nodes from the bottom of the tree upwards, and also finds the extra edge. Before the second call, we use the extra edge, flipping the two lights associated with it, then run dfs again to see if using the extra edge requires less flips.
Problem B : tried the greedy approach but im getting time limit exceeded, any thoughts? https://codeforces.net/contest/1907/submission/235958124
Me too at my first try. But then I record lowercase and uppercase by stack,It's truely faster. I check your code,there is O(n^2),it must be tle.
so you make 2 different stacks that record all letters and merge them?
yeah,note that their index should be record at the same time for merge
for(int j = i-1 ; j>= 0 ; --j)
This loop to find the closest previous upper / lowercase character can be
O(n)
in case the input looks like:aBaB...aB
(string contains onlyaB
pairs)i agree, at first i wanted to use an int to get the index of the last Upper/lower char in the array but what if I have 2 Bs then i cant use the same index that i previously deleted.
String length goes up to 1e6 your code has O(n^3) time complexity.
Done the problem, in case anyone's struggling here's the solution, i just kept a count of b's and B's and i went through the string from the other end to the start, as explained below by @bgopc https://codeforces.net/contest/1907/submission/235960691
If anyone's wondering how to solve this problem without going from back, push back uppercase and lowercase letters' indices in separate vectors(or stacks) and whenever you encounter b just pop the last occurrence and mark that letters index(with a boolean array of same size).
https://codeforces.net/contest/1907/submission/235873405
C>D>B>E>A
Can't agree more!! Also idk why the so many people could figure out C so fast or maybe I'm just too dumb for this... :(
anyone finding Div3.D harder than usual ?
C and D were harder than div 2(for me at least)
I found it on easier side than usual, no dynamic programming problem was there also generally there's a question of tree data structure which wasn't.
Question E is the simplest
Explain please how I am confused.
When adding to the digits of these three numbers, it is impossible to generate carry operations. Knowing this, writing code only takes 5 minutes
How did the combinatorics part work?
If a low position generates a carry operations. So the missing digits sum need to be filled in at the high position, but increasing the digit at the high position will increase the sum of these three digits, making it impossible for the sum of the three numbers equal to be N
I think that the solution of problem B has been widely shared by cheaters. Here are some examples :
235939705 235936558 235937575 235905766
Nice contest! Problems very really good. Thanks a lot for the round Vladosiya pashka MikeMirzayanov and all testers.
This is a genuine plea for help, I have no idea how to approach problems like 1907C - Removal of Unattractive Pairs. The first thing my mind tries is a greedy approach, doesn't help, maybe check for DP, still no use. How do you develop the intuition to solve these type of problems, or even more fundamentally, how do we even approach these types of problems, when nothing else matters except a few observations that perhaps never strike you during the contest?
I just saw that if we want to remove the letter with the highest count then pairing it with 2nd highest letter will be beneficial.... that's why I use set to maintain the order of letters on the basis of their count ... I pick the last and second last and delete them and the update them and reinsert it and this will cost log(n) and do this till the size of the set is greater then 1. we will do this for n/2 element so, TC will be nlogn. 235912384 there is math solution also but I come up with this one during contest
Your solution always gives the correct answer, but the reasoning is incorrect: it's not always possible to remove two characters with largest and second largest frequency (remember that you need to remove two adjacent characters):
$$$\mathrm{acbdaeb}$$$
The most frequent characters are $$$\mathrm{a}$$$ and $$$\mathrm{b}$$$, but you can't remove both with one operation. This turns out to not matter: it's enough to remove the most frequent character with any other character unless the frequency of the second largest character is $$$\left\lfloor\mathrm{len}/2\right\rfloor$$$, in which case we definitely can remove the most frequent and second most frequent characters at once.
upd: there are actually some other cases I missed but the main idea is still there.
As adjacency of elements doesn't matter, to remove the element with the maximum count, we need the same amount of other elements, so the answer is the difference between the count of the maximum occurring character and the count of other elements. If the difference is less than or equal to 0, then we give the output as 0 in the case of an even-length string or 1 in the case of an odd-length string; otherwise, the answer is the mentioned difference.
I have noticed that you can transform the string in a compression of it, example: "aaabbc" is converted to 3 2 1,then the new problem is given an array you can rest 1 to an adjacent pair of numbers any number of times and if a number become 0 remove it and refill the space and this new problem look easier for me to solve.
I thought of this too but then consider the test case:
vvcvvv
. You will compress this to2,1,3
. However, the2
and3
cannot reduce each other since they are both instances ofv
. This is where I faced issue with my greedy approach. I do not know how to account for the fact that after some operations, 2 numbers in the array will become adjacent but they carry the same letter so they cannot reduce each other.of course the first observation to do is if a character appear more n/2 then you can delete all the others chars with an instace of it an the remaining ones will be the answer
You just have to count the letters. Like a frequency list of size 26. Cuz the order of the letters doesn't matter. vvcvvv -> 0 0 1 ... 5 ...
You're correct, but can you explain why that is true? On first glance it seems like it would matter as we're removing adjacent characters.
Is it even obvious after many glances? One would be tempted to say so since nearly 5000 people solved the problem but it just doesn't seem like the kind of fact that would jump at you, even if you stared hard enough.
It most definitely isn't obvious to me; even I guessed that it just works during the contest. I believe I would be able to prove it now, but it seems quite annoying.
Me guessing the solution was the combination of "I had seen similar problems before with similar solutions, this feels correct" and "this is D3C, the solution is probably very simple". Even though guessing isn't generally considered a proper way of solving problems, with strong enough intuition it might be more optimal than proving solutions in modern CF contests.
Is this a sign that the current problem style is bad? I'm not sure, but this should probably be discussed more.
I had to prove it to myself before coding it, but the argument goes something like :
Take your highest frequency letter, if there's at least one different letter, it means that the hfl has at least one letter adjacent to it (otherwise your entire string is just that letter and you're done) that is different and thus you can remove 1 from it and have 2 less letters.
So the optimal algorithm would be something like, keep tracks of letters frequency, take the top one, take any adjacent letter and remove these 2. Update frequencies and repeat. If you look a bit further, you see that if frequency <= len(string)/2, then you can remove all letter (or be left with 1 if odd). Otherwise, you can remove 2*(len(string)/2-nbr_of_max_frequency(letters) and be left with len(string) minus that.
think of it this way, you can always pair one highest frequency letter with another letter, unless only one type of letter remains(the highest frequency letter will have to border another letter). So the order doesnt matter
But if we consider the test case presented earlier by vgtcross:
acbdaeb
, we see that the two highest frequency charactersa
andb
turn out to not be adjacent to each other at all. So reducing both their frequencies by 1 is sort of a false move, since a and b can't reduce each other. Sure, you can always reduce the frequency of the highest letter, but it doesn't always end up being reduced with the second-highest frequency letter (which ironically turns out to be the correct greedy solution in the end).no, i meant pair (any) of the highest frequency letters at that moment with any other letter adjacent to it. you can always do this until you're left with nothing, or a string with a unique character(so you're not necessarily reducing it with the one with second highest frequency)
I think focusing on the highest frequency letter is more confusing than not : - you can always pair any letter with another letter except if this letter is the only letter.
Using this fact, the "order doesn't matter" property come in an easier way.
Then then question is, when do we have letters that are left and the highest frequency letter come in.
yeah that's it
This is not true, you need to pick the highest frequency letter, otherwise from aaabc you can end up at aaa, which is a wrong answer.
That is not what my message above is saying.
What it is saying is that you can basically always pick which letter you want and choose to delete it except if its the only letter. It does not say that your choice will be in the optimal answer.
So when you find that the letter that you want is indeed the highest frequency letter, you don't have think about IF at any moment, you will not be able to delete it. With the observation above, you know that you will ALWAYS BE ABLE TO.
That is also not true. Basically you are saying that in
abaca
, I will be able to pairb
andc
, delete them and end up withaaa
, but that is not the case.No, I'm saying that you can pick 'a', 'b', or 'c' and choose to delete it. It will be deleted with an other unknown letter but it is guaranteed that you will always be able to delete the one letter you choose.
А possible logical chain:
1) In final string you can't make any operation, since it's the shortest possible achievable string.
2) => In final string $$$s_1 = s_2, s_2 = s_3, \ldots, s_{k-1} = s_k$$$. I.e all symbols are equal in final string.
3) Quite intuitive thing to do is try to bruteforce that "final symbol".
4) Then you can see than until there is at least two different letters and at least one "final symbol", than there is an adjacent pair of symbols, one of which is "final symbol" and one of which is not. It's like a simple application of that classic obvious lemma: if there is a binary string with at least one "0" and at least one "1", than there is an substring "01" or substring "10".
From now it's more or less obvious what's next to do (I believe)
Steps 1, 2, 3 seems very logical to me. Maybe step 4 can be seen like an "observation", but this "lemma" about "binary string with at least one "0" and at least one "1", than there is an substring "01" or substring "10"" is way too classical, and it is an easily recognizable pattern after you seen this some number of times. So it all comes down to "solve more problems to be able to quickly recognize such patterns", who could have guessed
FWIW, I'd like to point out that the DP approach for C does work, although it's not efficient (time complexity $$$O(n^3))$$$. But solving it using DP in $$$O(n^3)$$$ is still a good learning exercise, as you might find transitions difficult if you are accustomed to thinking about DP problems in a certain manner, owing to the fact that the neighbors are joined together after deletion of inner elements. I suggest people comfortable with DP to try this out.
For example, you might define $$$dp[i][j]$$$ as the minimum number of characters remaining at the end when we are only dealing with $$$str[i...j]$$$. Then, you might try collapsing the first pair, say starting at index $$$x$$$. However, there's no way to proceed now because $$$dp[i][x - 1]$$$ and $$$dp[x + 1][j]$$$ cannot be combined.
Instead of performing the first collapse, focus on what happens to the first element. Apply some choices to it.
Notice that we were able to write the transitions easily just by changing our perspective.
Submission
What is the Testcase to hack B's solution?
I tried string of 1e6 length consists of a,A,b and B but get failed
It was a very interesting competition
I wanted help with problem C please, it is failing in test case 2
maybe, show the code could help make the problem more clear?
Well, I read your submission just now. As I'm not a native English speaker, if I say something confusing, please tell me. I thought you use recursion to delete characters until nothing can be deleted. Firstly, even if you writed the code well and didn't get a WA, this code could be made TLE because it's O(n^2). So it's not a correct solution for this problem. Secondly, your strategy of deleting is wrong. Let's think about such a string: "bbaebbaecccccccc". It's length is 16 and the answer is 0. However, your code will give the answer 6, which is wrong. because once it find a pair of different adjacent characters after same characters, it deletes them. For examples, it delete 3rd and 4th characters which are 'a' and 'e'. But it's possible that we don't delete them right now but later. Actually, to reach the answer zero,we delete the middle two chracters each time. So one correct way to solve the problem is to delete the characters which is the most numerous in the string right now with a character different with and adjacent to it. Obviously, when we can't do this, we can print the answer. You can use priority_queue (heap) to do this in O(nlogn). A better way is not to simulate the deletion process, just count the number of each letters and then print the answer, which is O(n). Here is my code: https://codeforces.net/contest/1907/submission/235898166
Oh my God, thank you so much @TokaiZaopen !! Not only did you take the effort to read my solution and understand it (understanding others’ code is not easy at all) but also you pointed out flaws and guided me !! I can’t be more thankful to you !!
What's more, it's usually not a good idea to use vector(bool) due to some historical reasons. Try to use bitset instead.
Right !! Thanks for your advice !!
.
CP is not just about speed. There are many types of tasks and not all of them are best served by the fastest language. Knowing more than one language can help in choosing the best strategy for a task. What's the point of abandoning Python and other languages if they also solve the problem correctly, albeit slower than others? Sometimes Python and other languages are just more convenient to use because of their built-in features, libraries, and tricks that other languages don't have.
Do you believe light? 你相信光吗?
Was this round rated? Why is it showing unrated?
Similar Question.
It's not time yet. Normally, it would rate.
Any update on this??
Why does my solution give TLE for problem B
https://codeforces.net/contest/1907/submission/235957135
I am not 100% sure but I think it is because of the string operations, I had the same problem and learned that string operations are very slow which is what was causing issues for me.
The statement ans = ans + str[i] takes O(n) time where n is the length of ans so actually your solution works in O(n^2). You have to change it to ans.push_back(str[i[) and it will work fine
ans=str[i]+ans; this operating is costly as every time you add new char at the beginning of the string it takes O(size of string) time. instead of doing this you can insert the char at end of the string and after all the operation just reverse the string 236009502
Who understands the pain of not being able to load in 20 minutes at the beginning of the competition? I've never been stuck for so long before.
pls explain problem E. Thank you
How I solved it, although I'm not sure if I explain it well enough.
Notice that the digits are 'separate' — You can't create/compensate higher weight digit with lower weight digits — Your digsum will always overflow, since a single digit can have a value of 9 at most, and to have the next weight/power digit you need AT LEAST 10 in the sum of the current digits, always making it to overflow...
...Therefore you can assume that the 3 numbers you have are like this: abcdefg, where each letter represents some digit. You can decompose the target sum's digits into the sum of 3 digits POSITION-based. For example, if you have 38, you can decompose 3 and 8 separately, and then use combinatorics to calculate their combined answer — you can distribute the decomposition of 3 over every possible decomposition of 8 and you will always obtain a new answer. This works because the 10^1 doesn't change the digit of 10^0 position. In general, 10^n doesn't change any other digit 10^m, assuming n!=m. I precalculated every possible decomposition of the digit target sum using 3 digits, and then multiplied each digits' possible decompositions on each other.
I hope this makes sense, lol.
Sol:-**PROBLEM A** https://codeforces.net/contest/1907/problem/A
So, I am new to codeforces and I want to know that in the contest I had solved only one question but did not got any rating. So, was the contest unrated or was it rated but I did not got any ratings for some reason. Would like to know the reason :)
The contest is rated ,just wait and your rating will change soon.
why didn't the submission 235883526 solution not work for 1907B - YetnotherrokenKeoard (problem B)? was it because of memory copy?
ans = str[i] + ans
This works in O(|ans|) which overall is O(n^2)
why it is so late to publish ratings nowadays?
After 10 contests, I'm finally green!
good job
wow
Commenting here just to see how my name looks in green color!!!
Good evening, Everyone (including system).MikeMirzayanov I have just recieved a notification regarding my submission number https://codeforces.net/contest/1907/problem/D for my solution coinciding with others. You can clearly see the name of functions been created to be obvious for the answer and also you can see the trademark of my solution to be genuine on the top. You can verify all of this from any of my submissions from the past few months. You can also go through my style of using the variables and functions from any of my previous submissions. It can be a coincidence as the functions and variables I use are very common among competitive coders but I am sure about my solution being genuine and completely self thought. Thank You
Mukul457 Some of my previous submissions-: https://codeforces.net/contest/1688/submission/217835352 (8 Aug 2023) https://codeforces.net/contest/1207/submission/220195657 (24 Aug 2023) https://codeforces.net/contest/1714/submission/226328908 (2 Oct 2023) https://codeforces.net/contest/31/submission/228841576 (19 Oct 2023) https://codeforces.net/contest/1869/submission/222855817 (11 Sep 2023)
[user:MikeMirzayanov][user:Vladosiya][user:pashka] Sir please look into this matter. I didn't expect such a behaviour from you all. It's been so many days, and nothing has been done. The system asked us to post a comment if there is a mistake from your side and it will be taken care of. Please I humbly request you! Thanks Mukul457
NIce contest
.
I also think so
MikeMirzayanov Sir, my solution submission 235899819 was skipped from the contest as I was notified by the system but all the logic and variable was created by using my thoughts and the name of all the variable were also given by me only. Sir, I have practicing on the platform for a long time and never thought of violating any of the rules. Please recheck my submission and remove the skipped verdict. I also do not know any of the other users who were mentioned in the notification.
Why in this contest. I had rank 3xxx and got rating 500, but my friend had rank like 11k and got 620 rating ?
Because your initial scores are different
That was a shit
give some good articles for questions in contest along with tutorial
May someone please see my latest solution of question B and tell me why is it giving TLE on 3rd testcase even though it's complexity is of order O(N). People even have O(NlogN) solution then why its giving TLE in mine.