Hello Codeforces!
On Oct/17/2022 17:35 (Moscow time) Educational Codeforces Round 137 (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 Ivan BledDest Androsov, Alex fcspartakm Frolov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.
The round is based on the Qualification stage of the Southern and Volga Russian Regional Contest. Thus, we kindly ask its participants to avoid participating in the round.
Good luck to all the participants!
UPD: Editorial is out
New Edu Contest writer! Wow.
3 consecutive days of contests!
3 days in a row of contests! The professor will miss me at university (^-^)
u shold pay attention in learn learn rather than code code
That's why you're blue.
As if you are in different color.
(Btw you forgot to tag your “wonderful” name)
Marinush I think you should stop learning to code at all and focus on learning how not to be a rude kid !
I think you should stop and focus on learning how not to be.
In taraclia we say: sa mor io frate
Marian Stefan, IOI2023
I try to learn more and code what I understand but still can't think with which I learned to solve problems. I don't know if I learn in wrong way or what?
Could you please give me some upvotes to make up for my poor contributions?
I hate you all
I hate you too.
mARINUSH!
Does it mean this problem set has been used in the regional contest offline already? How to avoid the problem leaking?
Someone Plz explain, does it mean that Southern and Volga Regional contestants will be in Top of Standings (As they have Seen and Know all of the problems) ? How are problem setters sure that there is no Editorial of the problems in Internet already ?
These 2 things are pretty enough to Ruin the competition for everyone.
Last round (the Div.3), a cheater (seemingly teaming with multiple people) solved 3 problems in 5 minutes, and then immediately got eradicated out of standings. Likewise, I believe a large amount of the concerned situation could be prevented too.
He submitted last 3 problems in 5 minutes, because he had no time to change them properly enough. I bet if he had 10 more minutes, he wouldn’t get caught. This does not explain why people can’t cheat and spread the solutions in this “contest”.
I guess its's a bit late to answer, but I meant 5 minutes in the beginning rather than at the end. And this should seem closer to a case of an early leak, so I said it's preventable.
BledDest, awoo, fcspartakm
Why it is said to avoid the contest, do they mean it seriously or it's a joke. Or the participants of Volga Russian Regional Contest are said to avoid the contest. Please clear anybody if you understand.
The participants of Volga Russian Regional Contest are said to avoid the contest.
Everytime while participating in Educational rounds !
Please ban my account and delete this comment, kthxbye :)
don't click the link!! https://noodlemagazine.com/watch/-203295556_456239121
nice
Another edu!
If i hack another solution is there a penalty for that?
All solutions are going to be retested with test data from successful hacks. So a successful hack influences the final standings by kicking off some solutions.
Codeforces at It's best mood. Three back to back contest.
M let's go
Hope I will solve 2-3 problems really quickly to become PUPIL
best of luck
No testers, No free upvotes!
Hope to reach expert.
Speedforces
Why there is no impact in the standings even after unchecking the show unofficial box??
I'm able to see a difference.
Huge gap between D and E, but nice round with classical C and good D. Thanks!
I'm surprised that suddenly a lot of people started to solve D as if it was a count down for them to go
Why there is no impact in the standings even after unchecking the show unofficial box?? Is this with me only or with you also??
It may be useful after system test. Useless now.
I don't know why they do this in Educational Rounds. You can choose to see only div2 contestants after the round or system testing I don't remember
For C, no lid can be moved more than once. But the sample doesn't show that.
F seems easier than it's supposed to be.
Interesting E.
It's written in the problem statement that you can't move the lid more than once
Yes. But I tried to solve quickly(to get back to Master)and missed it.
You Solved D! Nice.
yeah.. hint: you just need to claim that there won't be a lot of strings to check (maybe at most 100) since there is an equal probability of 0 and 1 at an index (what is the probability of getting a continuous substring of 1's?). If you prove (or claim) this and make some other simpler observations, you will solve it.
btw don't worry, I am not really a newbie
actually, checking only for 10 strings does the job
if it was possible to move more than once, the task turns into output the sum of the top k elements, this should have alerted you
Well you can only move it in one direction
Yes, you're right, I'm sorry. It's just that I read the condition wrong at first (I thought it was possible to move in both directions) and spent an extra half hour
Oh yikes!
It would have been nice If they mentioned in bold For C, no lid can be moved more than once.
agree with you
how to solve d?
First, identify the leftmost 1. The suffix from here has the longest bit length (excluding leading 0s) you can get, so this suffix should be your first substring (impossible to reach this bit length with any shorter substring).
Now, identify the first non-leading 0. Making this 0 into a 1 will always be better than any alternative where this 0 remains as a 0. But to make this into a 1, we need the second substring to start sometime before this 0 (otherwise, it would be too short to reach this 0). Therefore, the second substring must begin sometime between the first 1 and the first non-leading 0, and its length should be exactly enough that the first 1 in the second substring covers the first 0 of the first substring.
We can try every possible choice for the second substring, and pick the one with the largest result. The worst-case runtime is $$$O(n^2)$$$, BUT the problem states that the strings are generated randomly, so the expected number of 1s before the first non-leading 0 is in $$$O(1)$$$, so we're not likely to get a huge number of 1s before the first non-leading 0, leading to $$$O(n)$$$ expected runtime overall.
thanks
Video Solution for Problem D and Problem C.
Great round!!!
Can you tell me how to solve D?
Brute force solution works because of the given probability condition.
Can you show me some hint?
Your main concern would be, what if there are O(n) consecutive elements, which is not plausible since it is randomly generated datas.
There is fixed a $$$s_1$$$ which maximize the value and if you know then, there is only few choices for $$$s_2$$$ to maximize the value and you can brute force over all $$$s_2$$$ and see the best answer.
Does E requires some data structure or topic or is it ad-hoc?
I used a lazy propagation in segment tree
Can you explain your solution please?
Sry. I misread it. It was for F.
Sorry I thought you are saying F as it mentioned about segment tree with lazy propagation. For F, You could do it with some observations, by considering the operations done on last set to the first set.
Dynamic programming of the form $$$dp_x$$$ — the minimum amount of time required to deal exactly $$$x$$$ damage to the enemy so that the last shot was a double one (i. e. both lasers have just fired).
Why the last shot was double is optimal while calculating dp?
Did anyone else also thought that the lid can be moved more than once in Problem C :")
I did. And this mistake will cost me a massive loss of rating points.
i do not know what is the wrong with me i spend around 3 months studying and practicing and still newpi .can you tell me what should i do
i guess the problem is u have solved very less problems of higher rating (>=1200).
What about me Plz suggest something for me too.
u have done some problems of higher rating but still less.
If u have any doubts then do let me know.:)
Which red coder u suggest have best implementation
I follow jinagly and utkarsh gupta,but others are good as well.
It completely depends on you,like if u can understand their code then it is goood for u.
Utkarsh Gupta is not active these days .And Jiangly some times give and some times not when Jiangly does not give the contest then whom I have to follow. And also a one more query is that While Problem C is of some times 1600 /1700/1800 they are now out of my reach still I have to try them or not
see until u reach 1900 most of the problems just need basic dsa like stacks,queue,dfs and etc.somtimes segment tree.(if u r not good in theese then read it from usaco guide)
So if u r feeeling that problem c is out of reach just solve it by reading editorial or watching video editorials.(but u should solve it after every contest).
It is not that u only need to follow jiangly or ug u just need to see one or two good implementations of the problem it may be anyone.:)
just keep trying, somedays you will be pupil, maybe expert, cm, master,.. just keep trying.
Don't take it serious man. Just practice as much as you can and try to solve harder problems. Like if you want to reach pupil, solve problems with difficulty from 1300-1600. I have been newbie for 11 months but never left hope. Be courageous. Select some handles and while the contest, try to beat them. You will improve :) .
Best of luck,
Daniyal.
Any ideas for D?
One of subarrays is of course all array without leading zeroes. So check as second subarray only subarrays that have length of n — first 0 index after first 1. This don't give tle because that length can't be < n — 60 (chance is too small).
1) One of strings (s1) should be longest started with 1. It is unique and starting with the first 1 in the string
2) You want to cover zeroes in s1 from left to right with 1 in s2. It doesn't make sense to have leading zeros in s2. So we even know its length — it should start with 1 and this 1 should cover the first 0 in s1. Random guarantees a rapid decrease in the number of best candidates when processing more and more zeros. If some of them can cover another 0 — we leave only these as candidates and move on
How to solve problem F?
Solution for F:
First,use sweep line.Enumerate $$$x=0,1,...,3*10^5$$$,and record current segment set containing $$$x$$$.
Now let's calculate the number of operation schemes so that after operations,the segment set contain $$$x$$$.
($$$i.e.$$$ contribution of $$$x$$$)
Define clear operation $$$op_i S_{i+1}$$$ as:
$$$op_i==∪$$$ and $$$S_{i+1}$$$ contain $$$x$$$,or
$$$op_i==∩$$$ and $$$S_{i+1}$$$ not contain $$$x$$$.
Consider the last clear operation $$$op_i$$$,
for $$$op_1,...,op_{i-1}$$$,which do not affect the results,there're $$$3^{i-1}$$$ schemes.
for $$$op_{i+1},...,op_{n-1}$$$(contain $$$k=(n-1)-(i+1)+1$$$ number of operations),
if there is $$$S_j(i+2 \leq j \leq n)$$$ which contains $$$x$$$,there're valid $$$2^{k-1}$$$ schemes in total.
if there is not $$$S_j(i+2 \leq j \leq n)$$$ which contains $$$x$$$,there're valid $$$2^k$$$ schemes in total.
The total number is $$$3^{i-1}*2^{k-1}$$$ or $$$3^{i-1}*2^k$$$.
Enumerating the last clear operation $$$op_i$$$ costs $$$O(n^2)$$$.But we can optimize it using prefix sum trick,which costs $$$O(n)$$$.
There are two subproblems to solve here.
First, for each coordinate x determine which segments it belongs to. This is classic sweepline: loop over x, at x=l[i] turn on S[i], and x=r[i]+1 turn off S[i], then process x. Sort l[i], r[i]'s together with bits of information what to do as you encounter them, and iterate over this sorted list together with x.
The second problem then is: given a fixed coordinate x and bitmask S from previous step (indicating which segments contain x), calculate number of ways to put binary operators between S[0], S[1], ... S[n-1] so that the whole expression evaluates to 1. The final answer is the sum of this count for all x.
One obvious way to calculate that is with dp, maintain dp[pos][result] = number of ways to get 'result' after choosing operators and evaluating the expression up to S[pos]. It's a bit too slow due to constraints on n, but observe that dp[pos] (as a vector of 2 elements) depends only linearly on dp[pos-1] and S[pos], so you can actually express it as a matrix multiplication:
dp[pos] = dp[pos-1] * <some matrix>
, where there's one matrix M0 for S[i]=0 and another M1 for S[i]=1. You can calculate these transition matrices by hand or with a bit of code. The whole dp then is a product of matrices: initial state [0,1] or [1,0] depending on S[0], multiplied by M[S[1]] * ... * M[S[n-1]]. You can use segment tree to efficiently evaluate it and support updating matrixes in the middle of it, as S[i]'s are turned on and off during your sweepline.Actually, you probably don't even need matrices as this comment suggests, just focus on dp[pos][1] counts I guess. But it's a neat trick in general to know that if your dp transitions are linear, then you can speed it up by thinking of it as a matrix multiplication. For example, closed form derivation for fibonacci numbers starts from such matrix multiplication reformulation.
C: misread (I thought move can be arbitrary no of times and solved the hard version)
D: Also misread XOR instead of OR. In the last 5 min, were understood the mistake and then WA on 40 while 40 was the last case mentioned.
A worst contest -_-
Actually the version where you can move the lid multiple number of times is at least more classic than the current version (I also think it is easier but that's subjective)
In that other version you just insert elements from left to right in a priority queue and for each $$$1$$$ you extract the current maximum and add it.
However in the current version, you need to look for every substring of the form $$$011 \ldots 110$$$ and then take everything except the last element and the minimum of the other ones.
Agree ._.
For question D I keep failing test 40.
Idea is divide string into blocks of consecutive 1s and 0s. We know that one of the answer string would be the entire input string, and the other is the entire input string, and remove some of the number in the back to shift the 1s rightward.
Now we just calculate how many shift we should do. We will prioritize blocks of 10s that come first. at each block we can see the max remove we can do left and finally construct how many shift we did.
Dunno why i got test 40 wrong.
https://codeforces.net/contest/1743/submission/176780050
EDIT: nvm found the issue
Really A and B are suitable for edu round ? why are they wasting peoples time ? They can be kept in div4
It's important to always have some problems that are very easy to solve. It's not a div1 contest with limitations on user's lowest rating, everyone should be able to solve at least 1 problem. And also, for me, C was easier than A or B and took less time because I'm an idiot and tried using combinatorics in A instead of bruteforce ^D
What are you talking about, A was way way easier when solved through combinatorics. Look at my O(1) solution: https://codeforces.net/contest/1743/submission/176712399
Only basic high-school level pnc is used here.
I mean, idea of A is obvious, just wasted some time to remember something from combinatorics(Eben though was faster to write bruteforce without thinking), While C was straightforward for me and took 5 min^D.
I saw your submission for C, and I just want to say, please don't look at my submission for C (took me an hour xD)
Happens to the best!^D
A is supposed to be easy, even in Div2. If it's not too easy, many participants might quit if they don't solve it quickly, which can really skew over the ratings of those who participated, as well as the problem ratings. Please do not encourage problemsetters to make Div2A too hard.
I do agree that B is a bit easy for its position though.
Agree
How to solve E?
Tried brute-forcing (for all [i,j], where i is the number of shots taken by the gun with the greater reload time and j being the number of times the other laser was fired at the same time (in coordination to save s points), plus any extra shots, if required).
Also considered the bonus free shots I could possibly get in the waiting time between coordinated shots.
I am assuming the coordinated shots could have a more optimal arrangement than the one I was going with.
My WA 5 Solution.
https://codeforces.net/contest/1743/submission/176779463 Can anyone show me a test case where my code not works ``_?
debugmode() is working
[Deleted]
Hint : How to compute answer if string is 011111110?
FTL is a very nice game that exists in the real world
PLAY IT
upd:it's not expensive
Yeah, I was quite smiling when I read FTL :)
I tried to solve Problem C by BFS, ending with memory limit exceeded, which confused me a lot. Is it because there are too many staus to store in queue and set ?
I think I have solved the Problem D, however, it's always WA at the test 11 and I can't find any bugs of my code.
In all, I think I can do better in this edu. :(
Use spoilers for code.
Your comment is literally taking up 30% of the blog's scroll-space.
For Problem D, your mistake was in considering the left shift. A left shift does not form a valid substring. For example, consider the following test-case:
The answer should simply be 1100011111, where the second substring is the prefix without the last character (so it's equivalent to a right shift). But your code answers 1111111111, because it assumes the 1s on the right can be left-shifted to cover the 0s on the left, but there's no way to actually pick a valid substring that would cover all the 0s.
Is it intended in problem D, that you get penalty for wrong answer on test 2 and 3, but no penalty for wrong answer on test 1, even though they are all examples?
For example Vercingetorix had "wrong answer on test 1" twice, but got no penalty. I had "wrong answer on test 3" and got a penalty.
Wrong answer on test 1 = no penalty (the rules. the same for every problem)
Ok. Thank you
WA on TC1 has no additional penalty on any contest.
Educational rounds follow extended ICPC rules. Here you won't get a penalty for WA on test 1. You can read about it here: https://codeforces.net/blog/entry/105575?#comment-939387
But here in problem D, tests 1, 2 and 3 are all supposed to be "test 1".
Meaningless problem D
Can someone please share their thought process for easy permutation problems like A? I never bothered to learn because a pattern is usually observable but I was wondering the correct 'math' way to figure it out.
Each password is of the form XXYY. The number of ways to generate permutations of this is: 4! / (2! * 2!) = 6. Now, there are 10 numbers in your hand [0 — 9] and some are excluded. So the remaining numbers left are 10 — n. Let's call that size K. You need to pick 2 numbers from these remaining K numbers. The number of ways to do that is KC2 = K*(K-1)/2.
Therefore, your answer will be KC2 * 6 [Choosing 2 numbers from the available set, and generating permutations of them]
Thanks
Nice contest! D was the best problem ever! So original!
f**k Problem D
how tf there are so many AC on D? It's not that easy imo.
I just looked at D after not being able to participate due to other schedules.
now what the fuck is this
All the non-example tests are generated randomly,so it is nearly impossible to let your code get wrong answer in 40 test cases.
Well, I thought "weak pretests" was a funny joke. Turns out it could be even funnier
It is time for weak systests with hacks prohibited.
Tests are not weak, they are just random. These are different things
Could you please explain why checking only first 100 shifts work? Is it because getting the first 100 characters as 0's is not probable so we always get the best answer in the first 100 shifts?
probably because it is so unlikely to get a very long substring of zeroes.
My approach for C:
Let the given binary string be $$$s$$$.
If for current $$$i ( i \neq 0 )$$$ . If $$$s[i] = 0$$$ just continue.
Now if $$$s[i] = 1$$$ If $$$a[i-1] \ge a[i]$$$ then we swap ( $$$s[i-1] , s[i]$$$ )
But if $$$a[i-1] < a[i]$$$ and $$$s[i+1] = 1$$$ (if $$$i < n-1$$$) then check if $$$a[i-1] \ge a[i+1]$$$
Because it will result in an overall positive gain which is equal to $$$a[i-1]-a[i+1]$$$.
If it is then swap ( $$$s[i-1] , s[i+1]$$$ ) (what's happening first lid goes from $$$i \rightarrow i-1$$$ then from $$$ i+1 \rightarrow i$$$ ) else don't swap.
I am not getting where I am actually going wrong.
Submission Link: 176741104
You are only half right. Notice in your third condition, you explore a a different option.
Take example the string 0111. Your code considers, 011, 101, and you notice that 110, is also possible (swapping the first and third element). However, take a look at this string: 0111111. Your code will only consider, 1011111 and 1101111. However, these are also possible: 1110111, 1111011, 1111101, and 1111110. Basically, when you have one zero followed by n 1s, you can swap any of the 1s with the 0. But you only consider the first 2 1s.
c was a dp problem still 7000+ submission . cheating is ruining codeforces.it seems like all the cheaters came here from codechef
It could be done by greedy tho. Just by considering continuous segments of 1's. But dp solution shouldn't be really complicated in this case.
The problem has a greedy solution too. It seems that dp solutions are getting hacked now (Or Only Memoization one) ;)
I did C purely through greedy
I think if problem D was xor instead of or it will be more "Educational". Cause it will be a really nice application of using KMP.
or FFT :D
FFT is an over-kill here. But yeah FFT also works.
Can you please elaborate a bit
How to solve D? My idea is: Divide string into blocks of consecutive 1s and 0s. We know that one of the answer string would be the entire input string, and the other is the entire input string, and remove some of the number in the back to shift the 1s rightward.
But my sub failed test 40 so it's wrong. Why is this problem tagged probabilties?
The solution highly relies on randomness.
Problem C.Why my submission got TLE on test 4.my submission —->176765114.Thx for your help .I think my solution is O(n),but when n is equal to 200000,I got TLE.
Well, your logic needs extra 0 at the end of s.
So many people have used the same code surprisingly for problem C. Agreed it was pretty easy, but so many submissions is surprising to see. Most of them have similar logics, some of them changed their entire code from the previous incorrect attempts in a matter of minutes.
Submissions: 176764109, 176765007, 176759508, 176765416, 176764960 and so many more. MikeMirzayanov please look into this excessive plagiarism on problem C, and do the needful.
Do look into this and conduct a plag test, as there are hundreds of submissions with the exact same code, just with the variables changed. Removing 100s of such users from the leaderboard will be very good, especially for those with ranks>5000. Kindly look into this MikeMirzayanov
Wow problem D trolled me good this time. Bc test is randomly generated you won't get more some constant consecutive 1s or 0s.
This is totally BS, this problem should be in a trolling contest.
I want to cry. I would have never thought to extract that conclusion out of that detail. Everything bold is bold for a reason.
there is a huge gap between c and d that you know your contest ended after reading it and it was a matter of speed :(
Did not liked that problem set since it is observation based like other div2/div3. Edu round where and should be mostly implementation problems. Why else Edu rounds exist?
PLEASE ANYBODY SHOW ME MY ERROR
Try eliminating all ones that are not last in the sequence of ones after zeros. Then you shall see how to solve this in O(n). For example
10001111110110 = 10001010 (lits) 12221234342322 = 12224222 (mags)
How to solve A?
Why does this work:
std::cout << (10 - n) * (9 - n) * 3 << "\n";
https://www.statisticshowto.com/multinomial-coefficient/
There are 10 numbers b/w 0-9, you are given n numbers, remaining 10-n numbers you have to pair.
So, (10-n)*(10-n-1)/2 are the number of pairs. Then, multiply by 6 because 6 permutations.
The above is just the simplified version of this
Basically, it's just the same as kC2*6, 6 is the number of permutations when all the conditions are satisfied according to the question. Where k is (10-n), so, k*(k-1) is eventually (10-n)*(9-n) which explains the statement.
Same as my submission
Where can I report cheaters at codeforces?
For now I will leave it here, but if there is better place please let me know.
OrazB and OrazBeg Signed almost the same code for A — Password Problem.
Except that OrazBeg's answer had one difference.
If amount of testcases was 2 or 200 then it will print out trash. So it was certainly just something to pass system tests and not pass hacking tests.
OrazBeg's Answer
OrazB's Answer
Accusation relies on
- similar name
- Code is the same if we delete fragment with amount of testcases
- OrazBeg signed up 10 codes that differ only in newline characters just for other people to hack it.
- OrazB of course hacked OrazBeg 6 times.
Apologies Huehuehue277353
Actually, alter account is also a violation of the rule. But I don’t think you have a bad motive. Anyway, please keep this in mind.
Hacks are unrated in edu rounds
Bro, he is gaining 0 WA. Testing solution with alt account then submitting with main and hack alt in hacking phase to avoid plag.
These all seem to be hacked practice submissions after the contest. Is anyone actually using such main/alt trick in the real contest to dodge WA?
not really because he first submitted on normal account and 5 minutes later on his alt
edit. i was referring to techiehere but ssvb is right. i guess it was not even during the contest
I see, I am dumb. But creating alt is violating the rules too.
In problem D I am unable to understand how we can have output 11111 if we have 10110 as input, I am unable to find a substring which could give this or maybe I am to dumb to understand this :(
10110 1011 11111
We are doing the OR of the binary substrings so we start from right to left
Great D
thats what she said
how to D?
Is there an $$$O(n)$$$ solution for D? One that doesn't utilise the randomness of the test cases
i feel like using bitsets can pass the $$$O(n^2/w)$$$ (cuz TL is 4 secs). But u'll need to implement ur own comparison that is also avx fast.
Actually solution that uses randomness is also expected O(n), because expectation value of number of process is constant complexity.
Why is it that when I always comment and scroll down, what I write is already written?
Can someone explain to me the complexity analysis of D? I think the worst case will be when the first "10" we encounter is at n/2 (n is 1e6 for 20 cases). Now in this case we will have our loop running for n/2 * n/2 which will be 20*(1e12)/4. I thought C++ could only work up till 1e10 in overall complexity. So how is this working?
The worst case will never happen.
what does that mean?
It has extremely low chances to happen. Most likely, it will never happen.
Oh...this was the first question for me where the test cases were random. 1/(2^1e6) chances that someone got the case that I mentioned xD
This approach does have $$$O(n^2)$$$ worst-case runtime. However, the problem explicitly states (in bold, too) that the tests are generated randomly. Therefore, it is extremely unlikely that the first "10" will be so late. The expected runtime is in $$$O(n)$$$, and the chances of being unlucky enough to get a bad input that TLEs is extremely low and likely has not happened to anyone.
yup..got it Thanks!!!
Problem C wasted my 1 hour as i was shifting 1 left any number of times but we are allowed to shift it left only once.
Similar case here; I thought going to (i+1) was also possible :p
Will there be any system test for problem D? It says that there is only 40 test for this problem but I am not sure that's why I am asking right now.
No. Only $$$40$$$ tests
So cool E and F!
Any ideas for these? Would like to hear some hints
For F you can do it by calculating the probability that ith point is in the final set.
XOR sets x -> (1-x)
OR sets x -> 1
AND sets x -> x in the range and x -> 0 out of the range
So each operation does x -> 1/3(1-x + x + 1) = 2/3 in the range and x -> 2x/3 out of the range. This can be managed by segment tree. Final answer = sum of probabilities multipltied by 3^(n-1)
Why does 176804514 this solution pass and 176772722 this solution TLE. Time complexities seem to be same to me. Please help :(
Are there anyone think the problem B might be too easy for the contest div 2?
Is it possible to solve D if the randomness condition is removed?
Perhaps with hashing/KMP, or maybe with a bitset ($$$O(n^2)$$$, but a small constant)
Of course you can with some suffix structure.
Any code that proves idea?
In problem B Statement, it is given that "For example, the value of [2,1,4,3] is 3 since the subsegments [2,1], [1] and [2,1,4,3] are permutations."
But this is incorrect as for N = 4, the permutatation [3,1,4,2] gives minimum possible value as 2 instead of 3.
It said nowhere that $$$[2,1,4,3]$$$ is the answer :|
Will the DP solution of C fail(FT) as many of the DP solutions got (Hacked)TLE?
No it won't. Prolly all the solutions that got hacked were recursive-memoized and not iterative.
I think I saw a few iterative solutions also that got hacked, still was unable to understand why it got TLE.
Can you share the link to any of the hacked ones?
My solution got hacked
https://codeforces.net/contest/1743/submission/176742146
and when I asked the hacker about the reason he told me because of using memset function.
As I was using memset function on 4e5 size. So for 10^4 testcases there will be 10^4* 4*(10^5) operations which is TLE
I think many of them were doing memset(dp,-1,sizeof(dp) in the solve function which was causing TLE.
I used a vector. Thank god I escaped xD
MY CODE IS GIVING THE CORRECT ANSWER IN MY IDE. BUT THE SAME TEST CASE IS GIVING WRONG ANSWER WHILE SUBMITTING. PLEASE HELP ME OUT.
https://codeforces.net/contest/1743/submission/176773214
Is the time complexity reasonable in the first place?
How to solve problem D...... I am getting stuck in it
Just note that all the data is random, so you can just search for the s2 and find the max answer as this process is thought to be around O(logN)
Can you please elaborate the steps for finding string S2
Given string $$$S$$$ of length $$$n$$$. First trim all the left zeros from $$$S$$$ and call this $$$S1$$$. We are trimming the left zeros because they can never be flipped to 1.
Example: $$$S = 00110010110$$$
Then $$$\hspace{0.5cm} S1 = 110010110$$$
Next we will try to flip the remaining 0s in $$$S1$$$ from left most zero to right most zero and we will do this greedily since we need to maximize the binary value of $$$S1$$$.
Let $$$S2 = 0010110$$$, that is we trim all the $$$1's$$$ before the first $$$0$$$ in $$$S1$$$. If we maximize $$$S2$$$, it would the same as maximizing $$$S1$$$.
We use 2 pointer approach. Let $$$itr1$$$ be the iterator for $$$S1$$$ and $$$itr2$$$ be the iterator for $$$S2$$$.
$$$if(S2[itr2] == 1)$$$ then we can't make it $$$0$$$ as we are performing BITWISE OR operator. And this works to our advantage as we want to maximize $$$S2$$$.
$$$if(S2[itr2] == 0)$$$, then $$$S2[itr2] \hspace{1mm} | \hspace{1mm} (Bitwise OR) \hspace{1mm} S1[itr1] = 0 \hspace{1mm} | \hspace{1mm} S1[itr1] = S1[itr1]$$$. So we set $$$S2[itr2] = S1[itr1]$$$.
Question: What will be the starting index of $$$itr1?$$$
Answer: Let $$$idx_0$$$ be the first occurrence of $$$0$$$ in S1. If we take $$$itr1 >= idx_0$$$, then $$$S1[idx_0]$$$ will never become $$$1$$$. So $$$itr1 \hspace{1mm} \epsilon \hspace{1mm} [0, idx_0 - 1]$$$.
Code: 176851036
Using a language with BigInteger support will be very helpful in the process. See my submission (176783281) for a solution using BigInteger on python.
True, the code will become much simpler.
Shimt! Yesterday in contest I taught that this approach will give tle That's why i didn't implemented this
What does it mean when it says jury has a better answer in the 2nd problem. I faced this problem in past also but solved after manipulating a few steps. I don’t understand what does it mean and how to avoid it in the first place? Thanks in advance!
That simply means that your output is not the optimal solution for the given testcase.
Have this contest turned unrated? I was hoping to become master after this contest. :(
Rating changes in Edu rounds usually take around 24 hours.
I can’t wait for my +103…
Predictors aren't accurate right?
Ah..? Since we use the published rating formula, wouldn't it be almost the same?
True that but sometimes I find the difference is sometimes +-5 and sometimes +-20
It was +107 bro
For me +99 and finally BLUE! xD
Can you give me a predictor, every single one i find online are not working.
carrot extension!
Where it can be found?
It's web browser extension. I recommand 'Carrot'.
Ok, installed Carrot and opened https://codeforces.net/contest/1743/standings But how I can find myself in this list? UPD: found!
Clik the friends standings tab. - UPD: I hope you use it useful.
Thanks, -37 unlucky :(
Waiting for the editorial.
Will there be system testing?
Me also Waiting for it.I think there must be system testing.
Congrats on reaching Specialist!
Congo to you man on reaching expert. Let's talk drop me a message.
On LinkedIn?
Yeah
System testing is done now. When the ratings will be updated?
Looks like that's the most frequent comment of yours. I wonder if anyone ever has answered that. I wish anyone could. Soon, I guess.
I too waiting for the same. I guess plagiarism check would be going on.
I think it's done before systest)
Any one who can tell me the solution of problem D please?
This has already been discussed a lot above.
Ok, thanks.
can someone tell me why test case generated randomly is relatively important? in the problem D
Because the solution is based on the fact that the first group of ones in the string has <= relatively small number. The probability of having, let's say 1000 consecutive ones , is $$$\frac{1}{2^{1000}}$$$, which is extremely small number.
The algorithm is O(x*(n-x)) where x is the length of the suffix such that if we remove that suffix all the element that remains is 1. So having a 100 1's at the end have a very less probability so the algorithm works in 100*n that is acceptable.
I think codeforces have forgot that this round is rated.
Now, Yes it is rated.
Thank this round for making me Blue
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
Thanks for this contest make me green,Can i have an upvote:)
yeah