vovuh's blog

By vovuh, history, 6 weeks ago, translation, In English

Hello! Codeforces Round #677 (Div. 3) will start at Oct/20/2020 17:35 (Moscow time). You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 (or 8) problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

  • take part in at least two rated rounds (and solve at least one problem in each of them),
  • do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Daria ZeroAmbition Stepanova, Mikhail pikmike Piklyaev, Maksim Ne0n25 Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round. Also thanks to Artem Rox Plotkin and Dmitrii _overrated_ Umnov for the discussion of ideas and testing the round!

Good luck!

UPD: Thanks to infinitepro, sladkayaKlubnichka, MrReDoX and Peinot for testing the round and giving the feedback about the problems!

UPD2: Editorial is published!

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

»
6 weeks ago, # |
  Vote: I like it -37 Vote: I do not like it

vovuh orz

»
6 weeks ago, # |
  Vote: I like it -27 Vote: I do not like it

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Does this mean working in teams is allowed since ACM-ICPC is a team contest.

»
6 weeks ago, # |
  Vote: I like it -79 Vote: I do not like it

is it rated?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it -41 Vote: I do not like it

    It is mentioned clearly in bold. Rated for users havin' rating less than 1600.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Understand the sarcasm bro he is a cm with 2 year experience

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

        I know but now a days this question is the source of decreasing contribution.

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

          If i hurt you then please forgive me

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

            There is nothing to get hurted. I be happy with Coding.

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          This is a vintage question bro

  • »
    »
    6 weeks ago, # ^ |
    Rev. 4   Vote: I like it -34 Vote: I do not like it

    Not for >=1600

»
6 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Any idea why are problem ratings not getting updated for the past three contests?

»
6 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

imagine 8 problems for a div 3 ...

»
6 weeks ago, # |
Rev. 3   Vote: I like it +17 Vote: I do not like it

About 50 minutes after this announcement was published, the user System_2020 posted a fully copied text of it. Unfortunately, it is only in Russian. However, he almost immediately replaced it with just a call to participate in the round. But still, it was really strange.

»
6 weeks ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

Vovuh rounds are best to learn math, implementation and constructive for a beginner like me as I can hardly solve up to D in Div 3 rounds.

»
6 weeks ago, # |
  Vote: I like it +118 Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

did you decide to bring in the problems from the next div3 contest to this coming one ? cuz there are eeeeeeeeeeeight problems ! o_o

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Our beloved Vovuh is back to us.

»
6 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

I will try my best to solve problems even though i suck at this, i wont give up i believe that i can improve :).thank you for this div 3 rounds

»
6 weeks ago, # |
  Vote: I like it -32 Vote: I do not like it

![ ](IMG_20200928_122319.jpg)

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

    meanwhile couldn't increase rating in my last 3/4 div 3.. :(

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    Why this comment is getting so many downvotes?

»
6 weeks ago, # |
  Vote: I like it +93 Vote: I do not like it

Note that the start time is usual.

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

    I first read it unusual and scrolled up to verify the timings..got confused..came down and then read it correct.

»
6 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Has it been confirmed anywhere that the number of problems in the contest is 8?

»
6 weeks ago, # |
  Vote: I like it +82 Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it +48 Vote: I do not like it

[]memem.png

»
6 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Please this time wanted SHORT statements and a STRONG pretests for DIV3!! Interested for the contest hope to get expert this time (done lot of practice indeed) !!

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Too ambitious to be true

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    See you on the other side.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what is meaning of pretest ?. have been encountering this for a while but don't exactly know what it means.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      several testcases that are used during the contest, they are usually less than the original testcases, I think they do that in order to reduce the queue time

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello everybody, I have a question that might seem ridiculous to you but as I am still a pupil I think it is ok to ask it. When inputs are like 4 3 2 4 6 2 7 9 4 and 1 2 3 4 Should I use cin differently? I mean in the first, there is a number in first line, and then 4 numbers in the other lines, but in the second one there is only one input number in each line. Thabk you in advance for your help.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The comment did not share well. but it is like the first line: 4, second line: 3 2 4 6, third line: 2 7 9 4. and the other one, first line: 1, second line 2, third line 3, and etc.

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

      Above the editor box are some icons, try them, they wont bite you. Look out for "Block" and "Inline".

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

      no you can use cin as it is, and you can also verify it by actually trying it out

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

        I do not want to give unecessary pressure, but you know you are expected to make a big jump back to blue today, don't you?

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

          yep, that's why I initially decided to not attend,because of pressure,then I thought chuck it!Iam in

»
6 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

Wait !! I also want to be a tester. Someone knows how it is possible ?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

8 problems. GG

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

26 minutes left time to be ready : )

»
6 weeks ago, # |
  Vote: I like it +22 Vote: I do not like it

Are these tester comments trendy presently?

Either way, here are my views on the contest.

  • Balanced.
  • Interesting problems.
  • Not implementation heavy.
  • A bit on the easier side, compared to previous div3 contests by vovuh.

Nevertheless, a fine problem set for a div3. Good luck and have fun!

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck everyone

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

i am a new guy to this platform

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Will solutions judged again after contest finised?

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

How can a participant be a trusted participant ? because on contest it shows me in unofficial standing ? and i'm just a newbie

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you need to take part in one or two contests to become a trusted participant.

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

      @waltz47 Oh thanks , by contest you mean div.3 or anyone thanks again!

»
6 weeks ago, # |
  Vote: I like it +68 Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

Hope this round will remain rated :)

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Sigh. I solved A and B in under 12 minutes but couldn't solve C in the next 2 hours. There must be something wrong with the way I am practicing.

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

    I used to be really bad for the first 2 months, today I solved 5 problems so don't give up and keep practicing. Unless you're doing problems below your current level, there is no wrong way of practicing.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes. Same with me. Solved A and B in 10 min and got stuck on C because of run-time error. This makes me sad now.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Shit happens. Don't worry. I solved A and C but couldn't B and D in the next 2 hours. (In C, one possible solution is printing the maximum value of the array such that atleast one adjacent element is smaller than it.)

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

    Meh, it happens, there are days where I fail to solve problems rated 200-300 below my current rating in contest. Don't be troubled by it too much. Rather analyze where you went wrong and what you can do to improve on it in the future.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah I coudn't solve B and C at all after solving A in the first 5 minutes. For B i kept on trying to simulate the process but kept on getting WA. Is there a better way and are there other questions that are similar to B?

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

      My solution to B was just (the spread of the ones)-(the number of ones) assuming the ones are not already stuck together. Eg: For 0010101, 5 — 3 = 2.

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Why is this true?

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

          I'm not sure about a formal proof.

          However, if you imagine an actual horizontal grid with books as in the question and exclude the outer zeros, the number of moves required boils down to how much you can compress the span of books. Also, its always optimal to move a block of ones together instead of one at a time.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am little new to CP, but what I have learnt is not to give up. If you don't get it now, try hard later, repeat, still didn't get it, see the editorial's first line, then try to code, still stuck, see some more editorial, still stuck then see full editorial, still stuck, just try to understand the solution code and after 2-3 days try to code it on your own.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope Mike won't plag me today again xD.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What about D & E

was for solving D any knowledge of graph theory need??

and what is the procedure of E

any one tell me please the procedure of this two problem.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    E was simply (C(N,N/2)*((N/2 — 1)!)^2)/2 AND FOR D no just make a star graph.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i don't have any knowledge about graph that's i ask is there any other process to solve that

      would please explain E to me?

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

        See number of ways to pick N/2 people is C(N,N/2), where C is binomial coeff. Now to arrange them in a circle such that each time a different circle is formed is given by standard formula of circular permutations which is (no of objects — 1)! Here no of objects = N/2 and since there are 2 groups both of them get multiplied to get total number of ways hence a square in the factorial term. Now multiply this with our C(N,N/2) and you are almost done! Also you need to divide by 2 since you also chose the reverse order in the process.

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

        For D you can make a star graph by connecting all the non equal elements wrt center of the star.... to the center of the star and now only the elements having value equal to number in center of star remain. Connect these elements to the to any other vertex of the star other then the center and you are done. Answer is always YES if atleast 2 distinct elements exist.

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

      Tbh, I kept trying different formulas and got $$$\frac{2^n}{\frac{n}{2}}$$$

      Edited: See comment below.

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        What is that? Its not even true for n=2

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Oh sorry, I probably need to sleep now. My correct formula was $$$\frac{(n-1)!}{\frac{n}{2}}$$$

          • »
            »
            »
            »
            »
            »
            6 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            hahaah ok...yeah it is a direct simplification of what I wrote above..nice.

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

    I was thinking of a birpartite graph with coloring, but it wasnt, just search for a pattern.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      For D you realize that you can group graph vertices into components based on their entity/number assigned to them. You can then number each group and join only one element of each group with each element of the group that comes after. This way all the elements of next group are reachable one from another.

      Say you have groups 1, 2 and 3. You join first element of 1 with all elements of 2 and join first element of 2 with all elements of 3. Finally join all the elements besides the first one in the first group with first one of the second group. Why? So that each vertix of first group is reachable from any other.

      The only base case is when there is one color, then there exists no answer.

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

    D: Knowledge of bipartite helps in a way. If all numbers are same then answer is NO else YES. Then you can join first node to all nodes which don't have value a[1]. For other nodes having values a[1] connect them to any one of the nodes having value not equal to a[1].

    E: I just did OEIS. Too weak in maths. ;_;

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For D if all of the districts belong to the same gang it can't be done, otherwise pick two districts with different gangs then iterate over all districs and connect them district to the picked district that has a different gang of the two you picked earlier

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

anyone else solved E using OEIS?

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

    Problem E

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Did you?

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

    I was tempted to but the derivation was actually pretty easy.

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

    When I'm given a number like n=20 is 12164510040883200 I just can't resist going for OEIS. Never even read the problem, I just went directly for OEIS 96121869.

    Then Codeforces kept showing me popups over and over about announcements about issues with the problem description. My secret to success was to never having read the problem description in the first place xD

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How do you search in Oeis? You just put 12164510040883200 in the search bar then choose first result that comes? or what?

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I just searched for 1260 12164510040883200 and scrolled down until I found what I was looking for (the sequence in E turned out to be the 2nd search result).

        You can read about different ways to do searches here. You can do for example this (shows all sequences containing 1,3, 1260 and 12164510040883200) or this (searches using wild cards).

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it +13 Vote: I do not like it

          Lol. The sequence you used is "Complexity (number of maximal spanning trees) in an unoriented simple graph with nodes {1,2,...,n} and edges {i,j} if i + j > n" which has nothing to do with the problem, but just by coincidence happens be described be the same explicit formula for even $$$n$$$.

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I tried searching with this 1,3,1260,12164510040883200 but it shows no result. Help please

          • »
            »
            »
            »
            »
            »
            6 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Comma seperation means you search for exactly 1,3,1260,12164510040883200appearing in the sequence (in that order with no numbers inbetween).

»
6 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

This contest is a nightmare for higher specialists, many solved 5 still their rating will decrease.

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    Yeah, it was a nightmare but we can jump back in next contest right?

    Good Luck for next round

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

      yesss...

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

        When your Spanish teacher calls on u 10 times in the first thirty minutes of the contest even though u never raised ur hand. Tough.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone know? Which formula is answer of E problem?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    ((n-1)!)/(n/2)

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    $$$(n-1)!/(n/2)$$$

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

    It is "(N-1)! / (N / 2)" but I have no idea why

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      As me :)

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I just found out that half of people did it with OEIS, how could I have forgotten...

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Same here, I know OEIS but I also forgot.. Just kept scratching the paper.. lol

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      See number of ways to pick N/2 people is C(N,N/2), where C is binomial coeff. Now to arrange them in a circle such that each time a different circle is formed is given by standard formula of circular permutations which is (no of objects — 1)! Here no of objects = N/2 and since there are 2 groups both of them get multiplied to get total number of ways hence a square in the factorial term. Now multiply this with our C(N,N/2) and you are almost done! Also you need to divide by 2 since you also chose the reverse order in the process.

      Sadly I got this right 3 sec after contest ended...I hate OEIS.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    (N!)/(N*(N/2)).

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it +11 Vote: I do not like it

    ll ans = nCr(n, n/2) * pow(fact((n/2 )-1), 2)/2;

    First calclulate number of groups possible (of half members each) by nCr(n, n/2), then use formula of circular permutation i.e. (n/2 -1)! to find number of ways to arrange people in a group. (n/2 -1)! * (n/2 -1)! would give the ways for both group. Now divide the product by 2 as there be would be possibility of group A,B and B,A.

    eg. n = 8 , ways to make group of equal people = 8C4 = 70 AND ways to arrange people in one group = (4-1)! = 6 AND ways to arrange people in 2 groups = (6 * 6)/2. Final answer = 70 * (6*6)/2 = 70*18 = 1260

    edit: And we can simplify this to the formula many people used, although I took too much time in D and could not submit E in time

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      LOL used the exact same thing and happened the same exact way...3 sec after contest ends...AC xD.

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        and I got this idea 3 minutes before end of the contest ;)

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

What were the solutions to F and G?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Accepted Accepted Accepted Accepted

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

If Div3 is a contest in which we'd like Div3 participants to solve the entire set, this seemed like the perfect one.

I dislike problem E because it felt easier than B (to me and maybe others too considering the number of solves). F seems pretty easy if the constraint of M/2 is omitted and we're supposed to find maximum sum divisible by K in each row. How do I stay within the constraint? I'm thinking 3 state dp maybe. Any ideas on how to solve G?

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

    For F, it is simple to reduce that difficulty in your idea, do an auxiliary dp for only col counting the state for checking M/2. Extract optimal and use it to update main dp.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I looked up your solution after you posted the "Why would you give a problem...." comment. It's very elegant. Understood, thanks!

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

First time solved 5 :) and spend 1 hour in F but not able to get AC.

»
6 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

I think the tests in Problem F are weak as printing the maximum sum minus (maximum sum) % k is giving Accepted.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How is second test case for G giving 13 ??? shouldn't it be 16 by reducing edge (2,3) to zero????

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

    They took a path which wasn't in any of the shortest routes. After making it 0 it became a part of the shortest routes.

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

$$$E$$$ — OEIS

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can someone tell me how to use OEIS, especially when I don't know the whole sequence(contigous sequence) of numbers.

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

      for this problem, they gave the answer for 2, 4, and 8 so I just find the answer for 6 manually and then search that series on Oies.com, it simply gave me a formula which gave me AC

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Use underscore, like for the given problem you can search something like 1, 3, _, 1260.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why would you give a problem like F in a serious contest?

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

    To be fair I don't think any significant number of participants < 1600 rating would have come across the idea. Anyway Div3s are fairly educational in nature, E / F is often a problem which can easily be condensed to a standard idea.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah, but F should not be solved by 250+ peoples if we see the other div3s. And yeah, it was educational. I was getting struck in implementation with fake updates cause I initialized everything with 0. Probably that's why they put it in F.
      But, a lot of people dance between blue and cyan so this probably gives unfair advantages to them.

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah fair enough, maybe the idea is more common than I realize. I just felt that way since I didn't actually come across this idea till I was around 18-1900.

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

Can anyone tell what's wrong in my code for D?
my approach: if all elements are same, then answer is NO,
else find the min element index, find the max element index. bring the min element to first index, and then print from second index with following condition.
if arr[i]!= minimum element print i min_index (i.e. i 1) else print i max_index
UPD: got it. I was changing index's value.

»
6 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

There is always a problem which doesn't allow to increase rating. This time it is F.

»
6 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

I want to know if anyone bothered to simplify the answer of E to (2*(n-1)!)/n.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can't simplify it further. It's a factorial. Maybe you could write the mathematical notation to make it look clean but that doesn't help programmatically.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I thought D is like, I have to arrange elements of an array such that no two adjacent elements are of same type using max heap. But don't know why that failed :(.

»
6 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Solved 3 problems for the first time, Is this round easier than usual or have I improved?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Both are possible, it was slightly easier this time, but it seems like it's been like that for the last 10 rounds or so, so it could be a bit of both.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    important thing is your rank.

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Search 12164510040883200 on OEIS, and you will find the answer in the first sequences of the searching result — A110468

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You could have simply chose to not post that. I feel incredibly stupid now as I calculated it for every n using the formula and wasted more than 30 min :facepalm:

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      A lot of people solved it by hand. There's nothing to feel stupid about it. I did it too (although I took only 10-ish minutes proving at 3-4 implementing). Although those who did search for it are at a slight advantage in the contest, it's insignificant over many future rounds. At least you were able to prove why the formula is correct and not blindly copy it from elsewhere.

»
6 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

It took an Eternity to understand E :(

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I read the announcements only 15 minutes before the contest ended :'(

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Great Contest Feeling sad for not solving E coudnt figure out the formula

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone solved the problem D using maximum spanning tree where weight = abs(a[i], a[j]) ?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You don't need MST @rds_98. Just see if there are atleast 2 distinct gangs. If yes, select the first index, and build a road with any district which has a different gang. Now select an index which is not equal to the first index and build a road for all the first gang districts with this road.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can solve D using basic concept of MST. Instead of using Priority_Queue, just a normal Queue will help you getting out of TLE. https://codeforces.com/contest/1433/submission/96110388

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone explain E?

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

    1- you want to know how many times you can divide n people into to n/2 teams. The answer is nC(n/2). But, for every time you choose a n/2 number, you leave another n/2 (aka you choose them too into a different team). So, the answer will be nC(n/2) / 2.

    to give a quick example, say n = 4. One way to choose 2 people is [1,2] (which leaves [3,4]). Another way is to choose [3,4] (which leaves [1,2]). They are both the same. So, we divide by 2.

    2- For every team, you want to know how many times u can rearrange it (without changing the members) to form a different team. this is basically (n/2)!. Realize also that every ordering will be repeated n times. for example, [123], [312] and [231] are the same. so, it's (n/2)!/n.

    So the answer is nC(n/2) / 2 * (n/2-1)! (how many times we can reorder the first team) * (n/2-1)! (how many times we can reorder the second team).

    I hope this helps.

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

      Yes now I understand. I was able to get the first part but could not find the number of possible arrangements in each team.

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

      One Correction

      2- For every team, you want to know how many times u can rearrange it (without changing the members) to form a different team. this is basically (n/2)!. Realize also that every ordering will be repeated n/2 times. for example, [123], [312] and [231] are the same. so, it's (n/2)!/(n/2). So, (n/2)!/(n/2) = (n/2 -1)!

      Correct me, If I wrong!

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Basic idea of problem C (atleast what I thought): The dominant piranha is not present if all elements are same. Whenever all the elements are not same, there will exist one or many piranhas with the greatest weight , one of these must have a neighbour which has weight less than maximum value ,that index is one of the answers. But my code gives wrong answer, Clearly there is a silly mistake in it , It would be helpful if someone could point it out my submission

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Someone explain solution for F pl.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I somehow get to manage the formula for E (only god know what logic I applied.. actually I tried to fix random factorials lol) but dont have a intuition for that. Can someone please help me with the intuitive proof for the same ?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please help me by telling that where my code is failing for B, I am unable to find it. Code

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

SS.png
How to submit all problems at the same time without a gap of even one second ?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You do all the problems and then submit all in 1 go. maybe a script can help you as well.

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

    Open 6 tabs and you can submit everything under 1 minute. Seconds aren't counted.

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

    There are various tools that allow you to auto-submit problems directly from your text editor / ide / the command line.

    Example — cf-tool]

  • »
    »
    6 weeks ago, # ^ |
    Rev. 3   Vote: I like it +9 Vote: I do not like it

    I think it is formatted as HH:MM.

    It is without a gap of even a minute.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      He is a red coder he can do anything ;)

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        If he solved it all in 1 min and 7 seconds, he would be first on the ranking.

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          No, only trusted participants in the ranklist

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how to do b?

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

    Number of zeros between first appearance of 1 and last appearance of 1.

»
6 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

too many people solved too many questions ;-;

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Just google searching the output to the last sample on E (n=20) leads you straight to https://oeis.org/A273878.

Getting answers from OEIS after typing out a series is alright, but with just one number, that too which is given in the sample, is not.

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

    I hate OEIS...I solved it with a smooth PNC method and got it right 3 sec after contest ended :(

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can I see solutions somewhere?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

please tell what is wrong with my solution it is showing run time error with exit cod=2147483647 https://codeforces.com/contest/1433/submission/96165473

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Authors tried hard so that formula for E do not reveal directly , but "a ninja must see through deception" :) . Nice problemset.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Amazing problems. Thanks to all the testers and problem setters for wonderful problems.

»
6 weeks ago, # |
  Vote: I like it -61 Vote: I do not like it

What an absolute stupid contest! No thinking, no DS, nothing. Just some stupid observations and you're good to go. Why do you even frame these type type of problems? Just say like — Print numbers from 1 to n. It will be a lot better to solve. Seriously, even Leetcode contests are better than these contests, atleast they require some thinking and implementation, and DS. But here, just put some if-else conditions in problem D which is supposed to be a good problem, and you're done! Absolute waste of time and effort.

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

    How can you say you didn't even participate in the contest?

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

      (Reminder) One can use multiple ids in cf.

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

    And how would you suggest they add ds without making the thinking part practically non-existant? Any even slightly tricky data structure will easily push the question over 1900 difficulty.

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

    You should participate in Div 1 ;)

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

E's problem statement was so confusing. Wasted 30 mins for me. They didn't make it clear if rearrangements in circle would be considered a different pair

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That's why it was "E". (Although today's E was easier than previous)

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

    In my opinion they made it perfectly clear in this statement.

    Two round dances are indistinguishable (equal) if one can be transformed to another by choosing the first participant. For example, round dances [1,3,4,2], [4,2,1,3] and [2,1,3,4] are indistinguishable.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the intuitive proof of E ?

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    There are cnk(n, n // 2) // 2 ways to split people into groups of size n // 2
    Now there (n — 1)! ways to arrange people inside each group

»
6 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

$$$F$$$ was awesome :).

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

    then please give me some insight to solve it, how you started thinking about it and how it end, please if you can

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

such a good div3 round !

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Likes AtCoder ABC(cf version) xD

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

in open hacking phase, is there penalty for Unsuccessful hacking attempts? if i hack someone, will i get points or something?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No

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

    No penalty. No points. You get a mention in the edits of this post if you are among the top 5 hackers.
    Edit — No mention about top hackers in Div. 3 posts.

»
6 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Problem E had only 19 possible inputs and you give 4 of them in the samples?!
I think Codeforces is advertising OEIS.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell why problem C is getting Hacked!? Where it is getting TLE?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

what is the solution of D?

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

    Maintain a count for how many cities are under a bandit gang and indices (using map preferably). Connect all other gang cities to one city.

    Example: [1,1,1,2,2,3,3,3,3]

    Counts: [1: 3], [2: 2], [3: 4]

    Now, connect all cities under gang 2 and 3 to one city in gang 1. For the two remaining cities under gang 1 (notice 1 city of gang 1 is already used up in previous connection), connect them to any other city distinct gang city. Implementation is simple.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

(2*n!)/n^2

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

Can someone explain me why this output gives WA for 1433D - Districts Connection in the first test case:

My submission : 96170947

I also didn't understand the verdict.

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

    1 1000. You have to print the index, not the values.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think you answered someone else's query in my comment :3

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

        No, I saw the participant's output for your submission, for 3rd case, it has one extra output line 1 1000, the checker was expecting a string "YES" and you provided space-separated integers.

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks man, got the problem. I was searching wrong in 4th test case.

»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
  • in problem c
  • How this test case :
  • 4
  • 7 1 4 3
  • is 1 not 3 ??
  • Test 2 (14)
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    1 and 3 is wrong answer

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The biggest piranha can eat all other piranhas. So 7 at index 1 can eat everything else. However, 4 at index 3 (what you say) can not because it will only get to size 6 after eating piranha with size 1 and 3 and it can't eat 7.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Initially the pirhanas are 7(indx1) 1(indx2) 4(indx3) 3(indx4).

    NB: don't be confused. 1st element's index is '1' not '0'.

    if your ans is 3 that refers to index 3, that means the pirhana of size 4 will be the last. But it will become 6 at its peak which is still smaller than 7. So ans will be for 7, so ans = 1.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    my mistake was that i increased the piranha by array[index] not by 1

»
6 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Felt todays contest more inclined towards fast speed rather than logic building :(

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yep, Div. 3 is hard for those familiar with OI mode contests (where speed doesn't matter as long as you get the points)

»
6 weeks ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

I am getting TLE in F. Can anyone tell me how to improve it?

Complexity of solution: n*m/2*n*m*max(a[i]) Edit: Link updated

Edit2: Used the above approach with modulus for removing unnecessary values and got AC and also complexity becomes O(n^4)

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

Can anyone give me the tutorial of F please ?? ACtually i need the explantion of any solution approach

»
6 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

My solution was hacked too :p :p

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why so many hacks in F? What is the hack case?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain why this solution for D gives wrong answer, I tried it on local, it gave the correct answer for test case 1, but on OJ, it's giving WA.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you explain your approach ? I am looking for other approaches to solve this one.

    My O(n^2) solution with DSU got accepted. here is is: accepted code

»
6 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Lesson from Problem F: Don't be greedy. Be dynamic.

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Test for problem F 2 2 4 1 1 1 2

ans = 0

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Yet another HackForces?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't quite understand question F. This is the code of WA in my game https://codeforces.com/contest/1433/submission/96164623 This is my AC code after the game https://codeforces.com/contest/1433/submission/96173437 The only change is that I changed MAXM from 70 to: int MAXM = (70 / k + 1) * (70 / k + 1) + 5; if (MAXM <140) { MAXM = 141; } Although there may still be a problem, it is ac for the time being. (I guess if MAXM is set to 4901, it will definitely be ac, but it will time out), I don't understand. According to my understanding, the total status will not exceed 70. How is this going? Is there any kind person to answer? Thanks in advance.

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

    I think I know why. maxm should be set to 35*(70/k+1), it can definitely be ac.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem G?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    Use floyd Warshall algorithm to find the shortest paths and then find min distance by removing a edge.

  • »
    »
    6 weeks ago, # ^ |
    Rev. 3   Vote: I like it +13 Vote: I do not like it

    First of all, lets just forget about setting the weight of an edge to zero for a second. So we want to find the shortest paths for all courier routes. Floyd Warshall might come to mind but $$$O(n ^ 3)$$$ is not likely to work here with $$$n \le 1000$$$. However we have an additional constraint on the number of edges, $$$m \le 1000$$$. So we can just Dijkstra from each node to get all distances in $$$O(n * m * log(n))$$$. Lets call these original distances $$$original(i, j)$$$.

    So now that we have these original distances lets get back to the main problem, how do we find the answer for setting an edge weight to zero? Well suppose we set the weight of an edge {$$$u, v$$$} to 0. Then for each courier path one of the following must be true:

    • The courier path doesn't use this edge, i.e., $$$d(a_i, b_i)$$$ = $$$original(a_i, b_i)$$$.

    • The new courier path is of the form $$$a_i - \cdots - u - v - \cdots - b_i$$$ or $$$b_i - \cdots - u - v - \cdots - a_i$$$. Since $$$original(u, v) = 0$$$, we get $$$d(a_i,b_i)$$$ = $$$d(a_i, u)$$$ + $$$d(v, b_i)$$$ or $$$d(a_i,b_i)$$$ = $$$d(a_i, v)$$$ + $$$d(u, b_i)$$$ respectively.

    We can just again use dijkstra from the vertices $$$u$$$ and $$$v$$$ (this time ensuring we don't pass through the edge {$$$u, v$$$}) to calculate the distances for the second case in $$$O(m * log(n))$$$ for each edge. After this we can just take the minimum of these three values to value of $$$d(a_i,b_i)$$$.

    So we can just iterate on each of the $$$m$$$ edges, consider it to be the edge we make zero weight, and calculate the answer for all m edges using these distances in a total time of $$$O(m * m * log(n))$$$.

    Submission — 96142460

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Using Dijkstra only wouldn't this method also correct? (haven't implemented yet)
      For every $$$(a_i,b_i)$$$ Let $$$e_1,e_2...e_k$$$ will be the edge in the shortest path. $$$C[i]$$$ contains the contribution of every possible edge i.e. $$$C[i]=w_i*f$$$ where $$$0<=f<=K$$$ is the frequency of the edge $$$e_i$$$ in all $$$K$$$ delivery. Now final answer will be $$$\sum C[i] -max(C[i])$$$.
      I think it's right, right? However can you tell any easiest implementation idea of how I can get these edges in shortest path while using Dijkstra?

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        No, this is not correct. The given 2nd example in the problem statement is a counter example. It is possible that an edge is not picked with the initial edge weights, thus not even included in your shortest path.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Awesome Explanation. Thanks a lot.

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

can i get some help on finding the hack-testcase or why my code might fail on some cases ? it seems like a lot of people are getting hacked on F XD

my submission : my code

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Was expecting someone would do this and here it is.

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

This solution looks copy pasted from somewhere here

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell why my Submission for Problem D gave this weird Memory Exceeded Error.

My approach was to connect all possible edges(belonging to different gangs), then if it is possible selecting any connected graph print accordingly.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to approach problem F ?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Today I gave my first contest but I did only A B C D in 2 hours. But I did not even get time to read F, G, H . How do I improve ? and what mistake is very common among ultra beginners ?

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

    thats not a terrible first contest

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

      I get 449 rating (total) and I am in the bottom of the newbies. How is not terrible ?

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Your rating will build everytime you can answer 4 questions. It also measures consistency. Look at my rating, I answered 3 of those questions and dropped to 978

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

E was such an easy ques that it can be solved in 5 min but due to bad statement it took me 1hr to solve...really disappointed

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

I solved problem E afterwards with help of OEIS. During the contest, I was pretty messed up with that. Anyone would like to care what I am thinking wrong for Problem E. If I am not wrong there was two announcements. There was that thing, [1, 3, 4, 2] and [4, 2, 1, 3] are equal (in first announcement), [1, 2, 3] and [1, 3, 2] are distinguishable (in second announcement). My question is, I can make [1, 3, 2] from the [1, 2, 3] by choosing 1 (index 1) then going backwards index 3 with value 3 and index 2 with value 2, thus it makes [1, 3, 2]. So [1, 2, 3] and [1, 3, 2] circle should be equal like [1, 3, 4, 2] and [4, 2, 1, 3]. What is wrong with my thinking?

»
6 weeks ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

Weak pretests for F. Hacked a few solutions using this test case. 3 2 13 1 1 13 1 1 1

  • Few people didn't consider that minimum answer will be 0.
  • I misread the q. Instead of no more than m/2, I applied DP considering exactly m/2 in each row and it passed all pretests.[My fault]

BTW F was a really nice DP problem.

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

    You don't know what I did! I just took the max m/2 elements in every row summed them up and took the max number less than or equal to sum divisible by k and it passed pretests and later it got hacked. I already knew it would get hacked but this type of solutions passing makes me sad. The tests were quite weak. My solution would even fail for this-

    test
»
6 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Any hack test-case for A-E?

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

E was 2*f(n-1)/n why did they ask for so small n? for f being factorial

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is the contest very easy or all the participants were much more intelligent then me?

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

    It was a easy contest .. But if anyone stuck in a problem thats effects so much.. May be u stuck on any problem..

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

Problem F:

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

I think we need to rename Div3 rounds to vovuh rounds. Sounds kinda cool :)

»
6 weeks ago, # |
Rev. 3   Vote: I like it +50 Vote: I do not like it

As an extra, try to solve C for all fish, i.e. check for each fish if it can eat everyone else. It’s a surprisingly beautiful problem (probably div2E/div1C level).

Solution
  • »
    »
    6 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    We can use Segment tree. For every current fish $$$f_i$$$ we will do range update(left side and in right side). for $$$i<j<n$$$ we update as $$$a[j]=a[i]+j-i-1-a[j]$$$ in right side and $$$a[j]=a[i]+i-j-1-a[j]$$$ in left side. Now we will find min_range query in left side and right side If minimum value>=1 in both side then it's possible otherwise not. Overall complexity $$$O(NlogN)$$$
    Please verify whether it's correct or not. I think it is.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What does your solution do in the case where $$$a = [4, 2, 1, 1, 1]$$$ at position $$$2$$$? Answer should be “YES”. More complicated cases exist, as well.

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Ohh yes. I didn't consider the case $$$:-$$$ if I am going towards say left at any point of time(in the middle) I can turn right and then left,right,left... Hmm Now I don't know how to do this. Thanks for pointing it out.

  • »
    »
    6 weeks ago, # ^ |
    Rev. 5   Vote: I like it +1 Vote: I do not like it

    This is how I initially read the problem. Then I thought "this seems hard" and read it again. But now that I think about it again it is indeed a nice too-hard-for-Div3C problem.

    Here's a quick outline of a solution idea:

    Spoiler
    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      The solution looks good to me (at least the code seems OK)! I'm not exactly sure what you mean with properties (4) and (5) (for my example, $$$L = 2$$$ and $$$R = n$$$ satisfies your constraints, but does not block fish at position $$$2$$$).

      I've posted my take on the solution to my original comment.

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

        Constraints (4) and (5) do apply to the $$$L=2, R=n$$$ interval on $$$a = [4, 2, 1, 1, 1]$$$, but it does not block the fish at position 2 because $$$L \neq 1$$$ and $$$a_2 = 2 > a_{L-1} - R + L = 4 - 5 + 2 = 1$$$.

        Regarding the question posed at the end of your solution: I expect $$$O(n)$$$ time is possible. My idea is to generate the constraining intervals in increasing order of $$$R$$$ with one pass, and to generate the constraining intervals in decreasing order of $$$L$$$ with another pass. Then, the constraints can be applied in $$$O(n)$$$ with one more pass using two pointers and a stack, since any two constraining intervals are either disjoint or nested. (EDIT: See 96263307.)

        Incidentally, the hack test that I added to kill my incorrect version of that submission with slow asserts left on caused around 150 people with naïve $$$O(n^2)$$$ submissions to the original problem C to fail system tests.

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          ‘Any two constraining intervals are either disjoint or nested’ -> nice one.

          Also, it’s pretty funny that you managed to hack 150 people by hacking your bad solution.

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

    Some progress.
    1. The set of fish $$$i$$$ can eat forms an interval $$$[L, R]$$$ where $$$L <= i <= R$$$. If we can't extend it any further, than
    2. $$$a_{L - 1} >= a_i + R - L$$$ and $$$a_{R + 1} >= a_i + R - L$$$
    3. $$$mx(L, R) < a_i + R - L$$$
    if we combine, we have
    4. $$$a_{L - 1} > mx(L, R)$$$ and $$$a_{R + 1} > mx(L, R)$$$
    Now, how to check that thing? I am struck here.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please also tell a way to solve that one?

»
6 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

For problem D, why does 96184774 AC and 96185095 doesn't? All I did was change arrays to ArrayLists. I am unable to see the testcase which it fails on.

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

    Integers are object so you can't compare them with == because most of the time the references won't be the same.

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

Anyone, please help me here! I coded F and got a TLE on case 144. I was practicing out of the contest, so I hardcoded that case to see if there are more cases like it. But after hardcoding, my solution passed. On scrolling through cases, Case 144 and Case 227 are similar while 227 being more in size constraints. But my solution passes 227 while fails on 144 if not hard coded. I used DP. Can anyone please help why is this happening and how do I optimize to pass case 144?

Submission: 96189336

Update: Hacked my own solution so as to someone don't see it as an AC solution. But someone help me out here so as to why is this happening on case 144 and not on 227. And how to optimize?

Update 2: Figured it out! Thanks

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

deleted

»
6 weeks ago, # |
  Vote: I like it -30 Vote: I do not like it

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

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

It is so annoying to see that someone needs only 2 minutes to solve the problem G while I have to spend 2 hours :/

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Will this round will be rated for user having rating less than 1000 if then why rating has not been updated yet?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

When will the ratings come?

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

    For the ratings, We need to wait at most 12 hours after the open hacking phase is finished.

    P.S. From my experience from previous Div3 contest participation :)

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      There is no hacking phase in this round right?