Codeforces Round 913 (Div. 3)

11 months ago, # ^ |

Damn, what a nice explanation. Thanks!

→ Reply

tickbird

11 months ago, # |

hardest div3c I've ever seen.

regular greedy approach simply not hold.

I'm losing hope in cp

→ Reply

phukaoz

11 months ago, # ^ |

← Rev. 2 →

yeah i stuck at this problem for entire contest :(

any idea for this problem?

→ Reply

11 months ago, # ^ |

what if a majority of the characters is equal to the same character? what if not?

→ Reply

Loganwick

11 months ago, # ^ |

how did you come to this idea?

→ Reply

11 months ago, # ^ |

randomly trying stuff.

If I'm being honest, I found C harder than G...

→ Reply

Loganwick

11 months ago, # ^ |

If I had to improve on such problems, which topics should I practice?

→ Reply

11 months ago, # ^ |

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.

→ Reply

vivek_coder_9

11 months ago, # ^ |

look at his colour ;)

→ Reply

Loganwick

11 months ago, # ^ |

lol

→ Reply

Antroz

11 months ago, # ^ |

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).

→ Reply

del1990ta

11 months ago, # ^ |

← Rev. 2 →

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.

→ Reply

m_nature

11 months ago, # ^ |

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

→ Reply

SXZZ5

11 months ago, # ^ |

But that's a really neat idea nonetheless. Kudos!!

→ Reply

11 months ago, # ^ |

no TLE!? I thought test cases were too big and discarded that kind of approaches:(

→ Reply

m_nature

11 months ago, # ^ |

← Rev. 2 →

If you look at the time complexity then at worst it would be O(n * 26 * log(26)) which is not that bad lol

→ Reply

11 months ago, # ^ |

t<=10^4, n<=2*10^5 O(n*t) no?

→ Reply

m_nature

11 months ago, # ^ |

There is a guarantee on the sum of n over all test cases to be <= 2*10^5

→ Reply

11 months ago, # ^ |

Then what is the point of separate test cases ToT. It will take me so long to keep that in mind.

→ Reply

11 months ago, # ^ |

Ok, I get the point of seperate test cases.

→ Reply

Si_jo

11 months ago, # |

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.

→ Reply

surajiyer

11 months ago, # |

Why does my solution for problem D not work? Any help is appreciated.

→ Reply

11 months ago, # ^ |

← Rev. 2 →

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)

→ Reply

bunkerman

11 months ago, # ^ |

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.

→ Reply

11 months ago, # ^ |

← Rev. 2 →

Idk, I looked through 6 cases just to be sure. It doesn't take much time tho. But you're kinda right

→ Reply

bunkerman

11 months ago, # ^ |

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.

→ Reply

11 months ago, # ^ |

You can see it, they're open now

→ Reply

noobcoder696969

11 months ago, # ^ |

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

→ Reply

Abhirup2002

11 months ago, # |

How to do problem e?

→ Reply

rope_and_snake

11 months ago, # ^ |

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)

→ Reply

Inori

11 months ago, # ^ |

Why is that? Could you explain please?

→ Reply

adityagamer

11 months ago, # ^ |

← Rev. 5 →

+12

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.

→ Reply

11 months ago, # ^ |

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

→ Reply

haha_haha

11 months ago, # ^ |

what is meant by rank here ?

→ Reply

f: https://atcoder.jp/contests/arc132/tasks/arc132_b

11 months ago, # ^ |

1, 10, 100, 1000...

→ Reply

rope_and_snake

11 months ago, # ^ |

← Rev. 4 →

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

→ Reply

lord_frieza

11 months ago, # |

Nice Problemset

→ Reply

cleanser

11 months ago, # |

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.

→ Reply

18o3

11 months ago, # ^ |

Yes

→ Reply

g_x_j

11 months ago, # |

+10

→ Reply

11 months ago, # ^ |

how did u find this, like how do u find the same problem in general?

→ Reply

g_x_j

11 months ago, # ^ |

+10

it just happened that I had seen this before

→ Reply

adityagamer

11 months ago, # ^ |

+19

This ARC B is much easier than current one because all numbers are distinct and also it is guaranteed that operation exist.

→ Reply

g_x_j

11 months ago, # ^ |

well, you are right

→ Reply

CoolPythonProgrammer

11 months ago, # ^ |

how does that make any difference?

→ Reply

_Lactosi

11 months ago, # |

C ruined the experience

→ Reply

Deep1809

11 months ago, # ^ |

235953756 Can't find the bug for code in C :(

→ Reply

phukaoz

11 months ago, # ^ |

what's idea of this solution

→ Reply

Deep1809

11 months ago, # ^ |

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)

→ Reply

tienloc1511

11 months ago, # ^ |

← Rev. 2 →

+11

I think it's because of vector of char instead of vector of int

→ Reply

Alex.Svanidze

11 months ago, # ^ |

+10

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.

→ Reply

Deep1809

11 months ago, # ^ |

Thanks a lot! its a blunder

→ Reply

carolinux

11 months ago, # ^ |

Same, sometimes those adhoc problems with the simple solution really stump me.

→ Reply

iamujj15

11 months ago, # |

Hints for problem E? Thanks.

→ Reply

kar2003

11 months ago, # ^ |

try to observe a pattern in the given test cases. There is simple formula hidden

→ Reply

llc5pg

11 months ago, # |

Solved F 20 minutes after the contest ended.

→ Reply

DuongForeverAlone

11 months ago, # |

+14

At first I thought G is 2-SAT. LOL

→ Reply

parag776

11 months ago, # ^ |

me to just for a second.

→ Reply

11 months ago, # ^ |

Me too!!

→ Reply

BF_OF_Priety

11 months ago, # |

I couldn't solve $$$C$$$ , have I really gotten that dumb!!!

→ Reply

iiand

11 months ago, # ^ |

Relax, I've solved the EFGA problems :)

→ Reply

anto777

11 months ago, # ^ |

Thanks man ! tbh I also felt like totally giving up. But both of your comments made my day !! :)

→ Reply

phukaoz

11 months ago, # ^ |

yeah when I first saw this problem I thought it was another easy problems.

RIP my rating

→ Reply

11 months ago, # ^ |

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...

→ Reply

NinJaa_Nyz07

11 months ago, # ^ |

Hey, Can you just prove your solution for C

→ Reply

11 months ago, # ^ |

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.

Base case: n=2 then s1!=s2, then we can make the length 0.
Inductive step: suppose it's true for n-2, now prove for n: we claim it is possible to remove characters so that no character occurs more than (n-2)/2 times in the remaining string. Take the most common character and remove it with any other character. In this way we can see that the condition is satisfied with the remaining string and we can continue until the string is empty.

When n is odd, the reasoning is similar, but since the parity of the length is constant, replace "0" by "1" in the above.

→ Reply

Mohanad.MT

6 months ago, # ^ |

← Rev. 8 →

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.

→ Reply

MJavad

11 months ago, # ^ |

← Rev. 3 →

You can always remove a pair which contains the most frequent letter, as long as all the letters are not the same...

→ Reply

Hasib.Nabid

11 months ago, # |

Solved my first ever live contest problem. Thanks!

→ Reply

11 months ago, # |

It's my first time to complete 4. Can I turn green?

→ Reply

11 months ago, # ^ |

nope ig , you are having delta +105

→ Reply

11 months ago, # ^ |

I'm confused,what “delt+105”?

→ Reply

11 months ago, # ^ |

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

→ Reply

11 months ago, # ^ |

I see.But how he can predict my delta so accurately? I thought this was calculated randomly based on rankings.

→ Reply

11 months ago, # ^ |

codeforces uses a rating system similiar to the chess elo system. Meaning they have a formula to calculate rating changes deterministically.

→ Reply

bit-trie

11 months ago, # ^ |

can you check my delta?

→ Reply

Orifkhon

11 months ago, # ^ |

use This extension

→ Reply

bit-trie

11 months ago, # ^ |

Error is large in this extension

→ Reply

11 months ago, # |

F implementation was tricky

→ Reply

parag776

11 months ago, # |

← Rev. 2 →

it would have been interesting if e would have been not for triplets but n-plets (basically for n numbers rather than 3 numbers).

→ Reply

11 months ago, # ^ |

I could not think of E yet, still trying lol

→ Reply

the_last_smilodon

11 months ago, # |

did any one else solve problem F using Hashing ?

my solution

→ Reply

11 months ago, # ^ |

can u pls explain ur solution, I am new to using hashing for strings in cp

→ Reply

the_last_smilodon

11 months ago, # ^ |

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.

→ Reply

11 months ago, # ^ |

thanks!

→ Reply

Matveyko

11 months ago, # ^ |

Nice idea!

→ Reply

the_last_smilodon

11 months ago, # ^ |

thank you!

→ Reply

adarsh403

11 months ago, # |

Can someone please explain problem D, how BS is working there?

→ Reply

11 months ago, # ^ |

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

→ Reply

11 months ago, # ^ |

← Rev. 2 →

[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:

bool good(int k, vector<pii> &segs){
    pair<int, int> current = make_pair(0,0);
    for (int i = 0; i < segs.size(); i++){
        current = make_pair(current.first-k, current.second+k); //we can jump anywhere here
        if(segs[i].first > current.second) return false; //no overlap
        if(segs[i].second < current.first) return false; //no overlap
        current = make_pair(max(current.first, segs[i].first), min(current.second, segs[i].second)); //we can be anywhere here
    }
    
    return true;
}

→ Reply

Astroflexx

11 months ago, # ^ |

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.

→ Reply

sulthanso73

11 months ago, # ^ |

← Rev. 3 →

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

→ Reply

rudraditya

11 months ago, # |

Either brain's not braining or found the problem D much harder that usual don't know why...

→ Reply

DuongForeverAlone

11 months ago, # |

How to solve G?

→ Reply

leovl48

11 months ago, # ^ |

+15

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.

→ Reply

yuan-shen

11 months ago, # ^ |

← Rev. 4 →

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

→ Reply

vstiff

11 months ago, # ^ |

Almost did it during the round, but didn't spot the trees and tried to find shortest paths to connect 1's instead

→ Reply

samadeep

11 months ago, # ^ |

Could you explain the code a little more in detail please ?

→ Reply

yuan-shen

11 months ago, # ^ |

← Rev. 2 →

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.

→ Reply

11 months ago, # |

Problem B : tried the greedy approach but im getting time limit exceeded, any thoughts? https://codeforces.me/contest/1907/submission/235958124

→ Reply

11 months ago, # ^ |

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.

→ Reply

11 months ago, # ^ |

so you make 2 different stacks that record all letters and merge them?

→ Reply

11 months ago, # ^ |

yeah,note that their index should be record at the same time for merge

→ Reply

treasuryonly

11 months ago, # ^ |

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 only aB pairs)

→ Reply

11 months ago, # ^ |

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.

→ Reply

amansingh81757

11 months ago, # ^ |

String length goes up to 1e6 your code has O(n^3) time complexity.

→ Reply

11 months ago, # ^ |

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.me/contest/1907/submission/235960691

→ Reply

https://codeforces.me/contest/1907/submission/235873405

11 months ago, # ^ |

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).

→ Reply

fernandezpalomojosue

11 months ago, # |

C>D>B>E>A

→ Reply

NinJaa_Nyz07

11 months ago, # ^ |

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... :(

→ Reply

harsha_.05_

11 months ago, # |

anyone finding Div3.D harder than usual ?

→ Reply

235939705 235936558 235937575 235905766

11 months ago, # ^ |

C and D were harder than div 2(for me at least)

→ Reply

Mayank_Pushpjeet

11 months ago, # ^ |

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.

→ Reply

feixiong

11 months ago, # ^ |

Question E is the simplest

→ Reply

Alonenonymous

11 months ago, # ^ |

Explain please how I am confused.

→ Reply

feixiong

11 months ago, # ^ |

When adding to the digits of these three numbers, it is impossible to generate carry operations. Knowing this, writing code only takes 5 minutes

→ Reply

Alonenonymous

11 months ago, # ^ |

How did the combinatorics part work?

→ Reply

feixiong

11 months ago, # ^ |

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

→ Reply

Ahmad_Hajjouz

11 months ago, # |

I think that the solution of problem B has been widely shared by cheaters. Here are some examples :

→ Reply

Astroflexx

11 months ago, # |

+24

Nice contest! Problems very really good. Thanks a lot for the round Vladosiya pashka MikeMirzayanov and all testers.

→ Reply

11 months ago, # |

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?

→ Reply

NeverSpot

11 months ago, # ^ |

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

→ Reply

vgtcross

11 months ago, # ^ |

← Rev. 2 →

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}$$$

$$$\mathrm{cnt_a} = 2$$$
$$$\mathrm{cnt_b} = 2$$$
$$$\mathrm{cnt_c} = 1$$$
$$$\mathrm{cnt_d} = 1$$$
$$$\mathrm{cnt_e} = 1$$$

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.

→ Reply

Pawan_Sharma99

11 months ago, # ^ |

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.

→ Reply

fernandezpalomojosue

11 months ago, # ^ |

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.

→ Reply

11 months ago, # ^ |

← Rev. 2 →

I thought of this too but then consider the test case: vvcvvv. You will compress this to 2,1,3. However, the 2 and 3 cannot reduce each other since they are both instances of v. 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.

→ Reply

fernandezpalomojosue

11 months ago, # ^ |

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

→ Reply

11 months ago, # ^ |

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 ...

→ Reply

vgtcross

11 months ago, # ^ |

← Rev. 2 →

Cuz the order of the letters doesn't matter.

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.

→ Reply

11 months ago, # ^ |

← Rev. 2 →

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.

→ Reply

vgtcross

11 months ago, # ^ |

← Rev. 2 →

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.

→ Reply

Pozay

11 months ago, # ^ |

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.

→ Reply

weirdflexbutok

11 months ago, # ^ |

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

→ Reply