feecIe6418's blog

By feecIe6418, history, 4 years ago, In English

Hello Codeforces!

gyh20 and I are glad to invite you to Codeforces Round 670 (Div. 2) which will start on Sep/12/2020 16:45 (Moscow time). Note the unusual start time of the round.

The contest will last for two hours, and you will have five tasks to solve. The tasks are prepared by me and gyh20. This round is rated for participants whose rating is not higher than 2099. You can see that my current rating is exactly 2099 :)

There might be an interactive problem. You can learn about them here.

We would like to thank:

We tried our best to make the statements short and clear, pretests strong and problems interesting. We hope you like the problems!

Score distribution will be announced shortly before the round.

Good luck and have fun!

Upd: Score distribution is 500-750-1250-1750-2500.

Upd: For problem reasons, the contest is delayed for 10 minutes. We are very sorry to keep you waiting, sorry again.

Upd: Score distribution is changed to 500-1000-1500-2000-2750.

Upd: The round is finished. We're really sorry for B being well-known (none of the testers knew the harder version of this problem in ABC173E). Still, congratulations to the winners!

Div1 (unofficial):

  1. WZYYN
  2. Geothermal
  3. kort0n
  4. neal
  5. kotatsugame

Div2:

  1. JSoap
  2. DemolitionLovers
  3. killyou
  4. gmh77
  5. SkyStar

Upd: Editorial is out here.

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

| Write comment?
»
4 years ago, # |
Rev. 3   Vote: I like it +286 Vote: I do not like it

As a tester,I want some contribution!

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +69 Vote: I do not like it

    Have a strong heart, dear.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +60 Vote: I do not like it

    So why are we downvoting the tester >_<

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +56 Vote: I do not like it

    A tester leaves a rated contest for us, Have some decency please

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -85 Vote: I do not like it

      I won't mind leaving a rated contest just to see my name in the blog and then getting easy contributions later.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    what we get if we have some contribution.i often see people are asking for contribution ??

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      nothing,in general but it is an indication that you have been useful to the community.Also there is a list for top contributors

»
4 years ago, # |
  Vote: I like it +263 Vote: I do not like it

As a coauthor,I am so glad to hold the contest, and i want you-know-what.

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

    I want positive contribution instead of negative contribution!

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +31 Vote: I do not like it

      Don't forget to give the tester _zzw4257 you-know-what as well. :)

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +260 Vote: I do not like it

      sad life :(

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        This happens to me when contest is delayed it hurts alot as i am preparing my self to encounter the problem and just 10 mins more added....

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +12 Vote: I do not like it

          Thanks a lot for replying, I had forgotten about the contest. You reminded me. :)

»
4 years ago, # |
  Vote: I like it +59 Vote: I do not like it

feecIe6418 Can you highlight the start time of the contest.

»
4 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Really looking forward to the contest!I think it will be very good!

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

    Are you son of Time_tears ? :v

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it +24 Vote: I do not like it

      Definitely not! You can see that he created the account a lot later than I did and there is nothing I can do.

      Sorry,it's just a typo.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        Sorry for telling that..But when i read your id name , i think the tester fisherking and your id name can be related . Again sorry sir !

»
4 years ago, # |
  Vote: I like it +64 Vote: I do not like it

As a problem improver, have fun!

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

    What I improved is following:

    In the task E, there was one more constraint "It is guaranteed, that an integer $$$p>1$$$ such that $$$x$$$ is divisible by $$$p^2$$$ does not exist. You want to find $$$x$$$."

    I noticed that we can erase this constraint. If you couldn't solve E, it's good that thinking this version first!

»
4 years ago, # |
Rev. 3   Vote: I like it -118 Vote: I do not like it

Off Topic : What is the cutoff for candidate master.. 1800 ? or 1900 ?

»
4 years ago, # |
  Vote: I like it -26 Vote: I do not like it

Your rating is exactly 2099 but unfortunately the round is not rated for you.

»
4 years ago, # |
  Vote: I like it -83 Vote: I do not like it

feecIe6418, Will there be any subtasks? I really think having subtasks makes contest more interesting.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it -33 Vote: I do not like it

    The contest is ICPC style not IOI style,so there will be no subtasks.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      First of all thanks Elegy_No_Programmer for letting me know, but sadly I disagree with your explanation why this contest can't have subtasks. You can see many Div-2 contests had subtasks for eg:Codeforces Round 658 (Div. 2). Also each problems are scored equally in ICPC( like we have in CF educational round ) which is not the case for CF Div-2 rounds.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +46 Vote: I do not like it

    We used to have subtasks, but we found it meaningless to have subtasks on our problems. So we deleted them in the end.

»
4 years ago, # |
Rev. 2   Vote: I like it -54 Vote: I do not like it

Every Round is rated for me, except div 1 :3

»
4 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Are the authors middle school students?

»
4 years ago, # |
  Vote: I like it +42 Vote: I do not like it

Special thanks to csani for helping us with writing the editorials

Editorials are already written?

»
4 years ago, # |
  Vote: I like it +64 Vote: I do not like it

As a tester, I would recommend you to participate in this. The problems are really interesting. Good Luck and have fun.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +47 Vote: I do not like it

    .

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Not all testers comment on this!!! And everyone has their own opinion on what's interesting.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +56 Vote: I do not like it

      Not really, it's just that testers who think that the round is bad usually don't say "this round is bad, don't participate" in the comments.

»
4 years ago, # |
Rev. 2   Vote: I like it +80 Vote: I do not like it

That day is my birthday. It will be a memorable contest lmao :))

»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

$$$Yoo$$$ now it's becoming trend of $$$make \,the\, statements \,short \,and \,clear$$$

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

    Its useful too. Isn't it?Trgt_2021_explosion

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

      As far as there is no story telling(irrelevant statements i.e. not related to that Task) then even complex scenario is fine because converting some complex statements into Mathematical equations/logic is a skill and one should try to learn it.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        Hi,Trgt_2021_explosion I support your thoughts. But I think a clear statement refers to a clear mention of the requirements. Like "if multiple solutions, print any" or this kind of thing... not making a problem easy or spoon-fed.

»
4 years ago, # |
Rev. 2   Vote: I like it +33 Vote: I do not like it
  • Round #$$$666$$$ contains $$$5$$$ problems for each division.
  • Round #$$$668$$$ contains $$$5$$$ problems for each division.
  • Round #$$$669$$$ contains $$$5$$$ problems.
  • Round #$$$670$$$ contains $$$5$$$ problems.

Is it a trend or...something else?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +48 Vote: I do not like it

    No.In fact most of the CF contests a few years ago had 5 problems.

»
4 years ago, # |
Rev. 4   Vote: I like it -8 Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +24 Vote: I do not like it

486bie.jpg

»
4 years ago, # |
Rev. 2   Vote: I like it -22 Vote: I do not like it

I have a question for the authors. Do you know Jiangly? Are you friends?(Sorry. I now feel that this question is not so appropriate. Thank you very much for the author's answer.)

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +44 Vote: I do not like it

    We know Jiangly, because he is the best one in the city,but we are not so good as him so he definitely doesn't know us.

»
4 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Excited to take part in my first contest!

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I have known that the author is very excellent,bless all and hope everyone get higher rating.

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

After two years without competing here, it is time to come back! :)

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    your rating graph is quite interesting!

»
4 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Hope that the interactive one will be nice just like the one in the last contest...

»
4 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Thank GOD for no scary pictures this time...

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Great!! Problems with short and clear statement are really good. Hope this will be a good round.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    with strong pretest.

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it +8 Vote: I do not like it

      Yeah,this is also very good since my problem will not hack after pretest passed.This hacked really sad me.

»
4 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Why do all the Div.2 rounds consist of 5 problems nowadays? Why not 6/7?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +46 Vote: I do not like it

    How many times have you solved more than 3-4 questions lol?

    On a serious note, you and I can't even imagine the amount of work it goes into setting a problem and preparing the statements, test cases, etc. So, simply saying things is very easy, when you don't know what is going on behind the scenes

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it +10 Vote: I do not like it

      emmm, recent div.2 rounds are really easier than that before. just like me, before Round 658 , I only solved 2-3 questions. But after Round 658, I always solve 4 questions in Round which had 5 problems.

      To some degree, it can be named speedforces.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +55 Vote: I do not like it

        Maybe you just progress

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it +9 Vote: I do not like it

        That means you are improving! Do you want to stay at the level of only being able to solve 2-3 problems?

        And, let's just assume for a minute, that the problems have become easier. Do you still know how much effort goes into making those problems, setting up everything, co-ordinating with so many people, getting people to test your problems etc.?

        To be very honest, I have tried to sit down for hours by myself to think about making a problem, but I never made a single problem which wasn't already popularly known.

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 4   Vote: I like it +27 Vote: I do not like it

        You should have played Round 669.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +77 Vote: I do not like it

      is this really necessary to reply someone with this first line!? is it really matter how many problems he solved to tell his opinion and ask his question!? these kind of replies will force them to create alt acc(and probably ruin the cf community). dont bully anyone because of their rating PLS!

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Your point is valid, but he did ask in a curious way(Not implying or demanding anything). In no way was it appropriate to reply with that first line.

»
4 years ago, # |
  Vote: I like it +7 Vote: I do not like it

I hope it have strong pretest!

»
4 years ago, # |
  Vote: I like it -9 Vote: I do not like it

I don't want to FST any more.

So do you have the strong pretests?

»
4 years ago, # |
Rev. 2   Vote: I like it +44 Vote: I do not like it

This is gonna be my first ever contest. So excited about it. Not very experienced in Competitive Programmer but my journey starts from now. I hope this be a hell of a journey!

UPD : For those who Upvoted me and wished me luck, thank you so much! I think your wishes came true and i got Rank : 652 and Rating got +671

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +45 Vote: I do not like it

    T̶u̶r̶n̶ ̶b̶a̶c̶k̶ ̶w̶h̶i̶l̶e̶ ̶y̶o̶u̶ ̶s̶t̶i̶l̶l̶ ̶c̶a̶n

    Good luck on your first contest!

»
4 years ago, # |
  Vote: I like it -33 Vote: I do not like it

Is there any Chinese description

»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Happy Programmers' Day!!

»
4 years ago, # |
Rev. 2   Vote: I like it -17 Vote: I do not like it

What's Polygon?

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

    It's a platform that helps make problems, created by Mike

»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Socre distribution <- typo

»
4 years ago, # |
  Vote: I like it -93 Vote: I do not like it

The comment is hidden because of too negative feedback, click here to view it

»
4 years ago, # |
  Vote: I like it +17 Vote: I do not like it

As far as I've seen, this is your first contest arrangement in CF. Best of luck to you too.

(Hope everything will be fine)

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Interactive problem will be there or not ?

»
4 years ago, # |
  Vote: I like it +17 Vote: I do not like it

There might be an interactive problem.

I guess that codeforces is trying to make interactive problems a part of the contests, which according to me, is a good thing to do.

»
4 years ago, # |
  Vote: I like it -131 Vote: I do not like it

start the contest!! im feeling horny

»
4 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Delayed by 10 min :(

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +66 Vote: I do not like it

Very sorry,something we didn't expect happened just now ,the contest is delayed by 10 minutes, hope there won't be another delay.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thanks for the info :)

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +29 Vote: I do not like it

      I think no longer , it should be good this time.

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

    Just curious to know, what was the last minute change because of which score distribution was changed? I think present scoring distribution was accurate.

»
4 years ago, # |
  Vote: I like it -21 Vote: I do not like it

wish me good luck.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it -19 Vote: I do not like it

    why though? why to you specifically?

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -18 Vote: I do not like it

      because I am loosing my rating. can't you see?

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Then what you need is practice and not good luck!

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it -8 Vote: I do not like it

          yes bro I do.. But CP is fun and exciting. Why you taking it as a fight? if someone ask wish me good luck if you can just wish them.. What is harm in it? Spread love and have fun bro. This is what life is.

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        more practice and then make progress. good luck and high rating!

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

    good luck!

»
4 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Delay it as much as you want and solve the problem PLEASE DON'T MAKE IT UNRATED due to those issues

»
4 years ago, # |
Rev. 2   Vote: I like it -12 Vote: I do not like it

delayforces again lol, but still great thanks for the preparation!

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    We're very sorry. But please, still enjoy the contest.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Thank you for your effort!!

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

      So you people make quality problems for us, make quality test cases so that only good solutions pass and respond to our queries during the contest.

      I don't think you need to apologize for anything. You're already doing more than we deserve.

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

delay making me more anxious.

»
4 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Score distribution changes.

»
4 years ago, # |
  Vote: I like it -7 Vote: I do not like it

Hoping for strong pretests!

»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

How to solve D?

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Didn't passed system test yet but my solution idea is :-

    Hints:-

    ans is

    tot = a[0]+d where d = sigma( max( 0, a[i+1]-a[i] ) );

    ans = (tot+(tot>=0))/2;

    so only edges L and R in queries can change the value of d.

    I guess now you can figure out the solution

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +26 Vote: I do not like it

    My solution has not yet passed sys tests but here is how I solved it. Suppose we let initial value of non decreasing array be c so initial value of non increasing array will be a[1]-c.

    Now for each next element if is greater than previous value we can keep the value in non increasing array constant therefore the other array remains non decreasing. We can similarly keep the value in non decreasing array constant if the next element is less than the previous one.

    Therefore we get the final value of non decreasing array as c+(sum of all positive a[i]-a[i-1]). Now we just have to minimise max(a[1]-c, c+sum of +ve dif). We can see that it will be minimum if both elements are equal.

    After each query only 2 differences are changed at max so we can store values of each element by Fenwick Tree and recalculate the optimal c. Upd: passed sys tests.

  • »
    »
    4 years ago, # ^ |
    Rev. 7   Vote: I like it +4 Vote: I do not like it

    Observe that since $$$b_{i}$$$ is non-decreasing and $$$c_{i}$$$ is non-increasing, the max is just $$$max$$$$$$(c_{0}, b_{n - 1})$$$.

    We can notice that $$$b_{i} \gt b_{i - 1}$$$ will be required when $$$a_{i} \gt a_{i - 1}$$$ and $$$c_{i} \lt c_{i - 1}$$$ will be required when $$$a_{i} \lt a_{i - 1}$$$.

    Clearly $$$b_{0} + c_{0} = a_{0}$$$ is a required condition. Let $$$b_{0} = u$$$ and $$$c_{0} = v$$$.

    If $$$sum_{inc}$$$ is the sum of $$$a_{i} - a_{i - 1}$$$ whenever $$$a_{i} \gt a_{i - 1}$$$, $$$b_{n - 1}$$$ is clearly $$$u + sum_{inc}$$$. So we want to choose $$$u$$$ such that $$$max$$$($$$a_{0} - u$$$, $$$u + sum_{inc}$$$) is the minimum possible. This is clearly $$$\frac{a_{0} - sum_{inc}}{2}$$$ which gives an answer of $$$\lceil \frac{a_{0} + sum_{inc}}{2} \rceil$$$.

    As for the queries, we can notice that only the contributions from $$$a_{l} - a_{l - 1}$$$ and $$$a_{r + 1} - a_{r}$$$ to $$$sum_{inc}$$$ can change. Maybe there is some elegant observation that makes this easy to calculate, but without that also there is an easy way to figure out the change. Subtract the contribution of those two endpoints, update the range (standard lazy prop) and re-add the contribution of them.

    BE CAREFUL that you perform ceil correctly for negative values.

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

      BE CAREFUL that you perform ceil correctly for negative values.

      Damn. That's why my 4th TC got WA.

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

        Wait how, if you ceil incorrectly for negative values it should fail sample 3 as you will do $$$\frac{-2 + 1}{2} = 0$$$ instead of $$$\frac{-2}{2} = -1$$$.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          Hmmm. You've got a point. I didn't mention that I thought that, that might be the issue.

          Now that I can check the test cases, I'll check what exactly went down.

          EDIT: TL;DR: I'm dumb. So I just updated the l and r values of the array, and somehow thought that it would work, without updating the middle values. Will implement the lazy propagation part now.

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

      It should be (a0-sum)/2

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

        Fixed, thanks. I accidentally wrote the minimum obtained instead of the value to be value which when substituted gives the minimum.

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

      We can also do away with the Segment/Fenwick Tree. Since only the contribution of $$$a_l - a_{l-1}$$$ and $$$a_{r+1} - a_r$$$ affect our answer for the current query, keep an array of all differences between consecutive elements and change these two values in that array. Change $$$sum_{inc}$$$ accordingly.

      P.S. Don't forget to change the value of $$$a_0$$$ if the current query starts at index 1. Code

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

        Oh yeah since the Fenwick Tree effectively acts like a dynamic difference array here which is sufficient for our needs. Thanks, somehow that didn't strike at that moment during the contest.

»
4 years ago, # |
  Vote: I like it +23 Vote: I do not like it

How to solve C

  1. See CF blog in recent actions
  2. Understand you can only have one or two centroids
  3. For one centroid print any edge twice
  4. For the second remove an edge going from the first centroid to any vertex except the second centroid(e) then make an edge going from the second centroid to e.

Easy AK!

»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

How to solve E?

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

    I think ask for all prime numbers ( ~9600 ) and make some Inclusion–exclusion principle (ex if you have n = 6 ask for x=2 => s = {1,3,5,6} and for 3 you have to see that 6 is still there (because after the first operation just 1 element %3=0 had to remain in the set) ) .

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    First we use the second operation to all primes < 1000, all the remaining numbers can either be a prime or $$$x$$$.

    We can query A 1 and check if $$$x$$$ is a prime.

    If $$$x$$$ is not a prime, we query every prime number $$$\leq n$$$, and obtain x by finding all prime divisors of $$$x$$$.

    If $$$x$$$ is a prime, we can do the following: delete S prime numbers, and query A 1 to see if $$$x$$$ is in the $$$S$$$ primes numbers you just deleted. When you find the $$$S$$$ numbers that contain $$$x$$$ you do $$$S$$$ extra queries to find $$$x$$$. Let the number of prime numbers be $$$N$$$, The number of operations is $$$N + S + N/S$$$, and we can set $$$S$$$ to $$$\sqrt n$$$

    code: https://codeforces.me/contest/1406/submission/92637463. It passed the pretests anyway.

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

    перебрать все простые делители до N начиная с таких, что их квадрат больше N, проверять можно по группам, например первые 100 такие делители с помощью функции 2 типа, и проверить есть ли среди данных 100 простых чисел нужное с помощью типа 1 и так далее по сто, а в последнем оставшиеся. Затем перебрать все меньшие простые делители и его степени. Например, k — простое, k * k < n, тогда если н делиться на к, с помощью бинпоиска найдем степень вхождения это числа.(iterate through all Prime divisors up to N starting with such that their square is greater than N, you can check by group, for example, the first 100 such divisors using a function of type 2, and check whether among the data 100 primes necessary using type 1, and so on one hundred, and in the last remaining. Then iterate over all the smaller Prime divisors and its powers. For example, k is a Prime, k * k < n, then if n is divisible by K, we use bin search to find the degree of occurrence of this number.)

»
4 years ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

Could anyone help me to find why my code for problem C is TLE.92617935

My solution is linear,as far as i know.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    memset is the problem. If you have 10000 tests of n=1 then you will do 10000 (number of test) * 1e5 (maxN) operations

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You should not clear array sz for each testcase since T can be sufficiently large to give TLE for your implementation. Don't use memset(sz,0,sizeof(sz)) each time. Instead, clear first n cells.

»
4 years ago, # |
  Vote: I like it -9 Vote: I do not like it

Great Contest!! B was really original problem!!

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

    how to solve B I was getting WA in test 3

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -7 Vote: I do not like it

      Sort the array, took the first and the last 5 elements, now you have an array of 10 elements, just brute force for every 5 pairs and take maximum value.

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

        Is this approach correct? Sort the array then take i elements from front(i goes from [0, 5]) and take [n-4+i to n-1] elements from the back. Just compute the max ans from all i. I get WA on test 3, any clues anyone ?

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Aah, of course it is correct, got my mistake i use using INT_MIN instead of LONG_LONG_MIN ;-)

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Notice that there can only be 3 possible answers in B, 1) all largest positive numbers 2) 2 smallest negative and 3 largest positive numbers 3) 4 smallest negative and 1 largest postive numbers. Find the max of all three possible cases

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

      sort the array,the last 5 elements are definitely the biggest now so their product can be the answer but apart from that if the product of first and second number is greater than fourth last and fifth last ,or product of first four numbers is greater than product of second last ,third last,fourth last and fifth last (this will happen when starting numbers are negative ) they can be the answer as well. So, only three cases arise,pick the best.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    Actually.. problem B is a special case of this one ABC173_e where K=5

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

That's a nice contest!

Although I'm not able to solve E, I think the questions are very interesting and I really hope I can have the ability to make such greate problems :)

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve C? it seems it requires some observations, please anyone give hint.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Basically there can atmax exist only 2 centroids and this happens when there exists an edge u-v such size of subtree of u is equal to size of subtree of v (in opposite directions) or basically s[u]=n-s[u].

    Now all you have to do is remove an edge from u and connect it to v and only 1 centroid will remain

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve idleness limit exceeded for problem E? Please help in this solution — https://codeforces.me/contest/1406/submission/92639473

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Did anybody else did o(10^5) solution for b?

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

    Yeah but after 4 wrong submissions ;(

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

    My solution has $$$O(n\cdot k)$$$ time complexity; in this case $$$k = 5$$$, so final time complexity is $$$O(n)$$$.

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve E? I got to finding out all prime factors (and their powers) except one. There can only be primes with power more than 1 until 317. Until 317, we check all powers of each primes < 10^5. For primes higher than this, it can be a factor with at most one power. We can iterate through all primes from here and apply operation B. We also keep track of how many more multiples must be remaining at this point. If it differs, we know that this must be a factor (and something else). If we continue iterating all of them, we get all the prime factors (and their power is 1 as explained) except the first prime number.

I couldn't figure out how to get this one. Can anyone solve the puzzle? :)

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

    I think we can group the primes greater than 317 into like groups of 100. After every 100 operations of the form "B p" we can do an "A 1" to check if the number of elements in the set has decreased by less than 100, in that case we know one of these primes is a factor of x and we go back over the group and perform an "A p" operation for each prime p in that group. I realized this in the last 5 minutes but didn't have time to fix my code :(

»
4 years ago, # |
Rev. 2   Vote: I like it +16 Vote: I do not like it
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry for the problem being well-known. None of the testers knew this problem before. (In fact B used to be exactly the same as abc173e, but to make it easier we chose k=5). We're really sorry for it.

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

      thank you for this task, I didn't know how to solve it, and now I know

»
4 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

For D is this correct — $$$result = max(a_1 - x, tot + x)$$$ where $$$x = (a_1 - tot)/2$$$ and $$$tot = sum(a_i - a_{i-1}) $$$ $$$if$$$ $$$positive$$$ ?

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    My idea that passed pretests was $$$sum = a_{1} + tot$$$ and $$$result =\frac{ (sum + (sum \ge 0)) }{2}$$$ (basically ceil division of $$$sum$$$ by $$$2$$$. What is $$$t$$$ in your notation?

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

    I didn't solve it in-contest but I think you can compute the minimum gain of sequence B and minimum decrease of sequence C by computing the sum of all rising edges (for B) and the sum of all falling edges (for C).

    The max of the two sequences is the start point of C or the end point of B. So we can shift up or down the entirety of B and C to find the point that equalizes those two points as closely as possible, which should be the optimum.

»
4 years ago, # |
  Vote: I like it -7 Vote: I do not like it

CopyPasteForces

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

    Really sorry for problem B. Still we hope you have enjoyed this contest.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Out of curiosity — is there some nice observation about the changes on both ends that allows D to be solved without using lazy prop for the range updates in the queries?

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can anyone tell what is wrong in this code. for B. Link:- https://codeforces.me/contest/1406/submission/92640232

»
4 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Can anyone tell me what these numbers mean? I have never seen them before.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Probably number of tests

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

      Is this a new feature?

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        Probably YES, but it was previously available on m1.codeforces.com(or m2,m3).

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    This number tells us the number of pretests in this contest

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    The number of pretests. I think you could use it to measure if your solution was good enough. A good feature to possibly prevent system test failing imo.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Am I correct in my logic for E?

I first find all primes upto n, then print each of them with a 'B'. After this round of operations only two integers, 1 and x if x != 1 should remain or only 1 if x = 1.

Then I print out each of the primes with 'A'. If I get 1, then i try its powers till i exceed n or get a 0. At each of these steps, if i get 1, I multiply the ans with x.

I think that this should be enough but this fails pretest 2. Can someone please point out why logic falters?

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

    Number of request is about 2*PrimesUptoN which exceeds the given limit for N = 10^5.

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

      My bad, I googled number of primes less than 10000 instead of 100000. I feel so silly right now

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

    This solution will fail since we can't make more than 10000 operations. This will work only if we are allowed to make ~20000 operations.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    There are 9592 primes <= 100000. Thus, doing two questions per each one exceeds the limit.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When E seems to be easy than D, but that constraint You can perform the following operations no more than 10000 times made it quite tough to solve.

»
4 years ago, # |
Rev. 2   Vote: I like it -37 Vote: I do not like it
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Bruh...

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +65 Vote: I do not like it

    Sorry for this, we had $$$k=3$$$ and find this in the last hour and we don't have other problems, so we just changed $$$k$$$ to $$$5$$$ so you can't google it, and that's the reason for delaying. Sorry again.

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

      And you guys still managed to create strong pretests for B!

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem A, did the text change in between the contest? I think initially the problem was to split the set into two equal halves!

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Thanks to KokiYmgch for "The way to find the centroids of a tree"

https://codeforces.me/blog/entry/57593

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

For Problem E I think we can group the primes greater than 317 into like groups of 100. After every 100 operations of the form "B p" we can do an "A 1" to check if the number of elements in the set has decreased by less than 100, in that case we know one of these primes is a factor of x and we go back over the group and perform an "A p" operation for each prime p in that group. I realized this in the last 5 minutes but didn't have time to fix my code :(

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is problem B solved by sorting the array and then using it like circular array by doubling its size by copying first half to 2nd half and use a sliding window of width 5 and find the max product? I Couldn't submit in time.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please help me to figure it out why this solution 92602531 for problem B is giving the wrong answer for case 1 and exactly the same solution runs correctly on other IDE (CodeChef and my own local IDE)

I thought there may be issues with my current compiler version but after trying it with different versions, it stills gives wrong here but it runs correctly in other IDE's

»
4 years ago, # |
  Vote: I like it -59 Vote: I do not like it
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    bruh it is not a reason

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -13 Vote: I do not like it

      Many of my friends and other participants solved B in 3 minutes as it is a very famous interview problem.

      It was kind of unfair with the participants who haven't solved the question before.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        Even if you know, there is a solution on gfg, you should try it yourself during the contest. Forget about those who copied from gfg.

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

        That is the case for all problems, and the reason why it is a good idea to practice a lot.

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

    "pLeAsE MaKE iT uNrAtED"

»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

E was cool! Thanks

But i am actually not understand why we need answer on type B query...

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

    How to solve it?

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 4   Vote: I like it +6 Vote: I do not like it

      There are abut 9600 primes <= n, and about 70 numbers <= sqrt(n).

      Let me name prime number which <= sqrt(n) as small and >sqrt(n) as big

      And actually there is 0 or 1 big number in X factorization.

      We can understand small primes in X factorization using about 200 queries (asking A queries about p, p*p, p*p*p, ...)

      And how to understand is there a big prime? We can arrange all big numbers on 100 groups of 100 numbers. Lets check every group separately using B queries and after checking it ask A(1) to understand was bg prime found or not. If it was found check this group again.

      It will be like 200+9550+200=9950 queries

      Sorry for my bad English ;(

»
4 years ago, # |
  Vote: I like it -10 Vote: I do not like it

Best channel for editorial of this contest . https://www.youtube.com/channel/UCBStHvqSDEF751f0CWd3-Pg/ Do view and subscribe

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How to run interactor & solution for an interactive problem in terminal/cmd?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I tried solving B with multiset can any one tell me why am I facing TLE. Worst complexity is O(n * 2logN). Submission

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    Why? You iterate from 2 to $$$n-1$$$ and inside you iterate over all positive numbers. It's $$$O(n^2)$$$

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

      My approach was to for every i from 2 to n — 2, find the max, min product of two numbers before ith and max, min product after ith of two number. Then multiply them accordingly based on the value of element i. I did not understand how it is O(n^2).

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it +1 Vote: I do not like it

        Because at $$$i = 2$$$ you iterate all positive numbers ($$$solvemin(muls)$$$). At $$$i = 3$$$ you iterate all positive numbers except maybe one. At $$$i = 4$$$ you iterate all positive number except maybe two and so on.

        And besides you pass multisets by value. So you at each step copy multisets.

        P.S. Yes I see now that you iterate at max over two numbers. So copying multisets is you main problem.

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

          In solvemin(muls) I am breaking after I get two numbers from the multiset.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem C — if there are two centroids then we disconnect the leaf of 1 centroid and connect it directly to the other centroid. How does this not works ?

»
4 years ago, # |
Rev. 3   Vote: I like it +40 Vote: I do not like it

My approach to problem E:

$$$Ans=p_1^{k_1}\cdot p_2^{k_2} \cdots$$$.

For $$$p \le \sqrt{n}$$$, just ask their exponents directly. This costs about $$$180$$$ queries.

For $$$p \ge \sqrt{n}$$$, there is at most one prime factor. So remove $$$\sqrt{cnt_{primes}}$$$ primes in one time and check if the number of remaining numbers is wrong. If wrong, the factor is in the last $$$\sqrt{cnt_{primes}}$$$ numbers you remove.

There are $$$cnt_{prime}+2\sqrt{cnt_{prime}}+41+66\times 2$$$ queries at most. The time complexity is $$$O(n \ln n)$$$. Since the system test isn't finished, I don't know if it's correct.

edit: passed system test.

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

    So you would ask the exponents in a descending manner? Like for example $$$2^{19}$$$, $$$2^{18}$$$, ..., $$$2^1$$$, and see if one of them matches?

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it +5 Vote: I do not like it

      Asking in increasing manner is better (i guess). A number $$$n$$$ can be written as the product of at most $$$log(2, n)$$$ prime factors ($$$<20$$$ for $$$n=100000$$$), which means you will stop at the first query for most of the primes.

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

      You can also binary search on exponent. But it isn't necessary here.
      Ascending or descending anything is fine.

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

    Ive done the exact same thing but ive get WA(i checked it it was because of the number of queries) and cntprime is around 9700 right!?

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

      There are 9592 primes exactly. I think 408 queries are enough to do other things.

»
4 years ago, # |
  Vote: I like it -66 Vote: I do not like it

make this round unrated as B problem's code can be easily found,here are the links-> https://www.geeksforgeeks.org/maximum-product-subsequence-size-k/ https://atcoder.jp/contests/abc173/tasks/abc173_e https://www.codechef.com/problems/MMPROD

all those who have copied these code or have taken the logic from there are at an edge ahead of those who are solving problem honestly

Unrate this contest

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is LONG_MIN not defined in codeforces?

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

    $$$#include <climits>$$$

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

      I had included this header

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

        So you can use LONG_MIN. Show submission where you cannot use it?

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

            Its compiling, its just WA

          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
            Rev. 4   Vote: I like it 0 Vote: I do not like it

            $$$LONG\_MIN$$$ is minimum for $$$long$$$ type
            $$$long$$$ type is signed type that at least same size as $$$int$$$. $$$int$$$ type is signed type that at least 2 bytes.

            Sizes of that types are different between compilers. So maybe you want use fixed size types.

            If you want minimum of 8-byte signed type. You should use i64 and $$$numeric\_limits<int64\_t>::min()$$$ or $$$INT64\_MIN$$$

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

            Try LLONG_MIN

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

    I think LONG_MIN is same as INT_MIN on codeforces, because one time I was getting wrong answer using LONG_MAX and had to change to LONG_LONG_MAX

»
4 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

am i the only one who printed "1 2\n1 2" if there is only one centroid in C?

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    that doesn't necessarily work because edge 1 — 2 may not exist in the input tree

    a solution is just to save an edge from the input and output that one instead

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

    same , cost me 4 wrong answers.

»
4 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Is it possible to solve prob/B with dp ? Thank you for your responses but is there a recurssive dp solution ?

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +14 Vote: I do not like it

    Definitions:

    • $$$mx[i][r]:$$$ max product of $$$r$$$ numbers in the prefix $$$1...i$$$.

    • $$$mn[i][r]:$$$ min product of $$$r$$$ numbers in the prefix $$$1...i$$$.

    Now, the transitions:

    • $$$mn[i][r] = \min(mn[i-1][r], \ mn[i-1][r-1]\cdot a[i], \ mx[i-1][r-1]\cdot a[i])$$$.

    • $$$mx[i][r] = \max(mx[i-1][r], \ mn[i-1][r-1]\cdot a[i], \ mx[i-1][r-1]\cdot a[i])$$$.

    Now, base cases:

    • $$$mn[0][0] = mx[0][0] = 1$$$;

    • $$$mn[0][r] = INF$$$ and $$$mx[0][r] = -INF$$$ for $$$r \neq 0$$$;

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.me/blog/entry/57593 By just applying this links code to tree C problem can be solved

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

    What's next after finding the centroids of the tree using the code in the tree? The problem isn't solved yet!

    Finding the centroids are just a helping tool and not the full solution

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

      If $$$N$$$ is odd, is it always the case that the answer is printing a random edge twice (unique centroid)? Can anyone help me in proving that or hacking my submission?

      I have tried to find a sub-tree of size exactly $$$N / 2$$$ if $$$N$$$ is even.

      My submission: 92627903

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Indeed if N is odd, there can be only 1 centroid. Thus printing a random edge twice is valid.

        Then finding a subtree of size N / 2 if N is even, is also correct. Since those are the only nodes that satisfy sz[node] >= N / 2 and N — sz[node] >= N / 2 -> node is a centroid.

        Congratulations! Your solution is correct!

        (I might be wrong though feel free to correct me)

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

      IMO the tricky part of the solution is to find the centroid as after finding centroids we can remove any subtree from one centroid and connect it to the another centroid

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

        And do you have proof of that? Does it always work?

        You may have found that as intuitive, but many others don't

        The problem tests you if you found that property, not testing you how to find centroids

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Yeah applying this code gives you AC but only "JUST" applying wont get you anywhere ,this is the basic difference between having a particular tool and knowing where and how to use it.

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

In problem C, how can we prove that there can at max 2 centroids? I took this as an assumption (based on observation) and fortunately it turned out be correct.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +9 Vote: I do not like it

    This is my personal proof for this. Correct me if I'm wrong.

    Proof: assume that there's k > 2 centroids. Then, those k vertices should be connected by (k-1) edges (since they should form a tree). But because by Pigeonhole Principle, at least 1 vertex will certainly get 2 or more subtrees (from the other centroids). Then the centroid would be that vertex. Contradiction.

    Hence, the number of centroids should be at max 2.

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

      Sorry to ask, in your proof why do the k vertices needed to be connected themselves (i.e. connected by k-1 edges)

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

        If two centroids vertices are connected via a non-centroid vertex, then it would be more optimal to take the non-centroid vertex as the centroid rather than the initial ones.

        Probably it would be easier to visualize it by drawing some (possibly random) trees.

»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

So thanks for the nice constest feecIe6418, and now you may come up with the turorial.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I love problem D so much and thanks for this wonderful contest!

By the way,E is really hard...maybe I will try it later.

Difficulty gap: A<B<C<<D<<<<<E

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +35 Vote: I do not like it

    I don't think that's objectively true though. By solves, D was about 5x harder than C, and E was about 5x harder than D. It seemed to be about perfect actually. Perhaps D is right on the edge of what you are usually able to solve in contest which might explain why you liked it so much and thought E was so hard?

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Well my graph theory skill is not very good so solving C cost me a little time.

      But about problem D is right on my edge,I think I can solve harder problem but this problem is hard to think,easy to code.

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

      Yes, D is really hard for me at least to come up with maths behind it. But loved the problem D.

      I didn't read E though.

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

      D wasn't that tough tbh

»
4 years ago, # |
  Vote: I like it +32 Vote: I do not like it

Thanks for the cool problems! I've got video solutions to everything at the end of this if you're looking for them since the editorial isn't out yet :)

  • »
    »
    4 years ago, # ^ |
      Vote: I like it -22 Vote: I do not like it

    Thanks for your effort . Following things could be improved :

    1. In problem E's explanation , you have written "to make sure x is a big prime" . No x is an integer and may not be prime . 2.In problem E , you told we will take 1 extra query , what will be that extra query ? And how it will help knowing if prime is big/small or lies in the bucket .

    If you just explain that briefly , to be honest it's no better than editorial .

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

      I explained it pretty clearly I think. There are two cases. The first is the one in which x is a big prime. In that case you handle it with bucketing the primes. The other case is when x is not a big prime: it has at least one factor smaller than sqrt(n). In that case, you will see that there are more multiples of the big prime than there were suppose to be, so you can deduce that that prime is a factor of x when you see that.

      You can check which case you are in by querying "A 1" after the first sqrt(n) queries.

»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Where is the pre-prepared editorial ..
I need help on C,D.. can any one give me easy hnts of C or D please.

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

    The max possible number of centroids. (hint for C)

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I solved B using DP using 3 parameters the index of the current element 'idx', remaining elements 'rem', and the sign of the product till index 'idx', if neg is 1 meaning '-' otherwise '+'.

It seems the complexity of the solution is O(n*5*2) but still TLE.

Here the link of the solution: https://codeforces.me/contest/1406/submission/92647209

»
4 years ago, # |
  Vote: I like it -10 Vote: I do not like it

The constraints given in B. Maximum Product are wrong. it doesnt work if you take t as int and n as int and a[i] as int. Gives overflow. whereas it should not give overflow according to given constraints in the question.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    It would be overflow. In the worst case, you need to take $$$(3 \times 10^3)^5 = 243 \times 10^{15}$$$, and that wouldn't fit in int.

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

      but n and a[i] dont need to be long long int, only ans needed to be long long int

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

        It's your job to see and adapt to the worst case...

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

          int wouldve sufficed for n and a[i] according to constraints is all I'm saying, then what was the point of constraints even.

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

            What even? The constraints are correct. They specify what input you can get. Use your own discretion to realize what size integers you need based on what you actually do with the numbers.

            Would you be angry with the constraint n <= 80 if the task is to return the nth Fibonacci number?

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        Consider the following C++ psuedocode

        long long int ans = 100000 * 100000

        Even though 100000 * 100000 should still fit in long long, but 100000 * 100000 will overflow since their data type is still int

        To counteract this:

        long long int ans = 100000ll * 100000ll

        It can be applied to variables as well like:

        long long int ans = x * 1ll * y

        With this, the value will not overflow

        changing everything to long long gets ac, my bad

»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

in C I think if tree has 2 centroid then they must have edge between them or they are adjacent...can anybody prove this wrong..

»
4 years ago, # |
Rev. 2   Vote: I like it -14 Vote: I do not like it

I liked the contest

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    mmm, I liked the contest. Also, why do you say just math?

    • problem A was an easy ad-hoc problem.

    • problem B just needed very basic stuff of math, and then it just was Brute Force or even Dynamic Programming.

    • problem C wasn't math. It was graph theory.

    • problem D maybe was math, but it could be solved with data Structures.

    • problem E was math, and it could be solved by using some nice ideas like SQRT Decomposition.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why I got 5 times WA for problem A and got AC with same code afterwards without changing anything ?

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    if(mp[x]>1)

    if(mp[x]>1 and mp[x]%2==0)

    are they same?

    update: your mex function is not correct, for example in the first case a.size() is only 3 but you'll visit a[3], so you may get a wrong answer sometimes.

    you can change it to

    for (ll i = 0; i < a.size(); i++) { if (a[i] != i) return i; } return a.size();

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

      They aren't same.This was actually my bad.but I got AC with almost same as first code I wrote. And I was getting right output in my editor but got wrong in the judge for the given test case.

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

        Sorry, I have some mistakes on your code. I have updated the reason why you may get WA in my last reply.

»
4 years ago, # |
  Vote: I like it +46 Vote: I do not like it

To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

In B Just because of 3*10^3 I was not able to solve. I have assumed min as -1e16 instead of -1e19. I think the most important thing before solving a problem is reading it carefully.

»
4 years ago, # |
  Vote: I like it +36 Vote: I do not like it

Editorial:https://codeforces.ml/blog/entry/82560

tianbu has already gone to bed and I don't have the access. So wait until tomorrow to see the Editorial on the announcement.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone tell me why my code is givin runtime error on test case 3 in python.

https://codeforces.me/contest/1406/submission/92659527

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Wasn't the editorial already written ? xD

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem 1406C, the center of mass of a tree has an important property that a tree has at most two centers of mass, and the two centers of mass are connected.

According to this property, when solving the problem of 1406C, if the data given has only one center of gravity, it can be solved only by deleting and adding the same edge.

If the data given has two centers of mass, we break a subtree of one center of mass and connect it to the other center of mass, so that the other center of mass becomes the only center of mass.

For finding the center of gravity of the tree, I used one of the templates in CSDN (a Blog from China), This blog post was published on August 19, 2016.I used most of the code in question 2 and only changed it in the final output.

link: https://blog.csdn.net/qq_35866453/article/details/52254234?utm_source=app

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In my opinion, code style of the editorial is awful.sorry. By the way, nice problems.

»
4 years ago, # |
Rev. 2   Vote: I like it +19 Vote: I do not like it

1406B - Maximum Product is basically the extension of this problem : https://www.geeksforgeeks.org/find-maximum-product-of-a-triplet-in-array/ logic is pretty much the same

1406C - Link Cut Centroids seems to be very well known, lol, I spent 30 mins in proving that there can be atmost 2 centroids in a tree, had I resorted to googling "centroid of a tree" I may have got it immediately, you could have atleast changed the name "centroid" to some random thing like "good vertex"

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could anybody explain why is my solution of B is wrong? If there are enough, we can take even amount of negative elements(most minimum) and 5 — cnt_negative of positive. this is my code https://codeforces.me/contest/1406/submission/92591345 thank you.