Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | nor | 157 |
4 | atcoder_official | 156 |
4 | cry | 156 |
6 | -is-this-fft- | 155 |
7 | maroonrk | 154 |
8 | adamant | 153 |
9 | Um_nik | 151 |
10 | djm03178 | 146 |
Название |
---|
Can someone please explain problem A?
U are given some activities (n) starting from 1 upto n. Now u are given m other activities which are other than the previous 1-n ,i.e, n+1 to ahead. When a total new activity comes, u have to remove the oldest activity from back and if after sometime existing activity comes, u don't need to remove anything bcz there's already that activity ongoing.... Obviously 1 to n won't be there in the m activities, so we just have to print what activities still exists (-1 if they do) and if they have left the queue then at what time did they...
You can use set in this question. Iterate the actions from starting and see if the element is present in set then do nothing if it is not present then you have to remove the last post and element in the set. You can use a counter for knowing which is the last element in the recent field.
I think F can be solved in $$$O(n*log(n))$$$. My idea is probably different from the author's one, and I will try to improve the code.
Edit: tutorial on $$$O(N*log(N))$$$ solution: link
I had the same idea and was very surprised with how easy problem F actually was. Like, it's just simple greedy which is easily provable and we don't even need to optimize it with down to $$$O(NlogN)$$$.
I bet that if they placed it as C or D, a lot of people would solve it
F can be trivially solved in $$$O(n \; log^2\; (Wn))$$$ by simply using linkret trick, well known in Croatia (yes, not China :P).
https://mirror.codeforces.com/blog/entry/49691
how do we know it's not well known in China too XD?
Everything is well known in China, but this is also well known in Croatia as well xD.
I think that one is well known for everyone that you can call an "experienced contestant"
TIL I'm an inexperienced contestant
Ofc it's not a rule, as some people missed that problem. But for people that actually went around learning these tricks from problems, that's a huge problem that I'd be surprised if more people that were active at around 2017-2019 missed that problem than people that know it.
Perhaps you're just so good at the basics that you don't look into these weird little tricks.
Yeah, to be clear I was being (mostly) sarcastic :) I also wasn't especially active on CF until around 2018 and wasn't regularly participating at a Div. 1 level until 2019, so there are still lots of problems that were standard back then that I just haven't run into :p
Also well known in China, and it is often called "wqs binary search" in China. :)
Looking through your submission history, I noticed that you received WA with the code from this blog (195181117), but got AC with some additional trick(195185134). Do you know why? I am facing simmilar issue, but I don't undestand why in this problem the typical implementation of this trick seems to fail.
You can look at the blog for more details. Essentially the first solution doesn't handle some edge cases well and is less numerically stable because of the use of doubles. The second solution handles those better and uses fractions as well.
I didn't notice Neal's comment at first. Thanks
I’m so mad, I solved E 5 mins after contest ended ;(. I can’t solve anything in contest.
Don't be upset. You will be successful next time!
Thanks :)
Please add the proof of solution of problem C.
"This problem is trivial and the solution is easy to see"
Is probably enough as an editorial in the opinion of the person that approved that problem.
Somehow this is literally the editorial for E.
We need proofs!
1) Suppose there are only one 'a' and one or more 'b' and no other letters are left. If we consider how words are created depending on the location of a, we can see that the optimal is to place 'a' in the center.
2) Suppose there are one 'a' and one or more 'b' and at least one 'c' are left. If a word starts with 'b' and ends with 'a', the optimal (in this case) is to place the remaining symbols in order from the front. Let's prove this word (say w) is optimal. Let x be a position 'c' is appear in w. Suppose that word does not end with 'a'. Then the word must end with 'b', and in order for the word to be less than w, 'a' must be located between position 1 and position x. (Note that positions 1 through x-1 in w are filled with 'b'.) However, when this happens, the word is smaller than its reverse, which is a contradiction.
Sorry for my poor English.
Can’t E be solved faster by just checking where the two cities would intersect and then connecting cities in each x and y?
I do operation two times not (n+m) times still accepted in E,I don't know why.
Technically 4 because the editorial is referring to filling the y and x as separate conditions. You only need to do it twice, but you don’t know whether to start with the y or x so it’s satisfactory to do it four times to fix orientation. This is because after you fill x or y, if it can be filled it will at most give some new x that also needs to be filled. When it fills x, this will be the last operation given the statements above are true because it will fill every x in each y it added or there would be a gap between the two cities which does not need to be filled. Since it’s doing this on each x in the connected component’s range, it also fixes each y. Same thing vice versa.
Here's how I solved C:
Okay, so, after some time I came up with something which could be close to a concrete proof of this solution (or the explanation of the idea behind the tricky step number 6).
Let's look at the example like aaabbbbcc. First, we would process the 2 equal characters at the start of the string s, after this step our answer string would look like this: a ******* a, where the characters in bold are the most recently added ones and the rest are 7 characters that we still need to figure out.
Now the 2 most left characters in the sorted string s are not equal. However, for now, we are going to treat them as if they were equal characters. After this step the answer string is going to look like this: ab ***** ba, where the character in bold is the "lesser" character 'a' that we have temporarily replaced. We are going to figure out where that 'a' goes later, for now we just have to remember the position of the substituted character, the replacement character 'b' and the original character 'a'.
Now we fill our answer string with what's left of the sorted string s: abbbbcc b a. In this case, since the rest of characters in the string is sorted and we have characters that are "bigger" than 'b', our "palindrome" is in a bad spot right now (we were trying to build one, remember): if we were to reverse it, the resulting string would be lexicographically bigger than our current answer, which is not what we want. So, our only hope is to substitute that bold 'b' back to a, resulting in our final answer.
The step with the filling out the rest of the answer can have 2 total cases:
This process is similar to what is described in the second point of the C solution in editorial, however, described trick with c times y and break seems to be a little bit out of the blue.
Let's consider the most "annoying" cases, where the lesser character jumps in to the middle of the answer tmax, strings like abb, abbb, aaabbbbb. You can see, that according to this solution we would get the right corresponding answers: bab, bbab and abbbabba.
I have found an $$$O(N*log(N))$$$ amortized solution to F. Code: 195201483
The idea is simple. First, we sort the array in decreasing order.
$$$O(N^2)$$$: We iterate over to how many elements from the beginning we will apply both operations. After that, we know that there are $$$n-both$$$ elements to which we can apply at least one operation. We take $$$k1-both+k2-both$$$ greatest elements after $$$both$$$ taken elements from the array. Now, we apply operation 1 to all of them. We must apply $$$k2-both$$$ operations of type 2, so we choose $$$k2$$$ elements with biggest delta $$$cost2(a_i)-cost1(a_i)$$$ where $$$cost1$$$ and $$$cost2$$$ are functions that return an integer after applying operation 1 and 2 respectively.
$$$O(N*log(N))$$$: note that there are not a lot of changes if we calculate answer for some $$$both$$$ and $$$both+1$$$. We can use ordered_set of deltas $$$cost2(a_i)-cost1(a_i)$$$ in order to maintain to which numbers we apply 1 or 2 operation.
I believe I have a solution to E in $$$\mathcal{O}(nm)$$$ which also solves the problem for arbitrarily many cities/components (not just two). It consists of two simple steps:
Just be careful not to accidentally disconnect the cities again when removing corners, and you should be good. Here's a link to my submission: https://mirror.codeforces.com/contest/1799/submission/195179223
I haven't thought about a rigorous proof of correctness yet, so I welcome any hacks to my solution if any such hacks exist!
Where's H editorial?
Another way to solve D2 1799D2 - Hot Start Up (hard version), define
dp[i][same cpu with i-1 ?] = min time
if use
cold
, thendp[i][true/false] = min(dp[i-1][true],dp[i-1][false]) + cold[a[i]]
if use
hot
, lett[a[i]]
be thea[i]
last exist time.t[a[i]] + 1 == i
,dp[i][true] = min(dp[i-1][true],dp[i-1][false]) + hot[a[i]]
t[a[i]] + 1 < i
, thent[a[i]] + 1..i-1
is using same CPU, so thatdp[i][false] = dp[t[a[i]]+1][false] + sum(cold/hot[t[a[i]]+2..i-1]) + hot[a[i]]
, the middle sum can be precaculate with prefix sum,in this way there is no need for segtree
Thanks for sharing this, I was losing my head over my solution! I thought of the same but stupidly used
dp[t[a[i]]
when I should've been usingdp[t[a[i]+1]
as you mention; kept thinking of ways to get that working, gave up and just solved D1 instead.Can you share me your submission, please?
195421246
key part of the code
you are genius!!
I have a different $$$O(n + k)$$$ solution for the problem 1799D2 - Hot Start Up (hard version).
Let's say we currently need to run program $$$x$$$ and we want to run it in $$$hot_x$$$ seconds. To do this, we can use the same CPU that we used for the previous $$$x$$$, and use the other CPU for every program between these two. If the index of previous $$$x$$$ is $$$i$$$ and current $$$x$$$ is $$$j$$$, this means $$$i$$$ and $$$j$$$ will have the CPU 1, and every program in $$$[i + 1, j - 1]$$$ will have the CPU 2, or vice versa.
So, if we know the answer to finish the first $$$i$$$ programs we can calculate the answer for $$$j$$$. To calculate the amount of time needed to use the other CPU for the tasks $$$[i + 1, j - 1]$$$, we can use prefix sums where the $$$kth$$$ program takes $$$cold_k$$$ seconds if it's different from the previous program and $$$hot_k$$$ seconds otherwise.
However, there is something we're missing here. Please try to find it on your own.
While calculating the time needed for programs $$$[i + 1, j - 1]$$$, we don't have any information about the last program that ran on CPU 2. It could be the same as program $$$i + 1$$$ which might change the answer.
Let's consider the case where the program $$$i + 1$$$ is the same as the last program that ran on CPU 2. If we call this program $$$y$$$, then CPU usage will look like this:
Looking at this, we can notice that if we know the minimum amount of time needed to finish programs $$$[1, i + 1]$$$, where the program $$$i + 1$$$ uses the same CPU as the previous same program, we know the program that ran last on the other CPU. Program $$$i$$$ used CPU 1 while program $$$i + 1$$$ used CPU 2. Using this, we can calculate the time needed for $$$[i + 2, j - 1]$$$ and update the answer for the program $$$j$$$ accordingly.
Let's say function $$$C(l, r)$$$ calculates the amount of time necessary to run programs [l, r] using prefix sums as I wrote earlier, $$$a_i$$$ stores the program number of $$$ith$$$ program, and $$$nxt_i$$$ stores the next index with the same program as this index.
We can keep track of two different $$$dp$$$ arrays or one array with dimensions $$$(n, 2)$$$. For simplicity, let's keep track of two arrays and call them $$$A$$$ and $$$B$$$. $$$A_i$$$ stores the minimum amount of time to run the first $$$i$$$ programs if program $$$i$$$ took $$$cold_{a_i}$$$ seconds and $$$B_i$$$ stores the amount of time if it took $$$hot_{a_i}$$$ seconds.
If we're at program $$$i$$$ and we want to update the next $$$dp$$$ values we can do it like this:
If $$$a_i = a_{i + 1}$$$
If $$$a_i \neq a_{i + 1}$$$
If program $$$i + 1$$$ took $$$hot_{a_{i + 1}}$$$ seconds
If program $$$i + 1$$$ will take $$$cold_{a_{i + 1}}$$$ seconds
It's possible to only use one array considering that if we're currently at index $$$i$$$ the answer for $$$i + 1$$$ will only be $$$B_{i + 1}$$$. However, I think it's easier to understand this way.
Here is my implementation: 195175862
I tried to write it as clear as possible. However, I was in contest so if there is a mistake I'm sorry.
Please let me know if you have any questions or if there is any mistake.
Thanks for explaining so well. Your example helped clear it up for me, I was stuck on the same issue and dropped this idea mid-contest in order to solve D1 in time.
what is wrong with this submission? failing on test case 8
https://mirror.codeforces.com/contest/1799/submission/195211040
nevermind got it my solution does not guarantee that all elements are same at the end
I also have a different O(n + k) solution for D2 with a very simple implementation: 195175038
If you are interested, you can watch my video: https://www.youtube.com/watch?v=oOyPQL16x1M
What's intended for problem G? I solved it by counting it directly using DP, but everything that I know about solutions like this points to this dp being O(N^4), is it possible that it is O(N^3)?
https://mirror.codeforces.com/contest/1799/submission/195217087
Edit: I think that I managed to prove it being O(N^3). Basically for the transition at the first state being "i", we have at most (a[i] + 1) * (b[i] + 1) transitions. The sum of a[i] * b[i] is at most O(N^2). For each i, dp[i][j] has at most O(N) valid j's, so it ends up being O(N^3).
Could you elaborate a bit more on your DP solution?
I'm not sure if tfg did the same, but I just upsolved it without inclusion-exclusion and I used dp too. I calculated $$$dp_{i,j} = $$$ number of ways to vote if we only use the first $$$i$$$ groups and among the first $$$i$$$ groups $$$j$$$ people voted. To make transitions you want to know two things: how much people will vote for the new group that are also from the prefix, and how much people from the new group will vote for someone who is already on the prefix. In total there are $$$4$$$ loops, so it might look like it's $$$O(n^4)$$$, but $$$\sum_{i=1}^n sum_i*sz_i \leq n^2$$$, so the $$$3$$$ internal loops are actually $$$O(n^2)$$$ and the solution is $$$O(n^3)$$$. You might want to see my code.
My solution is $$$O(n^2)$$$ or $$$O(n\log^2 n)$$$(using divide and conquer FFT). I use inclusion–exclusion principle and calculate ways under $$$k$$$ fixed invalid votes.
I'm a little confused with the constraint...
For E, you could do the “filling” as stated in the editorial last and find the intersection point first. You can just put a # there and then fill it. 195194226
Why is the title of question B in the English answer in Russian?
Bad problem ABC
Why is the constraint of the G problem so small? I thought this problem could be solved using formal power series in $$$\mathrm{O}(N\log^2N)$$$.
my submission:https://mirror.codeforces.com/contest/1799/submission/195220905
Actually I have an $$$O(N^2)$$$ solution with (quadratic)polynomial convolution, but can be improved to $$$O(NlogN)$$$ with NTT, this is my submission 195224839
I think any time there's a question of why bounds aren't higher, the answer is usually that increasing the bounds doesn't make the problem more interesting, just more tedious, so then it's polite to keep it lower. I also solved the problem with inclusion-exclusion, and my code can be easily turned from $$$\mathcal O(n^3)$$$ to $$$\mathcal O(n \log^2 n)$$$ by iterating more precisely over sum of $$$c_i$$$ per team and copy pasting some FFT templates, but that doesn't make the problem more interesting and is not the main idea of the problem imo.
Hi guys you can check video editorial for
Problem A , Problem B, Problem C, Problem D here — https://youtu.be/AGIrdT_cQuY
I think the solotion for E maybe $$$O(nm)$$$?
Actually, we can use $$$2$$$ times filling operation to make a connected component meet the requirements.
Here's my submission.
How do you approach Problem G?
You can refer to this comment
Passed E with $$$O(nm^4)$$$ and some Chinese kung fu(small constant) again! Can it be hacked?
Link: https://mirror.codeforces.com/contest/1799/submission/195236064
Can anybody explain to me why my code won't give a correct output for D1? I'm stuck on it for hours and can't convince myself why it is wrong. my submission for D1
E,How to prove (i1,j1),(j2,j2) any Manhattan shortest path is right
In f, why can’t just pick k1 biggest elements to apply halve, then pick k2 biggest elements to apply subtract?
Here's how I solved problem G.
In such problems with some restrictions, using inclusion-exclusion often helps us. In this problem, we have the condition that people cannot vote for someone from the same team.
Suppose $$$s[i]=\sum_{j=1}^{i} c_j$$$, where $$$s_0=0$$$.
First of all, let's see what valid voting looks like. Assume that we have put $$$n$$$ boxes such that number $$$i$$$ is written on the boxes at positions $$$s_{i-1}+1$$$ to $$$s_i$$$ from the left. Notice the boxes having the same numbers are indistinguishable. Suppose $$$b_i$$$ is written on the $$$i-$$$th box from the left. Consider a permutation $$$p$$$ of length $$$n$$$ such that $$$p_i$$$ cast his vote in the $$$i-$$$th box. In a valid voting, $$$p_i$$$ and $$$b_i$$$ should not belong to the same team.
So our restriction is that $$$p_i$$$ and $$$b_i$$$ should not belong to the same team.
Suppose $$$dp[i]$$$ gives the number of permutations $$$p$$$ such that $$$p_j$$$ and $$$b_j$$$ belong to the same team at atleast $$$i$$$ indices.
Now calculating $$$dp[i]$$$ is easy. Suppose set $$$S_t$$$ denotes the players of team $$$t$$$. Assume $$$V(S_t)=\sum_{x \in S_t} c_x$$$. So there are $$$V(S_t)$$$ boxes containing the number of team members $$$t$$$.
How many ways are there to cast a vote, such $$$l$$$ people from team $$$t$$$ cast their votes in $$$l$$$ boxes belonging to people from the same team? It is $$$\binom{|S_t|}{l} \cdot \binom{V(S_t)}{l} \cdot l!$$$. Let us denote this by $$$W(S_t,V(S_t),l)$$$. How to get this? First, we decide which $$$l$$$ people out of $$$S_t$$$ to take. We get $$$\binom{|S_t|}{l}$$$ for that part. We must select $$$l$$$ boxes out of $$$V(S_t)$$$ boxes. We get $$$\binom{V(S_t)}{l}$$$ for that part. Now we can permute these $$$l$$$ people in any way, as all $$$l!$$$ permutations satisfy our condition. We are not focussing on the remaining $$$S_t-l$$$ people right now.
So $$$dp[i]=(n-i)! \cdot \Pi_{t \in T} W(S_t,V(S_t),f_t)$$$, where $$$T$$$ denotes the set of available teams and $$$\sum_{t \in T} f_t = i$$$. How to get this? First of all, according to our definition of $$$dp[i], $$$ atleast $$$i$$$ people should vote for people from the same team. $$$\Pi_{t \in T} W(S_t,V(S_t),f_t)$$$ gives us the number of ways such that exactly $$$i$$$ people vote for people from same team. Now $$$n-i$$$ people are left. They can cast their vote without any restriction. Note that $$$n-i$$$ boxes are left. So we can permute $$$n-i$$$ people over $$$n-i$$$ boxes. Thus we get $$$(n-i)!$$$ for this part.
Suppose $$$ans[i]$$$ gives the number of permutations $$$p$$$ such that $$$p_j$$$ and $$$b_j$$$ belong to the same team at exactly $$$i$$$ indices. Now $$$ans[i]=dp[i]-\sum_{j=i+1}^{n} \binom{j}{i} \cdot ans[j]$$$. Now how to get this? So $$$dp[i]$$$ gives us the number of permutations for all atleast $$$i$$$ indices. We need to remove the permutations in which more than $$$i$$$ people vote for people from the same team.
Suppose $$$d$$$ is a permutation of length $$$n$$$ such that $$$d_k$$$ and $$$b_k$$$ belong to the same team at exactly $$$j$$$ indices. How many times would we have counted $$$d$$$ in $$$dp[i]$$$? We would have counted it $$$\binom{j}{i}$$$ times. So we got $$$\sum_{j=i+1}^{n} \binom{j}{i} \cdot ans[j]$$$ this way.
Are we done? Not yet. Did you notice that the boxes with the same numbers are indistinguishable?
We would have overcounted.
So if $$$final[i]$$$ denotes the number of votings such that exactly $$$i$$$ person(s) vote person(s) from same team, $$$final[i]=\frac{ans[i]}{\Pi_{i=1}^{n} c_i}$$$.
Our answer is just $$$final[0]$$$.
Time complexity is $$$O(n^2)$$$(thanks to AbdelmagedNour for pointing it out).
I want to say that your solution is not $$$O(n^3)$$$, actually it's better. It's only $$$O(n^2)$$$.
Why that's true?
In calculation of dp, you have 3 loops, the first go from $$$1$$$ to $$$n$$$, the second go from $$$0$$$ to $$$n$$$, but the third doesn't always go to $$$n$$$. It goes from $$$0$$$ to $$$S[i]$$$, and sum of $$$S[i]$$$ overall values of $$$i$$$ is exactly $$$n$$$.
So the complexity is only $$$O(n^2)$$$.
Oh yes, thanks for mentioning it. I have edited my comment.
My doubt is related to problem A. In sample test case number 8. There are 16 unique new posts. And in my code I printed "-1" n-set.size() times (4-16 times which actually should not print "-1" at all). But it is giving TLE. When I printed the value n-set.size() in my terminal. It prints the value 18446744073709551604. Shouldn't it print -12 ?
If you use
size_t
or other unsigned type forn
, thenn - set.size()
is also unsigned, and subtraction overflows yielding $$$2^{64} - 12$$$.But I stored n in
int
which is by default a signed container.but set.size() is an unsigned int; when you perform an operation with an unsigned and a signed int, the latter casts to the unsigned type
can someone elaborate on why we pick the smallest and largest elements greedily at each step in problem B
Where is tutorial for problems G & H?
I found C to be a lot more intuitive when solved recursively.
My idea was first, sort the string lexicographically from least to greatest. Then, iterate over every 2 characters.
$$$s = c_0 c_1 \dotsc c_n$$$
Let $$$f(x)$$$ return the minimum of $$$\text{max}(x,\text{reverse}(x))$$$ (in other words, the problem statement; we want $$$f(s)$$$ )
Let our answer $$$a$$$ be an empty string for now. If $$$c_0 = c_1$$$, then it's clear that $$$a = c_0 \underbrace{\dotsc \dotsc \dotsc \dotsc}_{\text{remaining characters}} c_1$$$ minimizes the lexicographic maximum because any other arrangement would have one orientation be clearly greater. For example, if $$$s = aabbb$$$ then placing any character on the ends other than $$$a$$$ would be worse than just placing $$$a$$$ on both ends.
So, the problem now recurses, we need to find the minimum of $$$\text{max}(c_2c_3\dotsc c_n,c_nc_{n-1}\dotsc c_2)$$$ to fill in the remaining characters of $$$a$$$, aka $$$f(c_2c_3\dotsc c_n)$$$
So, our answer in this case would simply be $$$f(s) = c_0 + f(c_2c_3\dotsc c_n) + c_1$$$, where $$$+$$$ is string concatenation.
Now, if $$$c_0 > c_1$$$, then we have two choices. We can either have
Case 1. $$$a$$$ = $$$c_1 c_2 c_3 \dotsc c_n c_0$$$, because $$$\text{max}(a,\text{reverse}(a)) = a$$$
Case 2. $$$a$$$ = $$$c_1c_3c_4 \dotsc c_0 \dotsc c_nc_2$$$
I claim that case 2 will only be better if and only if there are exactly two different letters left and $$$c_1 = c_2$$$. Let's take an example $$$s_1 = abbbbb\dotsc b$$$
We can write case 1 as $$$a_1 = bbb\dotsc ba$$$, and case 2 as $$$a_2 = bb\dotsc a \dotsc b$$$
Let's look closely as my claim for case 2 being better than case 1.
$$$c_0 > c_1$$$, only two types of letters, and $$$c_1 = c_2$$$.
This immediately tells us that $$$c_0$$$ is the only letter of its kind. If it wasn't, then $$$c_0$$$ can't be greater than $$$c_1$$$. We can also deduce that there are at least two letters of the second kind, since $$$c_1 = c_2$$$ (we assume $$$c_2$$$ exists in this context).
Let's call $$$c_0 = a$$$ and $$$c_1 = c_2 = \dotsc = c_n = b$$$ to make things a bit more clear.
If we use up our only $$$a$$$ and delegate it to the back of our answer, then we won't be able to use it anywhere else (this should be obvious, since we only have 1 $$$a$$$, we should treasure it). $$$\text{max}(c_0 c_1 \dotsc c_n,c_n c_{n-1} \dotsc c_0)$$$ will just be the side starting with $$$b$$$, and our $$$a$$$ will only be in use at the end. So our string in case 1 will just end up looking like $$$bbbbb\dotsc bbba$$$
We can clearly do better. Since $$$\text{max}(c_0 c_1 \dotsc c_n,c_n c_{n-1} \dotsc c_0)$$$ is going to start off with a $$$b$$$ anyway, why not just place $$$b$$$ on both sides and use our precious $$$a$$$ when it really counts. Well, we get one shot with using it and we want to put it in the best spot such that no matter if the string is reversed, it'll be as close to minimum as possible. If we decide to place our $$$a$$$ early up (suppose $$$bbbabbbbbbb\dotsc b$$$), then it's clear that $$$\text{max}(a_1,\text{reverse}(a_1))$$$ will just be $$$bbbbbbbabbb$$$, which is definitely far from the smallest we can do.
Seeing that we want to minimize the worst that we can do, it makes sense to place our $$$a$$$ smack dab in the middle, so that no matter whether the string is reversed, it won't be significantly worse than our original. $$$f(s_1) = \underbrace{bbbb\dotsc}_{\lceil{\tfrac{s_1\text{.size()} - 1}{2}}\rceil} \underbrace{a}_{1} \underbrace{bbbb\dotsc}_{s_1\text{.size()} - 1 - \lceil{\tfrac{s_1\text{.size()} - 1}{2}}\rceil}$$$
195387468
If you sorted the string $$$s$$$ then it should be $$$c_0 < c_1$$$ instead of the other way around. Thanks for the explanation.
Turns out H is just basic dynamic programming over a tree's edges in $$$O(N \cdot 3^K)$$$. For each edge with direction, which defines a subtree, we find the number of ways to assign a subset of the $$$K$$$ operations to some edges in its subtree, then we find the number of ways to assign all $$$K$$$ operations for each possible root of the final subtree. Merging two such DP rows for two edges from the same vertex takes $$$O(3^K)$$$, and if we want to assign an operation to a specific edge, it just has to come after all operations "below" it, so accounting for that takes $$$O(K \cdot 2^K)$$$.
Auto comment: topic has been updated by subscriber (previous revision, new revision, compare).
Since F was tagged with flows, can someone explain their flows solution? Curious which insights from the editorial solution (if any) are needed to make it work.
(I'm sorry that you're receiving notifications for this reply) Is there any way to follow a comment thread in CF? It'll really help if I could get notified if someone replies with a flow idea to this comment thread. I had to visit this comment a few times today checking for updates, and it's a bit inconvenient. I know I can mark this comment as a favorite, but I'm not sure if that'll notify me of any new updates.
Can someone help where did my code/logic go wrong in D1 submission 195189579
Is $$$sz_v$$$ in solution H means the size of the subtree after removing parts appeared in current mask? If it stands for the size of the subtree, then there could be some operation-valid edges missed(consider this case: edges:{{1, 2}, {1, 4}, {2, 3}, {4, 5}, {5, 6}}, s:{5, 4, 2}, where edge{1, 4} can be removed as operation 3, yet neither $$$n - sz_4$$$ nor $$$sz_4$$$ is 2)
Turns out it is(at least it can be).
Code in Java: 196355197
Submission1 Submission2
Can someone explain the difference in the complexity of the two codes? Thanks.
In problem D1 , I've made several submissions but all of them received TLE and here is one of them TLE.
But when I just changed the variable MLong from (2**63-1) to (2**62-1) , it was accepted .
I usually make MLong assigned to (2**63-1) since it's equivalent to sys.maxsize but I dont't know why it gives TLE .
Is that because of using of Big integers in python or another issue ?
Apologies for the necropost, but in case you still want to know, it was because there were some points in the code where the 2**63-1 limit was temporarily exceeded (i.e. by dp+hot and dp+cold). Changing 2**63-1 to 2**63-1-10**9 works, while changing it to 2**63-10**9 does not.
This addition overflow issue is also why many coders choose their "infinities" to be less than half the maximum value.
I got the answer from conqueror_of_tourist. Anyway , Thank you bro and I appreciate it :)
Ugly alternative solution to problem F (but easier to prove?):
So, you can iterate over the number of moves of both types applied to the block $$$[b+1, 2b-1]$$$, and the rest is uniquely determined.
AC submission: 206143039
It seems that everyone has a different solution to D2. Here's mine:
First, we assume every program runs "cold". We sum cold[a[i]] over all 1 <= i <= n and save the sum in ans.
Then get rid of all adjacent programs as they can be treated as a single unit. EX:
[1, 2, 2, 3] is the same as [1, 2, 3] and we subtract (cold[2] — hot[2]) from our sum.
Now we define dp[i][0] as the maximum we can cut off our current answer given that program i was not executed "hotly", and dp[i][1] the maximum we can cut off our current answer given that i was executed "hotly".
We know that if program i is executed hotly, there must be a CPU that has not been used since the last time a[i] occurred. Define occ[a[i]] as the last occurrence of a[i] (we can update this as we iterate through n).
My solution:
let prv = occ[a[i]],
dp[i][0] = max(dp[i - 1][1], dp[i - 1][0])
anddp[i][1] = max(dp[prv][1], dp[prv + 1][1], dp[prv][0]) + (cold[a[i]] - hot[a[i]])
Then, our answer is
(ans - max(dp[n][0], dp[n][1]))
whereans
is the sum ofcold[a[i]]
over the array a.The reasoning for
dp[i][0]
relatively straightforward.dp[i][1]
was reasoned as follows:For
i
to be hot, the programocc[a[i]]
must have been the last program run on cpu 1 or 2. Thus, any program from occ[a[i]] to i (inclusive) cannot have been hot with the exception of occ[a[i]] + 1.For example, consider
[1, 3, 4, 2, 3, 4, 2] and we are on i = 7 (1-indexed), a[i] = 2. If we map the programs run on each CPU up to this point, we can get the following:
CPU 1: 1, 3, 4, 2
CPU 2: 3, 4.
Notice that no matter how you organize the program order, there is no possible way for program 6 (a[i] = 4] to be executed "hotly" if program 7 is executed hotly. However, program 5 may be run hotly since it is right after the previous execution of program 2. Consider:
CPU 1: 1, 3, 3, 4
CPU 2: 4, 2,
As you can see, program 5 was run hotly. We can generalize and say that if we decide program
i
will run hotly, we can either make programocc[a[i]]
run hotly,occ[a[i]] + 1
run hotly, or justi
. We execute our DP and print our answer.solution link: 221519230
How should one come up with a solution for B?
What should be the Thinking Process?
I think C would easily find a place above 2000.
b can be solved with log(max(a[i]))*nlogn