Hello Codeforces!
On Feb/28/2023 17:35 (Moscow time) Educational Codeforces Round 144 (Rated for Div. 2) will start.
Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.
This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest, you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.
You will be given 6 or 7 problems and 2 hours to solve them.
The problems were invented and prepared by Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also, huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.
Good luck to all the participants!
UPD: Editorial is out
Good luck everyone!
Generally, I like educational rounds but...
Worst Contest I Have Ever Seen!..
Worst Contest I Have Ever Seen!..
Worst Contribution Voters I Have Ever Seen!..
turkish.. hmmm... maybe the earthquake is responsible :(
...Said 10555th of last Div3 xD
Note that you do not have any right to underestimate or make fun with an event which killed more than 45k people!.. ;( Also, stop racism...
Hope problem 'C' of this contest would be easy and not like the previous round.
I agree, at least without trash problems...
didn't age well
hope this contest will make me expert
:(
even I lost everything which I gained after solving hard problem C from previous 2 contest
Yes i saw, it's okay bro. It doesn't effect your skills. The learning here will help u become CM one day :)
BTW the cat in vovuh's profile in cute (◠‿◠)
I'll try to perform my best in this contest last 3 contests didn't go my way
:(
Today is my birthday. I hope that in this round I will get good deltas.
Happy birthday liar :) Today isn't your bithday)
lol
Hopefully back to master, been a hardstuck purple for ages now
yesss, [user:blitzage] orz
all the best, ig it's possible now
I hope for really good problems and good pastime in this contest!
Its better to skip Educational Rounds
ur highest rating was in educational round
Why are there so few people take part in this time?
are you from China and are you really girl?
hope to get a big delta:)
And positive too x )
Was this round unrated?
No, it was rated I think, the rating updates a little late in codeforces educational rounds.
congo
Hope this is my CM promotion contest): (for the third time LOL)
Didn't age well:(
So sad , I hate letter K now !
You should use a comment //don't use letter k instead of u
Why are so few people participating?
continuous contests may have tired everyone
How can problem C be solved? Is it a DP problem? I figured out how to get the length but am stuck on counting the number of them. I also can't imagine that number of sets having maximum size being very large, is my intuition off?
me 2
Hint: In the optimal set, every next element is a multiple of the current one.
I knew that but I don't still know how to solve it.
Well because of that the maximum length is (maximum number of times you can multiply l by 2 while its less than or equal to r) + 1. Also because of this, if you multiply by anything greater than 3, the length will of course be less than maximum. So then you are just multiplying by 2 and 3 the maximum length # of times. Simply fix the number of times you multiply by 2 or 3 and binary search for largest number that we can multiply by that.
There is no need to use binary search to find largest number that we can multipy by that .we can just use r/2/2/2.../2/3 that is the largest number,and the number of above 2 is before we cauculate;
Ah yes you're right
size of maximum subset is log2(r — l) + 1
to calculate count subset u need to calculate sum (1) (2), where:
(1) count of i, l <= i, that i * 2^(sz-1) <= r
(2) count of i, l <= i, that i * 2^(sz-2)*3 <= r, and multiply by (sz-1) (count of take one number from sz — 1 numbers)
Isn't it log2(r / l) + 1?
Yes, something like that. I just made a mistake :)
It's not a DP problem. For a certain length there can only be some 2 and some 3 as factor, for each number of 3 count the number of valid left boundary for that. Should be fast enough if you pre calculate the combination result.
The set will have this form : $$$[x, 2*x, 4*x, ...]$$$ or $$$[x, 3*x, 6*x, ...]$$$. Note that we can only multiply by 3 at most once, because $$$[x, 3*x, 9*x]$$$ can be replaced by $$$[x, 2*x, 4*x, 8*x]$$$
Now we will find some $$$x, y$$$ such that for any set that has the lowest number in $$$[l,x]$$$ we can afford to multiple by 3 once, and set having lowest number in $$$[x,y]$$$ can only multiple by 2
Then the answer is $$$(x-l+1)*maxsize + (y-x)$$$
the maximum length is 1+m, where m is the max value where $$$2^m \cdot l \leq r$$$. Given a set $$$S={ a_0, a_1,\cdots, a_m}$$$, with $$$b_i=a_i/a_{i-1}$$$, one can show that $$$B={b_1,\cdots, b_m}$$$ has only 2s, or exactly one 3( and the remaining values 2). If B has only 2s, one can choose all $$$a_0$$$ in the rank $$$[l, r/2^m]$$$, and if B has exactly one 3, you can chose $$$a_0$$$ in the range $$$[l, r/(2^{m-1}\cdot 3)]$$$, if this range is valid, and the position of 3 in the rank $$$[1,\cdots, k]$$$.
The answer is: $$$(r/2^m - l + 1) + (2^{m-1}\cdot 3 \leq r/l) * (r/(2^{m-1}\cdot 3) - l + 1) * m$$$
First of all let's calcualate the max length. Notice that it can be achieved in a such way: x 2x 4x 8x and so on. So it can be easily calculated in log(n) time. Now lets find out how all sequences of this length look like, for example for l=4, r=100:
So its not optimal to perform any kind of operation except *2 and *3 in this sequence, because if you do *4, you can replace it with *2 *2 and get sequence with higher lenght. Also we dont care about in what order they were performed since multiplication is a communicative operation. Now we can fix number of *3 operations, calculate total number of seq with this count of *3 operation: C(numberof(*3), maxsize) and then find from what numbers they can start.
why do we only consider 2, 3? there's might be multiple of 5:
like set{5,25} and 7 like {7, 49, ..}, and multiple of prime numbers within the range l, r
Is it true or i missed understood ?
If we can multiply by 5 it means we can multiply by 2 atleast 2 times as 2*2<5 so multiplying by 5 will never gives the biggest set size.
I got the logic, and my code is working for first 3 examples, but for the case 4 100, shouldnt it be 5 3 instead of 5 7?
you dont count these 4:
4 8 16 32 96
4 8 16 48 96
4 8 24 48 96
4 12 24 48 96
-12 in A... Yay
in Problem A the pattern of BF string repeats so just set the BF string as
"FBFFBFFBFBFFBFFBFBFFBFFBFBFFBFFBFBFFBFFBFBFFBFFBFBFFB"
and compare every substring of lengthk
to get the answerIt doesn't even need to be that long. The string repeats every 8 characters, and the input string is always at most length 10, so even if the input string begins at the 8th character, it should end on the 17th character at the latest. Therefore, a length-17 string suffices, i.e.
FBFBFFBFFBFBFFBFF
Short Python Submission: 195354083
That might be the case, but overoptimizing can sometimes lead to issues, for example, I overkilled with 200 on A, but for some reason, tried doing away with 2*n memory on D and wasted a good half an hour, which could have otherwise been saved.
should BFB output "YES" or "NO". If we just consider a substring of the larger FB string then the answer is YES. But there a no valid L and R for which the string formed would be exactly BFB. The question is a little contradictory in this edge case.
YES
$$$\ell = 8, r = 10$$$
There is no contradiction. Note that $$$\ell$$$ and $$$r$$$ are indices of the FB-string; they don't correspond to any particular values that generated characters.
Since the second number can be very large, print it modulo 998244353
First time this is a misleading information in CodeForces for me.
good think that's what happend cause i forget to modulo it :>
In problem C example 4, (input -> 4 100), what are the 7 arrays which satisfy the constraints? I got only 3.
I totally thought that my "perfectly correct solution" is going to get WA
Well that C was a bit misleading with that modulo lol
Problem C is kind of similar to https://codeforces.net/contest/414/problem/B
Weird contest, managed to solve D easily but failed last minute submission on C xD
Can we considering move the contest time to sometimes when Indians couldn't participate? Like almost half (or even more) of the indian accounts ever do is waiting for paid solutions to get out and cheat during contests.
This will also allow the US participants to participate. The start time in the US east coast is 9:30am and 6:30 am in the US west coast. The contests will have a lot more high quality participants rather than just a bunch of Indian cheaters.
I bet there are cheaters in US too. Quit your racism and focus on "high quality questions" rather than the "high quality participants" (many Indians too, will be counted as high quality participants as a matter of fact). Don't get salty if you are not able to get positive delta.
guess how many indian cheaters there are in a contest on average? A recent contest on leetcode had 500-1000 cheater on a single questions, which were leaked on telegram where the majority of the members were indians.
It's the same shit here if not worse
deleted
deleted
deleted
deleted
deleted
deleted
deleted
deleted
deleted
deleted
deleted
deleted
deleted
deleted
deleted
deleted
deleted
deleted
Same here in Bangladesh, CF rating helps a lot getting shortlisted for job interviews. I still don't get it why people cheat in contests tho. I practice CP partially to boost my confidence in job interviews, at least on the technical interviews. And cheating is only going to reduce my confidence in the long run
-7 on A. Sucked all the energy out of me and didn't feel like even trying B or C. Newbie here I come.
Same but solved B and C too
Were we supposed to do D with an O(nk) DP solution? If so, Python gave me TLE. I really need to learn C++ lol.
I solved it with an O(n) solution, could still fail system test though
Interesting! With the bound of 20 on k I assumed an O(nk) solution was what they had in mind. I'll try this problem more after the contest.
My O(nk^2) solution got accepted. C++ lol
I think they meant $$$O(n)$$$, since $$$k$$$ is so small it can effectively be treated as a constant. The problem gets a lot harder if $$$k$$$ has high constraints.
check my submission 195331445
it's O(n)
tell me if it's wrong
It's probably correct, but I still feel like approaches that exploit the small constraints on $$$k$$$ are simpler than approaches whose runtime is independent of $$$k$$$.
My approach was to first try every possible subarray length of size 1 to k first (everything in the subarray gets boosted). After that, I considered subarrays of length $$$> k$$$ by reducing all values by $$$x$$$, computing the largest subarray sum, and elevating the sum by $$$2xk$$$ to account for $$$k$$$ of the values getting an addition instead of a subtraction.
This has $$$O(nk)$$$ time complexity, so raising $$$k$$$'s upper bound can cause it to fail, thus making the problem harder.
orz
Slept over and woke up right before the contest ended... fortunately I'm unrated.
I've misunderstood statement of D that I must modify k consecutive elements, and I wrote a solution by segment tree. However it's only a dp problem (with annoying corner case for x<0).
for the subarray's length <= n-k , it can be solve by just searching the maximun subarray sum and plus the length*(-x)
for the length > n-k , just search all possibility from n-k+1 to n .(k<=20)
I don't think $$$x<0$$$ case is annoying. You can observe that when $$$x<0$$$, you should add $$$x$$$ to some prefix(say $$$p$$$) and suffix(say $$$s$$$) such that $$$|p|+|s|=k$$$, and subtract $$$x$$$ from remaining elements.
Now you can find max subarray in $$$O(n)$$$ using simple $$$dp$$$.
You have only $$$k$$$ options for $$$|p|$$$. Thus time complexity is $$$O(n \cdot k)$$$.
One of the few rounds where B felt far more easier than A. Question A just didn't made any sense and went over my head !!
How to solve D
Solution for D:
This problem can still be solved even under the constraint of $$$0\leq k \leq n$$$.
If $$$x<0$$$,do:$$$x:=-x,k:=n-k$$$.
If $$$x \geq 0$$$,we notice it is always optimal to use the "+x" operation for consecutive $$$k$$$ numbers(use proof by contradiction).
Next, we need to get the max-sub-segment sum of these sequences:
$$$a_1+x,a_2+x,...,a_k+x,a_{k+1}-x,...,a_n-x$$$;
$$$a_1- x,a_2+x,...,a_k+x,a_{k+1}+x,...,a_n-x$$$;
...
$$$a_1- x,a_2 -x,...,a_{n-k}-x,a_{n-k+1}+x,...,a_n+x$$$.
We can use a segment tree.Maintain a segment tree supporting the following operations:
Single point modification
Query max-sub-segment sum
thanks, can you please tell a resource to learn segment trees?
This course is really good. You can enroll yourself here.
Thanks
How do you prove this by contradiction?
Suppose the optimal solution is $$$...[a_i+x,a_{i+1}-x,a_{i+2}+x,a_{i+3}-x,a_{i+4}+x]...$$$
Construct $$$...[a_i+x,a_{i+1}+x,a_{i+2}+x,a_{i+3}-x,a_{i+4}-x]...$$$,the answer won't get worse.
Worst C ever.
perhaps someone solved A in a difficult way.
here is how I solved that. It's really easy and you don't need to debug.
How do this work? I don’t understand what the ~ operator is doing here
~x
meansx != -1
if t can't be found in s, the function will return
-1
.Generally I like educational rounds, but this is the worst contest in the entire fucking century
Very nice contest! Congrats to the authors! I really enjoyed A-D, but didn't come up with one solution for D! Can anyone tell his solution?
how to do problem C?
First of all, the maximum size is k + 1, where k is the maximum number such that l * 2 ^ k <= r. Now i want to see what is the maximum number val_left_2 >=l, for which we have val_left * 2 ^ k <= r. This can be done with binary search or math. We have to observe that we can use multiplication by 3 or 2 from the previous number that is in the set, because for numbers greater or equal than 4 you decrease automatically the size of the maximum set, because you use in one operation at least 2 multiplication by 2. We alse have to observe that we can use multiplication by 3 just one time, because if we use 2 times, 3 * 3 = 9, and 2 ^ 3 = 8 < 9, so we also decrease the size of the maximum set. We have to find again using bynary search or math what is the greatest number val_left_3 >= l such that multiplying it just one time by 3 and after that just only by 2, the set has the same size. Suppose the maximum size is k. For numbers that we can multiply by 3 we have k — 1 possible answers, because we can use multiplication with 3 once time in position 2, 3, .. k. Suppose that we have the following example: l = 1, r = 12. We have k = 3(1 * 2 ^ 3 <= 12), so the size is 4. Now we can have the following sets: (1, 3, 6, 12), (1, 2, 6, 12), (1, 2, 4, 12). See that we chose to multiply by 3 at each set the number on the second, third, or fourth position. So the final answer is: (val_left_2 — l + 1) + (k — 1) * (val_left_3 — l + 1). I hope that you understand!
Solution for D:
This problem can still be solved even under the constraint of $$$0\leq k \leq n$$$.
If $$$x<0$$$,do:$$$x:=-x,k:=n-k$$$.
If $$$x \geq 0$$$,we notice it is always optimal to use the "+x" operation for consecutive $$$k$$$ numbers(use proof by contradiction).
Next, we need to get the max-sub-segment sum of these sequences:
$$$a_1+x,a_2+x,...,a_k+x,a_{k+1}-x,...,a_n-x$$$;
$$$a_1- x,a_2+x,...,a_k+x,a_{k+1}+x,...,a_n-x$$$;
...
$$$a_1- x,a_2 -x,...,a_{n-k}-x,a_{n-k+1}+x,...,a_n+x$$$.
We can use a segment tree.Maintain a segment tree supporting the following operations:
Single point modification
Query max-sub-segment sum
I did like that, but I didn't get Accepted :(
upd: I know why i didn't get AC and I pass it now.
there are a few obvious mistakes.
I forgot to reduce the value in the positions out of $$$[i, i + k - 1]$$$
I didn't ask for the max-sub-segment sum of $$$[1, n]$$$, $$$[i, i + k - 1]$$$ instead.
silly me!!
Maybe you didn't do $$$x:=−x,k:=n−k$$$ when $$$x<0$$$
I did it. I chose the maximum answer between the two situations.
Segment tree is overkill, you can replace it with pref/suff maximums.
maybe that's why $$$k\leq \min(20, n)$$$.
It seems that you can make $$$k\leq n$$$ with a segment tree :)
I thought of the same idea but got confused because of the low constraint on K
code for the mentioned idea
Fix the link,
It should be https://codeforces.net/contest/1796/submission/195442442 Thanks a lot for your implementation
fixed.
you're welcome <3
In E, I solved the problem when the root was fixed. Can anyone tell me how to choose root optimally?
I tried to choose the leaf with a minimum distance to some other leaf, but it didn't work.
You probably can't choose root and need make rerooting (when you calculate dp with fixed root and then recalculate for every root)
In my solution i fixed k with binsearch and made dp with rerooting
Got 5 wrong answer on C and wasted more than an hour over a stupid if statement.
Can someone help me figure out why TLE for C, feels like the order is fine.
https://codeforces.net/contest/1796/submission/195350573
Your time complexity is O(t(r-l)), notice that there could be a lot of test cases
ohh thanks, do you know how many operations per second we can do in codeforces.
Generally, with fast I/O and such, you should be able to handle about $$$10^8$$$ operations per second, but most standard solutions should fall at roughly $$$10^7$$$ operations or less. If you roughly estimate your code as performing $$$10^7$$$ operations, then it should be fine, but if you estimate it at $$$10^8$$$, then it's almost certainly slower than the intended solution and it might end up failing, but it also might actually pass, so it's worth submitting if you can't come up with any improvements.
If i do binary search between l and r then it should be able to pass ig. thanks a lot.
Was definitely not an educational contest I liked the questions tho
I think that the problems were easy(was able to view only A and B), solved A but messed up in B probably some stupid edge case.
When can I able to see the failed test cases?
My worst performance ever. I didnt hate the contest but man problem A got me. RIP
Why NlogN solutions were not allowed for 'C' ? My solution with TLE :- N*log N DP sol
20000 testcases?...
They should have then given 1sec allowed time limit . I saw top solutions can do in O(1) with some formulae which will be enough to run in 1 sec. I got misleaded with time limit and limit on N. either they should have increased 'r' to 1e9 or decresed time to 1 sec.
I don't know ,seems like I am frustrated by TLE submissions .Don't mind.
I understand, but the general thing is to check whether statement says something about limit of sum of n (or something like this) or not. Last case means that you have to come up with something like O(log n) for test case (in this particular problem). Nevertheless, sad :(
You need to do it in LogN, because of the number of test cases. I also suspected whether there is a limit on the sum of (R-L+1) over all cases or not, so I asked the judges a question. There wasn't any
.
a abcd
should give NO but in your case it will givea*
which I think is wronga abcd
is YES. An asterisk can be replaced by an empty stringSounds working, did you implement something wrong?
you are right. Are you checking for when first and last letters don't match and lengths of a or b is one. then answer should be no.
Some hints how to solve B?
If the first letters match, we can just form the template with first letter and asterisk.
If the last letters match, we can just form the template with asterisk and last letter.
Beyond that, we need to make sure a substring of length at least 2 matches between both strings. If we don't have a matching substring of length 2, the answer is NO (alternating between asterisk and non-asterisk won't work, since there are more asterisks than non-asterisks then). But if we do have a matching substring of length 2, then we can simply construct a template as asterisk, two-length substring, asterisk (equal number of asterisks and non-asterisks so it counts).
Checking whether the two strings have a matching length-2 substring can be done by simply storing all length-2 substrings of the first string in a set/map (or an array of size 26*26) and then retrieving the length-2 substrings of the second string to check if any of them were found in the first one.
What's an example where the answer is 2 for problem E?
1-2 2-3 3-4 4-5 3-6
for Problem C my solution was looping from [l,r] but it was giving TLE on test 3. I supposed my solution should have passed the constraints of 1<=l<=r<=1e6. Can anyone brief on how to predict approximate time complexity based on these constraints.
There are 2e5 testcases for 2 seconds. For each case, expected correct time is O(1)
correction: it's O(logn) not O(1)
C destroyed me :( How to get total number of possible sets ????? ^_^
Say the smallest number in the set is a. Then all numbers in the largest set are of the form a*(2^x) or a*3*(2^x). Use binary search to find the answer.
Thanks used your idea, actually we can do without binary search Here's my concise code
base l, l *2, l * 2 * 2, l * 2 * 2 * 2, .....
sometimes it is possible to change one of * 2 to 3. But not two of them, because * 3 * 3 > * 2 * 2 2, so if you can do * 3 * 3 and still be <= r you can change them to * 2 * 2 * 2 and increase amount of numbers. Same with * (>= 4)
first number in base is l, last is l * 2^k. We want to find max l' such that l' * 2^k <= r
it is r / 2^k, so l, l + 1, ..., r / 2k is good
same if *2 -> *3, but also * (cnt — 1) because we can chose which *2 to change
Not sure why D had k<=20, you could easily solve it in O(N log N).
First, if x<0, then make x=-x and k= n-k. The problem stays the same.
There are 3 cases.
The optimal subarray is nothing (0).
The optimal subarray has length <=k. For this case, we add X to every element and use a sliding window of length K to find the maximum prefix sum with <=k elements. This runs in O(NlogN)
The optimal subarray has length >k. We subtract X from every element and use modified Kadane's to find the largest subarray sum. Then, we add 2*k*x to this value to account for the k elements that we can add X to. This runs in O(N).
Just take the max of these valeus to get the answer
EDIT: I saw another solution solving k<=n, but it used Segment Tree. this solves it with elementary methods.
Could you explain your 2nd case ? If $$$x < 0$$$ then $$$k$$$ can be very big, so the naive $$$O(n*k)$$$ doesn't work. I'm not familiar with the $$$O(nlogn)$$$ technique
If x<0, then do the thing I described in the beginning (set x = -x, k = n-k).
Then we can use a sliding window to compute the answer, as follows:
A pseudo code is as follows:
if you have any other questions, lmk.
I read your submission and got it thank you
Can Somebody can say what could be the test case where my solution get failed in Problem A
https://codeforces.net/contest/1796/submission/195295985
$$$BFFBFFBFBF$$$
You need to repeat that string more times, as the BF-string is the repeat of $$$FBFFBFFB$$$
Problem D can be solved in $$$O(n\log(k))$$$(or $$$O(n)$$$).
Consider two cases of interval length $$$len$$$ respectively:
$$$len\le k$$$: the answer will be $$$\max(Sum(r)-Sum(l-1)+(r-(l-1))*x)$$$. We can calculate $$$F(r)-min(F(l-1))$$$ for every $$$r$$$ where $$$r-k< l \le r$$$ and $$$F(i)=Sum(i)+i*x$$$. This can be solved in $$$O(n*\log k)$$$ by using
multiset
(or usingmonotone queue
in $$$O(n)$$$).$$$len>k$$$: the answer will be $$$\max(Sum(r)-Sum(l)+k*x-(r-(l-1)-k)*x)$$$. We can calculate $$$G(r)-min(G(l-1))+2*k*x$$$ for every $$$r$$$ where $$$l \le r-k$$$ and $$$G(i)=Sum(i)-i*x$$$. This is easy to solved.
Here is the code:
$$$O(n)$$$ is also possible by using monotone queue
Thank you for the approach, learned something new :)
If you don’t mind, could you tell me the extension you use to display date-time and author?
cf-tool
Since the second number can be very large, print it modulo 998244353....lol
Can the answer to question C be greater than a billion?
The answer of 3*2*2*...is less than log(n).
OMG the statement in C confused me a lot.. they said that answer can be very large TT..
is it a kind of mistake although it's one hundred percent on purpose?
it can't be really large but it says it can be.
Nope. $$$2^{20}$$$ exceeds $$$10^6$$$, so the size won't exceed 20, and you're allowed at most one 3 (three 2s are objectively superior to two 3s, two 2s are objectively superior to any number greater than 3). There are at most $$$10^6/2 = 5(10^5)$$$ possible starting values, so that's already an upper bound of $$$20 \times 5(10^5) = 10^7$$$. This is an incredibly generous upper bound, since having a high number of starting values means the sequences are even shorter, and a good chunk of those starting values won't even be able to accommodate a single 3.
any idea why this submission for D gives a TLE? Submission
Help appreciated.
when x<0, k becomes n-k,and O(n*k) becomes O(n^2)
worst c. f*cked up
In B, I generated all substrings of a and b, stored them in map and checked for the common substring of max length. If its length >=2 then ans will be (string). But this gave TLE. The whole process of map and substring generation won't exceed n^2 where n is length of a which is <=50. Can anyone help me with this? Here's the submission https://codeforces.net/contest/1796/submission/195333589 I don't get how it is giving TLE, fucked up the entire contest. Newbie here I am
Generating all the substrings actually takes O(N * N * N). Imagine there are N * N substrings in total and each one takes O(N) time to copy.
But inserting in a map takes log(n) time.
It's not true for string type. I didn't read your entire code, but something like set.insert(s) where s is a string makes me concern. When insert() get called, I am pretty sure the parameter string get copied first which takes linear time. Later pushing it down to a ordered structure requires string comparison potentially takes linear time per operation. Overall I believe the time complexity for inserting a string to the set is O(N + N * logN) where N is the length of the string.
seeing that amount of hate towards problem C makes me disappointed. so want to remind everyone about this recent discussion about criticism of problems in comments after contest. please read it if you didnt before
During contest I thought task C was to count the no. of longest paths in a DAG, got TLE and couldn't think of any other way. Skipping C to solve D would have been a better decision. Also, there is no reason for k to be small, my solution works in O(nlgn). https://codeforces.net/contest/1796/submission/195367954
As I understand it, $$$k$$$ is kept small to allow for a certain class of solutions to pass as well. Since this is an educational contest, that probably makes sense from the aurbors' perspective.
can someone help me pls?
https://codeforces.net/contest/1796/submission/195364034
screencast with commentary
Thank you for educational videos! But the link doesn't work because it doesn't start with http://
Thank you, fixed.
How to solve F?
Good luck everyone!
195352766 For problem A. Hi can someone help with figure out why my code is giving a wrong answer on test 2. Since it is 144th token in test 2 out of 2046 test cases where the code outputs the wrong answer I am unable to see exactly where I might have a logical error. From all my thinking upto now the error with my code could be the time complexity but since it's not giving me a TLE so that beats me too. Any help would be really great. Thanks.
Counterexample: "BFB", your code output "No" but thats wrong. FB string starts with: "FBFFBFFBFBFFBFFBFBFFBFFB", and fb[7]-fb[9] is "BFB". Problem of your code is that for j%15==0 you add two letter in a row and dont check a substring with only one added letter. I advice to generate fb-string once before solve cycle and just search given substring in fb That will fix this error and also will help with speed.
Can someone explain me the dp approach for the Problem D. Thank you in advance..
The problems are cool. Love this contest!
when will the rating be changed?
system testing just completed.Just wait for an hour
I am very excited about this contest rating because I think I will become Pupil from Newbie.
Me too
Joy of Getting AC in last minute >>>>>
D is so good that it gave me headache :)
Seriously, I figured out the array needs to be pre processed(minus x), but the prefix complement subtraction is beyond my imagination. Is it something easy to think of or just a common idea? Hopefully not the former one
ps. it sounds way easier as I write it down that way :(
I personally found the idea to be more intuitive when you think of it as querying a ranged data structure. Once it's down to that, it's still probably not very easy. I remember though that I saw a video on youtube, maybe 2022/21, where a Red solved some question that used the idea, basically, each node in the segment tree would need to store 4 values, the sum of all elements under it, the maximum subarray sum, the maximum subarray sum (prefix) and (suffix), using these 4, you can create the required segment tree.
My submission Here,
st_s
stores the sum of all child elements,st_m
stores the maximum subarray sum,st_lm
stores the maximum subarray sum (prefix) andst_rm
stores the maximum subarray sum (suffix)Was this unrated?
Why did I not receive any rating for this contest?
Anyone, please tell
Well, I want to know it, too. The System Test is over.
If in any unfortunate scenario, a contest is actually unrated, it gets updated as such on the contest accouncement blog itself. I understand your emotion, I feel the same way, but please be patient, changes can sometimes take longer than expected.
When will the tutorial be uploaded ?
Problems are so nice just if we removed problem A
Thanks for good BCD !
If it had been k <= n in problem D, I would havent got 5 penalties for WA on test 2 (solved the problem in 9 minutes, trying to fix bugs for 30 minutes). Kind of an easy but annoying dp problem imo.
why no rating ,it's already 22hours
and i need the tutorial of Problem D
When will this contest be rated?
Regex solution for B: 195451488, Perl.
I joined the strings A and B into one string and regexed for:
X .* NEWLINE .* X
(dot = any symbol except NEWLINE).https://codeforces.net/contest/1796/submission/195318855 This code was hacked (TLE) and I missed the first place.
But I just submitted the same code again https://codeforces.net/contest/1796/submission/195453193 , then got AC (1606ms) .
It is sad to see this happen due to the blurring of judge speed by time of day :(
I participated in this contest and solved one problem but still didn't get any rating changes why? I'm a new to codeforces.
The rating will get updated in some time, for knowing about the expected rating change you could use chrome extension CF predictor
educational round rated slow, this time unusual slow ,but don't worry,just do something else ,you will recieve it later.
Excuse me, how could my solution of B get AC on the competition, despite it's wrong and didn't pass the rejudge? Unfortunately, i have no proofs, but yesterday it got accepted, and today it was rejudged and got WA on 1st test.
This solution: 195287792 (it's obviously wrong, but it passed all the tests yesterday)
Upd. the solution above is a little bit messy. Here is the same, but shorter one: 195464083.
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
when are updated ratings coming?
I finally reached Candidate Master :D
omedeto
if two people has cheated, both of them were skipped. I think if the rating changing is negative, they shouldn't be skipped.