Codeforces Round 913 (Div. 3)

2 года назад, скрыть # ^ |

Damn, what a nice explanation. Thanks!

→ Ответить

tickbird

2 года назад, скрыть # |

hardest div3c I've ever seen.

regular greedy approach simply not hold.

I'm losing hope in cp

→ Ответить

phukaoz

2 года назад, скрыть # ^ |

← Rev. 2 →

yeah i stuck at this problem for entire contest :(

any idea for this problem?

→ Ответить

2 года назад, скрыть # ^ |

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

→ Ответить

Loganwick

2 года назад, скрыть # ^ |

how did you come to this idea?

→ Ответить

2 года назад, скрыть # ^ |

randomly trying stuff.

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

→ Ответить

Loganwick

2 года назад, скрыть # ^ |

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

→ Ответить

2 года назад, скрыть # ^ |

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.

→ Ответить

vivek_coder_9

2 года назад, скрыть # ^ |

look at his colour ;)

→ Ответить

m_nature

2 года назад, скрыть # ^ |

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

→ Ответить

gvne

2 года назад, скрыть # ^ |

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

→ Ответить

m_nature

2 года назад, скрыть # ^ |

← 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

→ Ответить

gvne

2 года назад, скрыть # ^ |

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

→ Ответить

m_nature

2 года назад, скрыть # ^ |

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

→ Ответить

Si_jo

2 года назад, скрыть # |

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.

→ Ответить

surajiyer

2 года назад, скрыть # |

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

→ Ответить

2 года назад, скрыть # ^ |

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

→ Ответить

bunkerman

2 года назад, скрыть # ^ |

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.

→ Ответить

2 года назад, скрыть # ^ |

← Rev. 2 →

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

→ Ответить

bunkerman

2 года назад, скрыть # ^ |

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.

→ Ответить

2 года назад, скрыть # ^ |

You can see it, they're open now

→ Ответить

Sachinkumar99

2 года назад, скрыть # ^ |

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

→ Ответить

Abhirup2002

2 года назад, скрыть # |

How to do problem E?

→ Ответить

Abhirup2002

2 года назад, скрыть # |

How to do problem e?

→ Ответить

rope_and_snake

2 года назад, скрыть # ^ |

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)

→ Ответить

Inori

2 года назад, скрыть # ^ |

Why is that? Could you explain please?

→ Ответить

adityagamer

2 года назад, скрыть # ^ |

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

→ Ответить

2 года назад, скрыть # ^ |

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

→ Ответить

haha_haha

2 года назад, скрыть # ^ |

what is meant by rank here ?

→ Ответить

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

2 года назад, скрыть # ^ |

1, 10, 100, 1000...

→ Ответить

rope_and_snake

2 года назад, скрыть # ^ |

← 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

→ Ответить

NEERAJ2003

2 года назад, скрыть # |

Anyone Can give more precise view of E I just saw the first observation of how last character making answer and then rest what I did is in hurry and that worked LOL

→ Ответить

cleanser

2 года назад, скрыть # |

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.

→ Ответить

18o3

2 года назад, скрыть # ^ |

Yes

→ Ответить

MaribelHearn

2 года назад, скрыть # |

+10

→ Ответить

yggy

2 года назад, скрыть # ^ |

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

→ Ответить

MaribelHearn

2 года назад, скрыть # ^ |

+10

it just happened that I had seen this before

→ Ответить

adityagamer

2 года назад, скрыть # ^ |

+19

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

→ Ответить

MaribelHearn

2 года назад, скрыть # ^ |

well, you are right

→ Ответить

_Lactosi

2 года назад, скрыть # |

C ruined the experience

→ Ответить

Deep1809

2 года назад, скрыть # ^ |

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

→ Ответить

phukaoz

2 года назад, скрыть # ^ |

what's idea of this solution

→ Ответить

Deep1809

2 года назад, скрыть # ^ |

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)

→ Ответить

tienloc1511

2 года назад, скрыть # ^ |

← Rev. 2 →

+11

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

→ Ответить

Alex.Svanidze

2 года назад, скрыть # ^ |

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

→ Ответить

Deep1809

2 года назад, скрыть # ^ |

Thanks a lot! its a blunder

→ Ответить

iamujj15

2 года назад, скрыть # |

Hints for problem E? Thanks.

→ Ответить

kar2003

2 года назад, скрыть # ^ |

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

→ Ответить

llc5pg

2 года назад, скрыть # |

Solved F 20 minutes after the contest ended.

→ Ответить

DuongNeverAlone

2 года назад, скрыть # |

+14

At first I thought G is 2-SAT. LOL

→ Ответить

parag776

2 года назад, скрыть # ^ |

me to just for a second.

→ Ответить

2 года назад, скрыть # ^ |

Me too!!

→ Ответить

FiniteMoves

2 года назад, скрыть # |

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

→ Ответить

FiniteMoves

2 года назад, скрыть # |

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

→ Ответить

tbank

2 года назад, скрыть # ^ |

Relax, I've solved the EFGA problems :)

→ Ответить

2 года назад, скрыть # ^ |

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

→ Ответить

NinJaa_Nyz07

2 года назад, скрыть # ^ |

Hey, Can you just prove your solution for C

→ Ответить

2 года назад, скрыть # ^ |

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.

→ Ответить

MJavad

2 года назад, скрыть # ^ |

← Rev. 3 →

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

→ Ответить

shesgirlGhost

2 года назад, скрыть # |

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

→ Ответить

2 года назад, скрыть # ^ |

nope ig , you are having delta +105

→ Ответить

shesgirlGhost

2 года назад, скрыть # ^ |

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

→ Ответить

2 года назад, скрыть # ^ |

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

→ Ответить

shesgirlGhost

2 года назад, скрыть # ^ |

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

→ Ответить

2 года назад, скрыть # ^ |

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

→ Ответить

bit-trie

2 года назад, скрыть # ^ |

can you check my delta?

→ Ответить

Orifkhon

2 года назад, скрыть # ^ |

use This extension

→ Ответить

bit-trie

2 года назад, скрыть # ^ |

Error is large in this extension

→ Ответить

2 года назад, скрыть # |

F implementation was tricky

→ Ответить

parag776

2 года назад, скрыть # |

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

→ Ответить

2 года назад, скрыть # ^ |

I could not think of E yet, still trying lol

→ Ответить

the_last_smilodon

2 года назад, скрыть # |

did any one else solve problem F using Hashing ?

my solution

→ Ответить

yggy

2 года назад, скрыть # ^ |

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

→ Ответить

the_last_smilodon

2 года назад, скрыть # ^ |

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.

→ Ответить

Matveyko

2 года назад, скрыть # ^ |

Nice idea!

→ Ответить

the_last_smilodon

2 года назад, скрыть # ^ |

thank you!

→ Ответить

adarsh403

2 года назад, скрыть # |

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

→ Ответить

2 года назад, скрыть # ^ |

← 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;
}

→ Ответить

Astroflexx

2 года назад, скрыть # ^ |

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.

→ Ответить

sulthanso73

2 года назад, скрыть # ^ |

← 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

→ Ответить

rudraditya

2 года назад, скрыть # |

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

→ Ответить

DuongNeverAlone

2 года назад, скрыть # |

How to solve G?

→ Ответить

leovl48

2 года назад, скрыть # ^ |

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

→ Ответить

yuan-shen

2 года назад, скрыть # ^ |

← 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

→ Ответить

vstiff

2 года назад, скрыть # ^ |

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

→ Ответить

samadeep

2 года назад, скрыть # ^ |

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

→ Ответить

yuan-shen

2 года назад, скрыть # ^ |

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

→ Ответить

fernandezpalomojosue

2 года назад, скрыть # |

C>D>B>E>A

→ Ответить

harshaa005

2 года назад, скрыть # |

anyone finding Div3.D harder than usual ?

→ Ответить

Mayank_Pushpjeet

2 года назад, скрыть # ^ |

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.

→ Ответить

2 года назад, скрыть # ^ |

Question E is the simplest

→ Ответить

Alonenonymous

2 года назад, скрыть # ^ |

Explain please how I am confused.

→ Ответить

2 года назад, скрыть # ^ |

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

→ Ответить

Alonenonymous

2 года назад, скрыть # ^ |

How did the combinatorics part work?

→ Ответить

235939705 235936558 235937575 235905766

2 года назад, скрыть # ^ |

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

→ Ответить

Ahmad_Hajjouz

2 года назад, скрыть # |

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

→ Ответить

Astroflexx

2 года назад, скрыть # |

+24

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

→ Ответить

2 года назад, скрыть # |

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?

→ Ответить

NeverSpot

2 года назад, скрыть # ^ |

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

→ Ответить

vgtcross

2 года назад, скрыть # ^ |

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

→ Ответить

Pawan_Sharma99

2 года назад, скрыть # ^ |

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.

→ Ответить

fernandezpalomojosue

2 года назад, скрыть # ^ |

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.

→ Ответить

2 года назад, скрыть # ^ |

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

→ Ответить

fernandezpalomojosue

2 года назад, скрыть # ^ |

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

→ Ответить

gvne

2 года назад, скрыть # ^ |

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

→ Ответить

vgtcross

2 года назад, скрыть # ^ |

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

→ Ответить

2 года назад, скрыть # ^ |

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

→ Ответить

vgtcross

2 года назад, скрыть # ^ |

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

→ Ответить

weirdflexbutok

2 года назад, скрыть # ^ |

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

→ Ответить

https://mirror.codeforces.com/contest/1907/submission/235957135

2 года назад, скрыть # ^ |

← Rev. 4 →

But if we consider the test case presented earlier by vgtcross: acbdaeb, we see that the two highest frequency characters a and b 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).

→ Ответить

weirdflexbutok

2 года назад, скрыть # ^ |

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)

→ Ответить

A4n0n4

2 года назад, скрыть # ^ |

← Rev. 3 →

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.

→ Ответить

weirdflexbutok

2 года назад, скрыть # ^ |

yeah that's it

→ Ответить

PyAlpha

2 года назад, скрыть # ^ |

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.

→ Ответить

A4n0n4

2 года назад, скрыть # ^ |

← Rev. 4 →

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.

→ Ответить

PyAlpha

2 года назад, скрыть # ^ |

That is also not true. Basically you are saying that in abaca, I will be able to pair b and c, delete them and end up with aaa, but that is not the case.

→ Ответить

A4n0n4

2 года назад, скрыть # ^ |

← Rev. 2 →

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.

→ Ответить

sevlll777

2 года назад, скрыть # ^ |

+20

А 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

→ Ответить

adaptatron

2 года назад, скрыть # ^ |

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.

The Trick

Submission

→ Ответить

Tanjiro_Nezuko

2 года назад, скрыть # |

I wanted help with problem C please, it is failing in test case 2

→ Ответить

TokaiZaopen

2 года назад, скрыть # ^ |

maybe, show the code could help make the problem more clear?

→ Ответить

TokaiZaopen

2 года назад, скрыть # ^ |

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://mirror.codeforces.com/contest/1907/submission/235898166

→ Ответить

TokaiZaopen

2 года назад, скрыть # ^ |

← Rev. 2 →

What's more, it's usually not a good idea to use vector(bool) due to some historical reasons. Try to use bitset instead.

→ Ответить

hundunlilun1

2 года назад, скрыть # |

Do you believe light? 你相信光吗？

→ Ответить

what-force

2 года назад, скрыть # |

Was this round rated? Why is it showing unrated?

→ Ответить

Clownfish.

2 года назад, скрыть # ^ |

It's not time yet. Normally, it would rate.

→ Ответить

mayankprtp

2 года назад, скрыть # |

Why does my solution give TLE for problem B

→ Ответить

bhajji

2 года назад, скрыть # ^ |

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

→ Ответить

alpha1215

2 года назад, скрыть # ^ |

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

→ Ответить

Clownfish.

2 года назад, скрыть # |

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.

→ Ответить

rrohann__

2 года назад, скрыть # |

pls explain problem E. Thank you

→ Ответить

Alex.Svanidze

2 года назад, скрыть # ^ |

How I solved it, although I'm not sure if I explain it well enough.

Hint

The main idea

I hope this makes sense, lol.

→ Ответить

miko089

2 года назад, скрыть # |

почему рейтинг за раунд не начислен?

→ Ответить

2 года назад, скрыть # ^ |

Сори, но весь рейтинг достанется мне

→ Ответить

glennmendonca

2 года назад, скрыть # |

← Rev. 2 →

why didn't the submission 235883526 solution not work for 1907B - YetnotherrokenKeoard (problem B)? was it because of memory copy?

→ Ответить

arash.

2 года назад, скрыть # ^ |

ans = str[i] + ans

This works in O(|ans|) which overall is O(n^2)

→ Ответить

samdani333

2 года назад, скрыть # |

why it is so late to publish ratings nowadays?

→ Ответить

defarias25

2 года назад, скрыть # |

After 10 contests, I'm finally green!

→ Ответить