### Tommyr7's blog

By Tommyr7, history, 4 years ago,

Hi, all!

This is not Tommyr7, but the impostor behind the round again (guess who I am? :P). The statements are written by me. Thank you, everyone, and hope you've all enjoyed the round!

Any feedback on problems and tutorials are welcome — we look forward to doing even better in the future!

Here are some of the detailed tutorials!

### 934A - Совместимая пара

Author quailty / Preparation quailty / Tutorial quailty

Tutorial
Solution (quailty)

### 934B - Большая ставка

Author Tommyr7 / Preparation cyand1317 / Tutorial cyand1317

Tutorial
Solution (Tommyr7)

### 933A - Извилистые движения

Author visitWorld / Preparation visitWorld / Tutorial visitWorld

Tutorial
Solution (visitWorld)

### 933B - Генеральная уборка

Author Tommyr7 / Preparation cyand1317 / Tutorial cyand1317

Tutorial
Solution (Tommyr7)

### 933C - Цветное зрелище

Author quailty / Preparation quailty / Tutorial quailty

Tutorial
Solution (quailty)
Solution (cyand1317)

### 933D - Оригинальное вырезание

Author skywalkert / Preparation skywalkert / Tutorial skywalkert

Tutorial
Solution (skywalkert)
Solution (demon1999)

### 933E - Важнейшее объединение

Author skywalkert / Preparation skywalkert / Tutorial skywalkert

Tutorial
Solution (skywalkert)

Thank you everyone!

Happy Valentine's Day and happy Lunar New Year!

• +66

 » 4 years ago, # |   +5 Auto comment: topic has been updated by Tommyr7 (previous revision, new revision, compare).
•  » » 4 years ago, # ^ | ← Rev. 2 →   -59 Please don't make problems that require either using python or programming your own BigInt class, It's unfair for people who exclusively program c++. I don't see any need for the bounds in div1B to be so large.Or maybe I should just finally learn python...Edit: I was wrong, the problem is definitely solvable with just long long. I'll do more research before complaining next time.
•  » » » 4 years ago, # ^ |   +56 What? 35233893
•  » » » 4 years ago, # ^ | ← Rev. 2 →   -50 it was solvable in c++ only
•  » » » 4 years ago, # ^ | ← Rev. 3 →   +24 do you think all these guys used their own BigInt class?
 » 4 years ago, # |   +103 Feedback: Terrible pretests for D and terrible spj for E.
•  » » 4 years ago, # ^ |   +42 Oops... Sorry for the inconvenience. T_T
•  » » 4 years ago, # ^ |   +25 What is spj?And I don't really think that pretests should be that strong. Yes, input is bigger than MOD, so you should be careful.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +27 He means the checker. It is a pity that he operated on zeros and didn't pass pretests in problem E.
•  » » » » 4 years ago, # ^ |   +22 Ehem. It is written in bold that each operation should be on positive numbers.
•  » » » » » 4 years ago, # ^ |   +38 Yes you are right. Maybe he is just too nervous with the end of the contest approaching :)
•  » » 4 years ago, # ^ |   0 Terrible nickname.
 » 4 years ago, # | ← Rev. 5 →   +19 Python2: 35268543 [igorjan@archlinux]$du -b B.py 44 B.py Perl: 35270787 [igorjan@archlinux]$ du -b B.pl 38 B.pl 
•  » » 4 years ago, # ^ | ← Rev. 3 →   +13 python2 [42 bytes] : 35283953
•  » » » 4 years ago, # ^ |   +1 Oh! It's so easy in python! Here is my C++ code: 35239158 (charlieshu is also me)
•  » » » » 4 years ago, # ^ |   0 int n; int main() { cin>>n; if(n>36)OVER("-1"); for(int i=0;i
 » 4 years ago, # |   +16 div1C: find all intersections -> build graph -> count edges and vertices -> F = 2 + E — V . Am I right?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +6 Partially correct, think about three single circles.Actually my tutorial is finished but it needs to be posted by the sleeping poster :(
 » 4 years ago, # |   0 Where is the other problem editorial???
 » 4 years ago, # |   +24 Why is div1C = gym100200C ?
 » 4 years ago, # |   +11 Auto comment: topic has been updated by Tommyr7 (previous revision, new revision, compare).
 » 4 years ago, # |   0 For Div1 C, it should be 3 if n=2 and two circles are neither intersect nor tangent
•  » » 4 years ago, # ^ |   0 Thank you for pointing out. I will fix it later.
 » 4 years ago, # |   +3 Auto comment: topic has been updated by Tommyr7 (previous revision, new revision, compare).
 » 4 years ago, # | ← Rev. 2 →   +49 The tutorial isn't up for Div1A, and the code looks quite complicated. Here's a much simpler way:Let's say we flipped a segment and found the best subsequence. It will look something like this: 11111122222222Suppose we unflip the segment. Now the sequence looks like this: 1111222211112222That is, it will be composed of 4 regions, made of 1s,2s,1s,2s. So the problem reduces to simply figuring out the longest subsequence of such form in the original sequence, no flipping necessary.This can easily be done with a single O(N) traversal of the sequence. At each point, keep 4 values: the longest sequence of 1s, the longest sequence of 1s2s, the longest sequence of 1s2s1s, and finally the longest sequence of 1s2s1s2s.EDIT: The editorial is up and they put this solution in it. Still, strange that they would use the complicated N^2 solution as the sample.
•  » » 4 years ago, # ^ |   0 You Miss out cases like111111122112211221122222221111Here answer should be 18. It can be found if you twist from 7 index(0-based) to end.
•  » » » 4 years ago, # ^ |   0 Running it through my solution, I'm getting an answer of 24, so I think you're missing something. Flipping 7 index to the end does work for that (the only things missing from the increasing subsequence are the 3 pairs of 11 in the middle).
•  » » 4 years ago, # ^ |   0 Thanks nice explanation it worked for me
•  » » 4 years ago, # ^ |   0 Sir , I still didn't get why are we finding the longest subsequence of type 1s,2s,1s,2s in your solution.. Plz explain.
•  » » » 4 years ago, # ^ |   0 Because when you flip the middle segment of 2s and 1s, you get a sequence of 1s followed by 2s, which is what you want.
•  » » 4 years ago, # ^ |   0 Is there still a O(n) solution if the sequence has more values(1,2,3,4,5...)?
•  » » » 4 years ago, # ^ |   0 Yes, your intuition is almost right.In fact, a previous version limits 1 ≤ ai ≤ 5 and the author has tested a O(53n) solution :P
•  » » » » 4 years ago, # ^ |   0 If in that case, we need to find out the longest subsequence of 1s5s4s3s2s1s5s, am I right?
•  » » » » » 4 years ago, # ^ |   0 Partially correct. There may be several cases such as 1-2-4-3-2-4-5.
•  » » » » » » 4 years ago, # ^ |   +11 Thanks a lot, and Happy lunar New Year!
•  » » 4 years ago, # ^ |   0 Thanks a lot!
 » 4 years ago, # |   +5 For the benefit of all beginners, here's my O(nm) solution for Div 2 A. http://codeforces.com/contest/934/submission/35280443My idea was to find all products, find the maximum product A[i]B[j] in one O(nm) scan. Then, find the maximum without that particular A[i], in another O(nm) scan. The best A can do is hide at most one element and A has to hide the element that contributes to the greatest product.https://github.com/MathProgrammer/CodeForces/blob/master/Explanations/Explanations%2019/A%20Compatipble%20Pair%20Explanation.txt
•  » » 4 years ago, # ^ |   0 This is exactly what I thought of except that I missed some corner cases and got WA :P. Nice approach !
•  » » » 4 years ago, # ^ |   0 Thank you !
 » 4 years ago, # |   0 Div 2- C/ Div-1 A:I am unable to understand this case for which my solution is failing. The editorial is not yet there. Can anyone explain how is the answer to pretest 3 is 116. Many thanks :)http://codeforces.com/contest/934/submission/35263594
•  » » 4 years ago, # ^ |   0 Your answer of 13 is way too low.My guess is that you interpreted "subsequence" to mean "subarray". The difference is that a subsequence doesn't have to be contiguous.For example, 1 2 3 4 is a subsequence of 1 5 2 5 3 5 4.
•  » » » 4 years ago, # ^ |   0 Ah got it. Thanks. I read it wrong, my bad. Thanks for the help :)
•  » » » 4 years ago, # ^ |   0 Thanks
 » 4 years ago, # |   +2 My solution for "A Prosperous Lot" : 54 bytes. can we have a look at Tester Solution please.  n=int(input()) print(["8"*(n//2)+"9"*(n%2),-1][n>36])
 » 4 years ago, # | ← Rev. 2 →   -8 Not the best idea in E task. Complicated geometry that required special knowledges — it is not for 2-hour contest :(
 » 4 years ago, # | ← Rev. 2 →   0 I am a beginner and couldn't understand Div 2C problem, but 2A and 2B is fine. How should I overcome it? Pl. somebody explain the DP part fully.
 » 4 years ago, # |   0 Auto comment: topic has been updated by Tommyr7 (previous revision, new revision, compare).
 » 4 years ago, # | ← Rev. 2 →   -9 Where is Div2D ? Edit: Sorry.
 » 4 years ago, # |   0 Can someone explain me div2 C?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Here is my approach. Ask me if you have any doubt.
•  » » » 4 years ago, # ^ |   0 Thanks!!
•  » » » 4 years ago, # ^ |   0 Plz explain it ??Still not understood
 » 4 years ago, # |   +6 Can someone explain another solution for problem
 » 4 years ago, # |   0 for Problem C, my solution is to regard each a[i] as the position changes from 1 to 2. That means, we calculate all 1's before i and all 2's after i, so we can get all maxium length through a[i] in O(n). Then we do the reverse, we can regard the reverse section [L, R], only L < i < R will affect a[i]'s max length, and i split the section into two parts, [L, i) and (i, R]. For section [L, i] after reverse, we can minus all 1 and plus all 2 in the section. And for (i, R], it's simmilar but we plus all 1 and minus all 2. Also, these two section are distinct, so we can get max L and R, sepeartely. Therefor the whole algorithm is in O(n^2)
 » 4 years ago, # | ← Rev. 2 →   0 Can someone explain to me why my solution for problem C in JAVA is giving TLE in large value of n. I am using similar approch as sak3t described in this comment. I see that c++ solution easily passes whereas Java is having a hard time.
•  » » 4 years ago, # ^ |   0 Ideally it should pass the time limit easily. I don't find any bug in your submission. Probably it is some high Java intensive problem in your code.PS: Try to optimize the code more. Like you don't need to store dp[i][j][k], as we need data for only dp[0][j][k] and dp[i][n - 1][k]. Notice, 0 and n - 1 constants. You can have this data in two linear arrays rather than one 2D array.
•  » » » 4 years ago, # ^ |   0 Thanks for the response. Check this solution. I thought that indexing may be an issue, so tried this way. And this amazing result :P
•  » » » » 4 years ago, # ^ |   0 Woah, I had no idea, this can affect time taken by approximately 10 times.
 » 4 years ago, # |   0 Can anyone please provide beginner friendly explanation of Div2 E?
 » 4 years ago, # |   0 Can someone help me with my solution of DIV2 C. http://codeforces.com/contest/934/submission/35292502
 » 4 years ago, # |   0 In Problem A i just sorted the 2 arrays and the answer was the mutliplication of a[n-2]*b[m-1] i skipped the max of tommy and get the max of banban * the max of tommy after deleting the it's first max and i got WA on test 10 any help please
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Your code fail for this simple test:3 3-7 1 5-7 1 5
•  » » » 4 years ago, # ^ |   0 so what should be the result 5 or 49
•  » » » » 4 years ago, # ^ |   0 The correct answer is 25
 » 4 years ago, # | ← Rev. 2 →   0 How could I get the intersection of two circle, my previous method didn't provide enough precision.I can't get the main idea behind quailty's method.Could someone explain it for me?
 » 4 years ago, # |   0 Hi, in problem 934A — A Compatible Pair, the solution can be found sorting both vectors throw the greater values, then the answer is a[1]*b[0] or a.back()-1*b.back(), greater values of this two, is this ok? With that i have passed all pretest cases
 » 4 years ago, # |   +5 For Div.1 D, there's a terrible mistake in the tutorial which almost drove me mad this morning and took me hours to realize what was wrong.That polynomial of L mentioned in the tutorial appeared to be ,but the correct polynomial seems to be .Please fix it as soon as possible!
•  » » 4 years ago, # ^ |   +8 Thanks so much! I also wasted a great deal of time on it.
•  » » 4 years ago, # ^ |   +5 Ha! You found a blind spot! The mistaken polynomial was from my draft paper (and I used to wrong profoundly...) but the standard solution uses the appropriate polynomial :PThe tutorial was fixed just now. Please wait for a while and refresh the page :)
•  » » » 4 years ago, # ^ |   +8 Okay, thanks a lot. By the way, despite that accidental mistake, Div.1 D was really a wonderful and challenging problem :).
 » 4 years ago, # | ← Rev. 5 →   0 Many thanks Codeforces for the interesting problems.Is there an explanation that the solution to test #11530 0 10 3 24 0 3is 5 not 4? It seems that C1 = (0,0,1) is tangent to C2 = (0,3,2) at point P12 = (0,1), and is tangent to C3 = (4,0,3) at point P13 = (1,0). And, that C2 and C3 are not tangent and do not intersect. Therefore, the number of regions should be 4 not 5.Thanks in advance for explaining.Best wishes. An update: A further analysis of the test case revealed that C2 and C3 are tangent at P23 = (8/5,9/5). Therefore, the area surrounded by the three arcs on C1, C2 and C3 extending between each pair of P12, P13, and P23 constitutes the fifth region.Thanks again and best wishes.
 » 4 years ago, # |   0 can anyone please explain the approach behind div2A? I am not getting why do we need to print the minimum of maximums and not the 2nd maximum?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 harshit15 The idea here is if you can generate a max product value which is less than the max of all the other cases then you would choose to eliminate that value from the array. Eg. : If by eliminating i=0, you get max_product = m_0, i=1, you get max_product = m_1, i=k, you get max_product = m_k, i=n, you get max_product = m_n, and suppose m_k is min across these, then you would choose to eliminate i=k, and get the result product as m_k.
 » 4 years ago, # |   0 plzz explain DIV2 C problem solution?? Not able to get it
 » 4 years ago, # |   +10 Please note tutorial for 933E has been revised for better understanding. Hope it will be helpful :)
 » 4 years ago, # |   0 For div2 E can anyone explain why is my algorithm wrong? Codeif n==1 , ans=2 ; if n==2 , ans=3 (two circle,universal region) , for every pair of circles intersecting:ans++ if n==3 , ans=4 (three circle,universal region), for every pair of circles intersecting: ans++. if all three intersects, ans++.I cannot understand what is wrong with this algorithm? TIA.
•  » » 4 years ago, # ^ |   +1 You can use GeoGebra for reasoning. Here is test 14.
•  » » » 4 years ago, # ^ |   0 Thanks skywalkert! Yes, diagram clears me that my algorithm is wrong but i cannot understand why is algorithm wrong. I cannot seem to disprove it logically. For every 2-circle intersecting, adds a new region that wouldn't have existed if that particular 2-circle didn't intersect.Been stuck thinking on this for hours.
 » 4 years ago, # | ← Rev. 2 →   0 Can anyone please explain the question "A twisty movement" DIV2 C with this test case n=12: 1 2 1 2 1 2 1 2 1 2 Length of the Longest subsequence after the reversal is 8! Can anyone please tell [l,r] which need to flip to get this answer
•  » » 4 years ago, # ^ |   0 Flipping [10, 11] gives 1, 2, 1, 2, 1, 2, 1, 2, 1, 1, 2, 2.
 » 4 years ago, # | ← Rev. 2 →   0 http://codeforces.com/contest/934/problem/D Can anyone help me to understand how the code given in its tutorial is working, I am not able to understand how to get function is helping to get the answer
 » 6 months ago, # | ← Rev. 2 →   0 934D, when $x=-k$ then $f(x) = q(x) * (x + k) + p$ reduces to $f(-k) = p$. No need to deal with dividing polynomials at all.