Tommyr7's blog

Codeforces Round #462 Editorial
By Tommyr7, history, 7 years ago, In English

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!

Tutorials

934A - A Compatible Pair

Author quailty / Preparation quailty / Tutorial quailty

Tutorial
Solution (quailty)

934B - A Prosperous Lot

Author Tommyr7 / Preparation cyand1317 / Tutorial cyand1317

Tutorial
Solution (Tommyr7)

933A - A Twisty Movement

Author visitWorld / Preparation visitWorld / Tutorial visitWorld

Tutorial
Solution (visitWorld)

933B - A Determined Cleanup

Author Tommyr7 / Preparation cyand1317 / Tutorial cyand1317

Tutorial
Solution (Tommyr7)

933C - A Colourful Prospect

Author quailty / Preparation quailty / Tutorial quailty

Tutorial
Solution (quailty)
Solution (cyand1317)

933D - A Creative Cutout

Author skywalkert / Preparation skywalkert / Tutorial skywalkert

Tutorial
Solution (skywalkert)
Solution (demon1999)

933E - A Preponderant Reunion

Author skywalkert / Preparation skywalkert / Tutorial skywalkert

Tutorial
Solution (skywalkert)

Thank you everyone!

Happy Valentine's Day and happy Lunar New Year!

  • Vote: I like it
  • +66
  • Vote: I do not like it

Comments Comments (73)
| Write comment?
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Auto comment: topic has been updated by Tommyr7 (previous revision, new revision, compare).

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it -59 Vote: I do not like it

    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.

    → Reply
»
7 years ago, # |
  Vote: I like it +103 Vote: I do not like it

Feedback: Terrible pretests for D and terrible spj for E.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +42 Vote: I do not like it

    Oops... Sorry for the inconvenience. T_T

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it +27 Vote: I do not like it

      He means the checker. It is a pity that he operated on zeros and didn't pass pretests in problem E.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +22 Vote: I do not like it

        Ehem. It is written in bold that each operation should be on positive numbers.

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it +38 Vote: I do not like it

          Yes you are right. Maybe he is just too nervous with the end of the contest approaching :)

          → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Terrible nickname.

    → Reply
»
7 years ago, # |
← Rev. 5   Vote: I like it +19 Vote: I do not like it

Python2: 35268543

[igorjan@archlinux]$ du -b B.py
44	B.py

Perl: 35270787

[igorjan@archlinux]$ du -b B.pl
38	B.pl
→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 3   Vote: I like it +13 Vote: I do not like it

    python2 [42 bytes] : 35283953

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Oh! It's so easy in python! Here is my C++ code: 35239158 (charlieshu is also me)

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it 
        int n;

int main()
{
	cin>>n;
	if(n>36)OVER("-1");
	for(int i=0;i<n/2;i++)cout<<8;
	if(n%2)cout<<4;
	cout<<endl;
	return 0;
}
        → Reply
»
7 years ago, # |
  Vote: I like it +16 Vote: I do not like it

div1C: find all intersections -> build graph -> count edges and vertices -> F = 2 + E — V . Am I right?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

    Partially correct, think about three single circles.

    Actually my tutorial is finished but it needs to be posted by the sleeping poster :(

    → Reply
»
7 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Why is div1C = gym100200C ?

→ Reply
»
7 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Auto comment: topic has been updated by Tommyr7 (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For Div1 C, it should be 3 if n=2 and two circles are neither intersect nor tangent

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you for pointing out. I will fix it later.

    → Reply
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Auto comment: topic has been updated by Tommyr7 (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +49 Vote: I do not like it

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: 11111122222222

Suppose we unflip the segment. Now the sequence looks like this: 1111222211112222

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

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You Miss out cases like

    111111122112211221122222221111

    Here answer should be 18. It can be found if you twist from 7 index(0-based) to end.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks nice explanation it worked for me

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sir , I still didn't get why are we finding the longest subsequence of type 1s,2s,1s,2s in your solution.. Plz explain.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is there still a O(n) solution if the sequence has more values(1,2,3,4,5...)?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        If in that case, we need to find out the longest subsequence of 1s5s4s3s2s1s5s, am I right?

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Partially correct. There may be several cases such as 1-2-4-3-2-4-5.

          → Reply
          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
              Vote: I like it +11 Vote: I do not like it

            Thanks a lot, and Happy lunar New Year!

            → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks a lot!

    → Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

For the benefit of all beginners, here's my O(nm) solution for Div 2 A.

http://mirror.codeforces.com/contest/934/submission/35280443

My 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

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is exactly what I thought of except that I missed some corner cases and got WA :P. Nice approach !

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ah got it. Thanks. I read it wrong, my bad. Thanks for the help :)

      → Reply
»
7 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

Not the best idea in E task. Complicated geometry that required special knowledges — it is not for 2-hour contest :(

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Tommyr7 (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it -9 Vote: I do not like it

Where is Div2D ? Edit: Sorry.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain me div2 C?

→ Reply
»
7 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Can someone explain another solution for problem

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for the response. Check this solution. I thought that indexing may be an issue, so tried this way. And this amazing result :P

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Woah, I had no idea, this can affect time taken by approximately 10 times.

        → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please provide beginner friendly explanation of Div2 E?

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me with my solution of DIV2 C. http://mirror.codeforces.com/contest/934/submission/35292502

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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!

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Thanks so much! I also wasted a great deal of time on it.

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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 :P

    The tutorial was fixed just now. Please wait for a while and refresh the page :)

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Okay, thanks a lot. By the way, despite that accidental mistake, Div.1 D was really a wonderful and challenging problem :).

      → Reply
»
7 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

Many thanks Codeforces for the interesting problems.

RE: 933C - A Colourful Prospect

Is there an explanation that the solution to test #115

3

0 0 1

0 3 2

4 0 3

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

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Please note tutorial for 933E has been revised for better understanding. Hope it will be helpful :)

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For div2 E can anyone explain why is my algorithm wrong? Code

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

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Flipping [10, 11] gives 1, 2, 1, 2, 1, 2, 1, 2, 1, 1, 2, 2.

    → Reply
»
5 years ago, # |
  Vote: I like it -10 Vote: I do not like it

For 933 A, do not read the editorial's solution. It's, in simple words, bad. Use Um_nik's solution as well. Easy to understand.

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How would you solve D1d's bonus? Sorry for necroposting but I can't find it anywhere.

→ Reply