isaf27's blog

By isaf27, 13 days ago, translation, In English,

Hello, Codeforces!

I'm glad to invite you to Codeforces Round #559 (Div. 1) and Codeforces Round #559 (Div. 2), which will be held on May/12/2019 17:35 (Moscow time). The round will be rated for both divisions (I hope).

All problems were written and prepared by me. Thanks to aleks5d, TLE, sunset, Sooke, Peltorator for testing problems and good advice, 300iq for round coordination and help with preparation and MikeMirzayanov for great systems Codeforces and Polygon.

You will be given 6 problems in both divisions and 2 hours to solve them. Please, read all the problems. Good luck, have fun and I wish everyone high ratings!

The scoring distribution will be announced closer to the beginning of the round.

UPD

The contest finished, contgratulations to the winners:

Div1:

  1. mnbvmar
  2. ecnerwala
  3. ainta
  4. ksun48
  5. ekzhang

Div2:

  1. hbi1998
  2. Nutella3000
  3. calabash_fool
  4. ahgus89
  5. 1207koo

Editorial

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

»
13 days ago, # |
Rev. 4   Vote: I like it +11 Vote: I do not like it

Orz Sooke, wish I will be red too!

»
13 days ago, # |
  Vote: I like it -35 Vote: I do not like it

Orz Sooke

»
13 days ago, # |
  Vote: I like it +104 Vote: I do not like it

I'm not Peltorator, I'm Isaf27_loves_me. Fix it, please.

»
13 days ago, # |
  Vote: I like it +24 Vote: I do not like it

Please,No MathForces !!!

»
13 days ago, # |
  Vote: I like it -41 Vote: I do not like it

UPD1: The round is carried over for 20 minutes.

UPD2: The round is carried over for 15 minutes.

UPD3: The round will be unrated.

People who has +200: Why do I participate?

»
13 days ago, # |
Rev. 2   Vote: I like it -99 Vote: I do not like it

Okay! Thank u for your unreasonable voting :V

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

    I guess he will consider, if you give him some RAMADAN special biryani xD

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

      FYI Ramadan is not about eating but fasting.
      By the way, they don't eat Biryani in Russia :V

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

    It's hard if not impossible to consider the prayer time. Because the prayer time in every country are not same and people from all over the world participate here. And every minute is a prayer time in somewhere in the world. So when do you suggest to schedule the contest?

    Moreover, this platform have people from many religion, culture and region. The platform must not run by considering any religion, culture or region. The platform should be secularist and International.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Obviously, every hour there is muslims have fast breaking in Ramadan

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

I like the weekend contest, thank you isaf27.

»
13 days ago, # |
Rev. 3   Vote: I like it +27 Vote: I do not like it

I hope this will be IMO contest from isaf27, not 2 problems like "write a segment tree" and 4 problems like "write a link-cut tree with operations ADD, FIND_SUM and REVERSE_ALL_BITS in $$$ne^{\sqrt{\log n}}$$$ time and $$$n\log^{2.39}n$$$ memory".

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

    Hope is a good thing.

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

    I completely agree with you. Hope there will be some problems like find the equation of Euler line $$$\dots$$$

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

      Actually, I gave the problem about Euler line to isaf27 and he didn't solve it because of its extremely high idea level, so I don't think we'll see it in the contest.

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

        Please, don't discuss the problem from some contest in the future

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

          Yes, I hope nobody runs into this discussion and sees any ideas of problems that are to be used in the future.

          Blah-blah, blah, blah, so, isaf27, does your last statement mean that we can find the optimal length of twix in $$$\mathcal{O}(1)$$$ time per query?

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

            We should find a formula dependent on the volume of Lipton. I can't answer your question now, it's too hard.

            • »
              »
              »
              »
              »
              »
              »
              11 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              what's twix? what's the volume of Lipton? Could you give some links?

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

                Never mind, local jokes :)

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

    Have I misunderstood you? Do you want Mathforces?

»
12 days ago, # |
Rev. 2   Vote: I like it +15 Vote: I do not like it

Smh, All red contest. Hoping it will be balanced.

»
12 days ago, # |
  Vote: I like it -6 Vote: I do not like it

I will solve cookie (0) problems this round too!

All hail cookie

»
12 days ago, # |
  Vote: I like it +18 Vote: I do not like it

Sooke is our red sun!

»
12 days ago, # |
  Vote: I like it -65 Vote: I do not like it

I guess there will be a massive drop in participation from India due to the finals of IPL. (Once in a year).

»
11 days ago, # |
  Vote: I like it -22 Vote: I do not like it

I'm not gonna participate because i have final exams and I'm not gonna study because i wanna participate and I'm not gonna participate because i have final exams Sad ..

»
11 days ago, # |
  Vote: I like it +8 Vote: I do not like it

looking forward to Sooke 's contest!

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

    This is not my contest. I just test these problems for the correctness.

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

      Will your profile picture change to megagnar when you're angry

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

      Maybe he is looking forward to the one in the future.

»
11 days ago, # |
Rev. 2   Vote: I like it -41 Vote: I do not like it

Bad schedule for Man City & Liverpool fans! :p

»
11 days ago, # |
  Vote: I like it -33 Vote: I do not like it

Tanmay Bansal will give contest today

»
11 days ago, # |
  Vote: I like it -27 Vote: I do not like it

help me pls :(

»
11 days ago, # |
  Vote: I like it -8 Vote: I do not like it

Wish my rating will up up QAQ

»
11 days ago, # |
Rev. 6   Vote: I like it +63 Vote: I do not like it

Am I the only one who is facing problem accessing the problems and submitting the solution? Each time I submit the solution I am getting the verdict "You have submitted the same code before" but in "my submission" tab I am not able see the submission :(

It's almost half way and I am facing same problem now even! Can't submit my solution for A and B (or don't even know if they has been submitted successfully or not?) Doesn't matter which problem I am going to submit, I receive the same verdict all the time :(

»
11 days ago, # |
  Vote: I like it +61 Vote: I do not like it

unrated? site was down for the first 30 minutes for some people

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

    Maybe we can finally switch to using dynamic cloud providers instead of fixed hardware in the ITMO basement?

  • »
    »
    11 days ago, # ^ |
      Vote: I like it -21 Vote: I do not like it

    and Div2C was unclear for the 90 minutes for lot of people

»
11 days ago, # |
  Vote: I like it +69 Vote: I do not like it

Why is it impossible to register on m1.codeforces.com? I tried to register 10 minutes before the contest but the main site was down so I couldn't. And I can't even read the problems if I'm not registered. :(

»
11 days ago, # |
  Vote: I like it +101 Vote: I do not like it

I'm doubtful if the round should be rated. Quite a lot of people throughout the world experienced traffic issues. I think that absence of the score distribution in the round announcement post at this moment (45 minutes have passed) indicates the severity of the problem.

Everyone knows that the problemsetters, the coordinators and the Codeforces Headquarters endeavored to deliver the best contest. The same applies to the current participants, who tried to solve the prepared problems despite of the mayhem. But is there any reason to persist a rated contest if the impact of the techincal issues is apparent, for the sake of sportsmanship? Unrated contest is not a total failure; there are things to gain and learn, and the efforts of the contest managers do linger.

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

    Sorry about the technical issues, it seems some misconfiguration happened in process while I jump between servers. I work hard to diagnose and fix it.

    The notice about the micro-sites (green information bar in the header) appeared about 1 hour before the contest. Also I remind it in the official Telegram channel. Am I right that m1/m2/m3 work good without technical issues? I think it means if you follow recommendations you was able to read and solve the problems without any timeouts.

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it -23 Vote: I do not like it

      Not everyone saw that notice. I tried to login 5 minutes before the contest starts and the site was already down.

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

      But i wasnt able to know scoring distribution, and i couldn't view standings.

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

        Neither was anyone else, which at least is fair.

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

      m1/m2/m3 worked perfectly for me. It loaded almost instantly.

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It was fine, i didn't know what to do the first 2 minutes but then it was fine just like a regular contest.

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

      Yes , light weight sites worked good ...i submitted 3 problems from there without any unnecessary delay. Thank You!

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

      You can't log in to m1/m2/m3 sites with a google account because of which I couldn't submit for the first 15 minutes.

»
11 days ago, # |
Rev. 4   Vote: I like it +16 Vote: I do not like it

MikeMirzayanov crashed his scooter into a rack of servers,so site was down for 30 minutes .Is the round still rated?

»
11 days ago, # |
  Vote: I like it +110 Vote: I do not like it

There is no reason to make the contest unrated. The technical issue was in the beginning of the contest. Everyone could use m1 m2 or m3.codeforces.com. Participants who didn't use those sites and therefore lost time could still decide not to submit and don't participate in the round. Submitting code means you could use the system well or you accepted that you lost time. Everyone who submitted code made the decision to participate in the rated contest.

  • »
    »
    11 days ago, # ^ |
    Rev. 2   Vote: I like it -14 Vote: I do not like it

    .

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

      Main site was down at the start for less than 10 minutes. All the mirrors were still up. Rounds have been rated in more drastic cases, if I remember correctly. So please make this rated, even if the participant count was lower than usual because of technical issues.

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

        Last week we got an unrated round because of weak pretests on problem A lol.

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

          That round being unrated was one of the worst disappointments I have ever faced

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

            I agree. That contest was all right except problem A.

      • »
        »
        »
        »
        11 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        for me the page didnt work normaly for like 45 min

        • »
          »
          »
          »
          »
          11 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          That's unusual. I had no downtime on the mirrors and only like 10 minutes on main site.

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

      Neither did anyone else.

»
11 days ago, # |
  Vote: I like it +17 Vote: I do not like it

The main problem was even though I tried to use m1/m2/m3, somehow I wasn't registered(though I was), so I had to wait for 20 minutes to register and then submit solutions to m1. I guess I'm not the only one, who was unregistered without knowing.

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

    Then why didn't you register in advance? It is not that the site has been down for the whole time it has been able to register.

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

      I was registered in advance, but then system unregistered me, so I couldn't enter the contest on m1/m2/m3.

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

        There are almost 24 hours that can register. When did you register?

»
11 days ago, # |
  Vote: I like it +9 Vote: I do not like it

Someone posted the solution to div2 A in the blogs already lol.

»
11 days ago, # |
  Vote: I like it +104 Vote: I do not like it

Problem D is Windy Path (Problem L) from the 2016 ACM-ICPC Pacific Northwest Regional, with slightly higher bounds.

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

    Thank you. I was sure that I saw this problem in some contest but couldn't remember the exact contest.

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

    The bounds is not important. I'm sure that almost people have the same solution for both.

»
11 days ago, # |
Rev. 3   Vote: I like it +16 Vote: I do not like it

Good tasks, thanks!)

»
11 days ago, # |
  Vote: I like it +12 Vote: I do not like it

TIL you can submit in the mini-sites. I just read the problems :/

Doesn't matter much for me though since it took me so long to solve A that the servers were up when I was ready to submit

»
11 days ago, # |
Rev. 3   Vote: I like it +54 Vote: I do not like it

Me: Reading the problem statement of Div 2 C

made wild assumptions and passed for some reason

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

    Can you please explain why it was so hard to understand? It got two clarifications and I could not understand why.

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

      The statement was confusing. The word "some" was somewhat misleading. I would have separated the key sentence into two sentences as follows: "Boy i gave at least b_i sweets to each girl. Girl j received at most g_j sweets from each boy."

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      In theory everything was written in the statement, but for example I thought that each boy has to give at least $$$b_i$$$ sweets each girl and I couldn't get it right without asking a question to first sample.

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

      I thought bi is the upper limit for the number of candies the girls received from each boy. Then I figured out that is wrong, so i thought it means the upper limit for the total number of candies received

      Actually the main reason for the problem should be my poor English...

      There isn’t any actual problem about the statement, everything should be alright after reading the samples I guess

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hint: Solve the problem assuming there are no missing values, after that it will be easy to extend it to the general case.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it -31 Vote: I do not like it

    You can see my greedy solution (but i cannot prove it). Answer my comment if you have questions. 54046042

  • »
    »
    11 days ago, # ^ |
    Rev. 3   Vote: I like it -8 Vote: I do not like it

    Build a graph for relative order of p : if p[i] < p[j], there is an edge from i to j

    If there is a valid topsort order, there is the answer

    We build an edge from i+1..next[i]-1 to i and an edge from i to next[i].

    However, there are O(n^2) edges.

    To solve the problem, use segment tree to represent a range of nodes build two edges from [l..r] to [l..mid] and [mid+1..r] so there will only be O(n) number of nodes (not more than 4*n)

    EDIT: Hope I won't get TLE on systest :C

    EDIT2: Accepted :D

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

      I think there is an easier solution. For any -1 in the input, use i+1 (point them at the next node); this should not change the existence of a solution. As you read the nodes, keep track of the previous nodes that point at following nodes with a stack, and make sure they nest properly. Finally, sort the nodes using (next_i, -i) and assign values according to this order. I think this works . . .

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It is sufficient to add edges of two types:

      • i to next[i]

      • the first index j to the left of i such that next[j] > i (if it exists), where we add an edge from j to i

      So there are only O(n) edges anyway. (Code)

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Couldn't get an AC in the contest. I used a greedy algorithm.
    Let us try filling the array smallest to largest.
    We can observe that if next[i] = j, than for any x, i < x < j , next[i] <= j.
    Also, permutation[x] < permutation[i] < permutation[j] . We can just fill the subarray (i+1 to j-1) first, and then fill i.
    We can then go on working on array starting from j.

    int small = 1, flg = 0;
    void solve(int st, int en) {
    
    	if(st > en || flg)
    		return;
    	if(nex[st] == -1)
    	{
    		ans[st] = small++;
    		solve(st+1, en);
    		return;
    	}
    	if((nex[st] > (en + 1)) || (nex[st] <= st))
    	{
    		flg = 1; // determines invalid case
    		return;
    	}
    	solve(st+1, nex[st]-1);
    	ans[st] = small++;
    	solve(nex[st],en);
    }
    
»
11 days ago, # |
  Vote: I like it -65 Vote: I do not like it

How about making the round rated for only positive rating changed users? (This happened previously in codeforce)

»
11 days ago, # |
  Vote: I like it +16 Vote: I do not like it

Div 2E seems to be easier than Div 2D.

»
11 days ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve Div2D?

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

    Try to write a brute force and observe patterns. ;)

    The key is the number z = (n — k) / 2.

    You build a string with [z zeros, a one, z zeros, a one, ...]

    e.g. n = 14, k = 10, 00100100100100

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

    You can repeat the pattern 0000...001 over and over up to n length.

    The number of zeros in the repeating pattern is (n-k)/2.

    I am actually surprised why there has not been more solves. Makes me doubt the solution

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

      I couldn't figure out this pattern by myself. What was the idea behind it to came up with this idea?

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

        Tried some things with pen and paper, observed the pattern, coded a brute force solution and observation proved valid for all n upto 20. So, went for it : P

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Even in the examples, u can see the patterns...

  • »
    »
    11 days ago, # ^ |
    Rev. 3   Vote: I like it +8 Vote: I do not like it

    Say you are given $$$n$$$ and $$$k$$$. Set $$$d = \frac{n-k}{2}$$$, $$$l0 = floor(\frac{d+2}{2})$$$, $$$l1 = floor(\frac{d+1}{2})$$$. Now the string of $$$l0$$$ zeroes, $$$l1$$$ ones, repeat works. The special case is $$$k=1$$$, in which case you can only have one 0 or 1, and can use 0111... as your string.

    This works, since the string is cyclic with length $$$l0 + l1 = d+1$$$, and the start-point x (zero-indexed) of some substring mod $$$d+1$$$ uniquely determines its content, and the content for all residues is different. Therefore WLOG $$$x \leq d$$$. Let $$$s$$$ be the length of the substring. We must also have $$$x + s + (d+1) > n$$$, since otherwise the string occurs again $$$d+1$$$  characters later. So now we have: $$$s \geq n - x - d \geq n - 2d = n - (n-k) = k$$$

    Completing the proof.

    Submission: 54040228 (function count is unused, I just used it to test the code)

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

      Is the formula $$$n + 1 - 2 \cdot (\frac{n-k}{2} + 1) = n + 1 - (n - k + 2)$$$?

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You're right, the inequality should have been strict. Fixed.

        • »
          »
          »
          »
          »
          10 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Besides, do we really need to treat k=1 as a special case? I just use the overall implementation and i still got an accepted.

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

I can not access the site util the contest had passed 20 minutes. Stabilize the main site plz.

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

    and problems need clarification too!

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Smh, the issue has been already raised almost 10 times before your comment.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

  • »
    »
    11 days ago, # ^ |
      Vote: I like it -17 Vote: I do not like it

    I repeat my comment, but anyway : "You can see my greedy solution (but i cannot prove it). Answer my comment if you have questions. " 54046042

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Maybe he means Div1 ???

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

      If you see a purple or a red guy asking for C, its probably not Div2 C that he's asking for.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    make $$$nxt_i = i + 1$$$ for each $$$i$$$ $$$(nxt_i = -1)$$$

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

When I asked why Div2C sample3 's note said the first boy presented 1,2,1 sweets instead of 1,1,2 it just replied me to read the global announcement :(

(The problem has been fixed without announcement during the content.)

»
11 days ago, # |
  Vote: I like it +24 Vote: I do not like it

How to solve div1D?

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Problem D is Windy Path (Problem L) from the 2016 ACM-ICPC Pacific Northwest Regional, with slightly higher bounds.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think traversing convex hull and recalculating it after removing a point each time should do the trick.

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

    Lemma: Given any point $$$P$$$ on the convex hull, there always exists a solution that starts at $$$P$$$.

    Proof: We use induction (with the algorithm below).

    Clearly we can do it for $$$N = 2$$$. For general $$$N$$$, let $$$X$$$ and $$$Y$$$ be the points adjacent to $$$P$$$ on the convex hull. Because the entire set of points lie on one side of both the lines $$$\overleftrightarrow{PX}$$$ and $$$\overleftrightarrow{PY}$$$, we choose $$$X$$$ to be our next point if the first direction is to turn left, otherwise $$$Y$$$ if we want to turn right. Then we can remove $$$P$$$ from the set of points and continue by induction on $$$N - 1$$$ points, as $$$X$$$ and $$$Y$$$ will still remain on the convex hull after removing a point.

    Time complexity is $$$O(N^2)$$$. You don't need to find the entire hull; you can find $$$X$$$ and $$$Y$$$ in linear time using one step of gift wrapping.

»
11 days ago, # |
  Vote: I like it +161 Vote: I do not like it

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

If I make 2 submissions for a question, both correct.. will the first solution be checked?

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think olny the last one accepted in pre test.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    the first sumbissions are skipped, only the last one is valid.

»
11 days ago, # |
  Vote: I like it -29 Vote: I do not like it

Very Unfair Contest. First Server problem,then Div 2 C not clear and also announcement were not upto the mark.It should be unrated.

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

    I did terribly, but I still think it was a good contest. Although CF going down all the time is really annoying, there are m1/m2/m3 sites that work pretty consistently. Also div2c/div1a wasn't that unclear. They explained anything that might be confusing under the samples.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Learn Russian :)

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

    div2c was rather clear
    but there are some noobs who cant read

»
11 days ago, # |
  Vote: I like it +5 Vote: I do not like it

I am a newbie. How to solve Problem(B) Div 2.?

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    https://codeforces.com/contest/1159/submission/54032077

    A tutorial will probably come in a few days describing exactly how to solve it, but if you can understand this code, then that's all you need. I personally tried a lot of greedy solutions and I would have never thought about this one. I don't even know why it works to be honest. Anybody have an explanation ?

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

    This is how I solved it. First of all, notice that we can rewrite the $$$k$$$-extension condition for a pair $$$(i,j)$$$ to the following:

    $$$ k \leq \frac{\min(a_i,a_j)}{|i-j|} $$$

    The important observation is that the right hand side of that equation does not depend on $$$k$$$, so for every pair we have an upper bound to the value of $$$k$$$.

    Since this must hold for every pair $$$(i,j)$$$ such that $$$1 \leq i,j \leq n$$$ and $$$ i \neq j$$$, we conclude that an upper bound for $$$k$$$ is $$$\underset{ 1\leq i\neq j \leq n }{\min} \frac{\min(a_i,a_j) }{|i-j|}$$$, since $$$k$$$ should be less than all those upper-bounds in order to be a $$$k$$$-extension. Moreover, by definition we have that all $$$k$$$ that are less or equal than that number work. By choosing the biggest $$$k$$$ as possible (which is the smallest upper bound) we have our answer.

    Now that we know what the answer is, the remaining question is how to calculate it efficiently. An idea to do this is to find a small amount of candidates for those pairs and calculate the upper bound only for those pairs. To do this you can prove that the pair that attains such minimum must necessarily be paired with either $$$a_1$$$ or $$$a_n$$$, this gives us only $$$2n$$$ candidates and we can simply try all of them.

»
11 days ago, # |
Rev. 3   Vote: I like it -23 Vote: I do not like it

1159D - The minimal unique substring

What is wrong??

54043161

int solve(int n,int k){
	lint p=0;
	if(n==k){
		rep(n)cout<<'1';
		return 0;
	}
	rep(k/2+1)cout<<"10",p+=2;
	while(p<n)cout<<((n&1)?'1':'0'),++p;
	return 0;
}
n,k--------------------
output
1,1--------------------
1
2,2--------------------
11
3,1--------------------
101
3,3--------------------
111
4,2--------------------
1010
4,4--------------------
1111
5,1--------------------
10111
5,3--------------------
10101
5,5--------------------
11111
6,2--------------------
101000
6,4--------------------
101010
6,6--------------------
111111
7,1--------------------
1011111
7,3--------------------
1010111
7,5--------------------
1010101
7,7--------------------
1111111
  • »
    »
    11 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Maybe I am wrong as I am from Phone, but it seems for 9, 5 it would give 101010111, which has shortest unique 3

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      omg its true... Thank you for the information!

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

    Had the same idea, but realized it would fail for larger n values...

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think that in the future, you should preview your question before posting it, it is badly formatted.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

»
11 days ago, # |
  Vote: I like it +35 Vote: I do not like it

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

You think the geniuses are those who prove the Fermat's theorem? No, the geniuses are those, who made div2 D )))

»
11 days ago, # |
  Vote: I like it +15 Vote: I do not like it

This round in a nutshell : "I'm just gonna make some crazy assumptions and hope they pass the tests." Also, the difference between C and D was too much.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    D was not that difficult. If you can brute force, you will easily find the pattern.

    However, if you are talking about clarity in problem specification, I agree 100%

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

      You've got a good point, perhaps I_Didn't_Do_Enough_Things_For_WA

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve div1C pls?... :)

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

    In this task we just need to check, that topsorted-order of vertices is correct.

»
11 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Can we see the tests pls?

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello,I got some questions with problem C (Div2)

for

2 1

0 0

1

I think the answer should be -1.right?

I missed this situation during the contest.And I think my solution 54038745 will be WA after system test,but it's still accepted Σ(  ̄□ ̄||).

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Problem B?

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    for every item in the array, the value of k for that specific item = value/distance, where distance is maximum distance possible i.e either from 1st or from the nth item, now from all these values of k the minimum one is the answer. Pseudo code : i from 1 to n k=min(k,a[i]/max(n-i,i-1) print(k)

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I am not getting why we are taking individual values min(k, a[i]/max(n-i, i-1) ? aren't we supposed to consider the every pair? i.e.min(k, min(a[i], a[j])/|i-j|) ?

      • »
        »
        »
        »
        11 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        We can take individual values because in min(a[i],a[j]) if we take individual values it won't affect our answer in the end, because even if we calculated for the bigger value also, when taking min(k,a[i]/dist) that value will automatically be eliminated .

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you tell me why my submission to Div.1B got WA on test 22?

Test 22 is $$$(n, k) = (5783, 2359)$$$, and my output is '0{$$$1067$$$}10{$$$2357$$$}10{$$$2357$$$}' (0{$$$n$$$} means $$$n$$$ zeros) Judge says minimal unique substring for my output is 1069.

  • »
    »
    11 days ago, # ^ |
    Rev. 5   Vote: I like it 0 Vote: I do not like it

    Edit nvm I read it wrong

    as tfg said 0{1068}1 i completely overlooked that mybad

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      For t="0{$$$1067$$$}", I think we have at least two $$$l$$$s in problem statement, $$$l=1$$$ and $$$l=1069$$$...?

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

    0{1067}10 appears more than once

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    0{1068}1 happens only once.

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

In Div2E/Div1C.
Does anybody know why this 54049263 gives MLE? When I change stack to set I get AC in this 54047364

My Approach: Construct a directed graph where edge (u,v) means a[u] < a[v] and then do topological sort on that graph.

The way I construct it is if nxt[i] = j that means there is an edge(i, j), also there is an edge between all elements [i+1, j-1] and i since all of them must be less than i. I only keep track of the least previous element.

Here's an example where ix, jx means nxt[ix] = jx:
i1 i2 i3 ... j3 j2 j1. Edges are (i1, j1), (i2, j2), (i3, j3), (i2, i1), (i3, i2). I don't add (i3, i1) since it's redundant.
In a case like i1 .. i2 .. j1 .. j2 In the MLE submission I exit immediately and say that it's impossible. In the AC submission with set I let the topological sort handle it.

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

    Change vector<stack<int>> Pop(n); to vector<stack<int, list<int>>> Pop(n); and MLE should be gone. This is happening because when you pop elements from the stack, the underlying container (deque is the default) is not actually freeing up space. deque will hold the allocated space during the entire runtime of the program. So just change the underlying container to list, which on the other hand frees up space when an element is removed from it. Now you are maintaining $$$N$$$ stacks which can have upto $$$N$$$ elements, thus requiring too much space if space is not freed when elements are popped off the stacks. list will free-up space and your program wouldn't run into MLE. Also, set will free-up space as soon as your erase from it. Thus your second program doesn't run into MLE.

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

      Thank you so much for the answer! I've changed the internal container from
      vector<stack<int> > Pop(n) to vector<stack<int, list<int> > > once and to vector<stack<int, vector<int> > > once and both got AC without changing the other stack to set.
      However I've got 2 questions.

      1- Shouldn't my total amortized memory be N not N^2? at each iteration I do at most one push_back in some deque in Pop[i]? even if I don't free up memory shouldn't that be fine because the total number of elements in all N deques will still be N? specially since AC solution passes in 27~35KB so I'm not on the edge of running out of memory.

      2- Why does changing the underlying container to vector<int> still pass although the vector doesn't shrink the capacity with the pop_back() calls either? I know that deque requires more memory than vector but is it really that much more?

      Please note that I've only changed the underlying container in Pop. I haven't changed the other stack to set, neither have I changed its underlying container either. I've only made changes to vector<stack<int> > Pop(n).
      Here's the latest 2 submissions: 54094520 , 54094473

»
11 days ago, # |
  Vote: I like it +22 Vote: I do not like it

OMG finally purple! Gonna try not to lose this next contest lmao

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you for your contest !!!!!!!!!!!!!!! I very love it

»
10 days ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Please translate the tutorial to English isaf27, can't understand google translation of 1159D - The minimal unique substring's solution

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I tried solving Div2 E with a solution of complexity O(t*nlogn) and am getting a TLE. Can anyone suggest why? Submission link — https://codeforces.com/contest/1158/submission/54055728.

I basically replace all -1's with a positive value in the following manner ~~~~~ int o = n+1; for(j = n-1; j>=0; j--) { if(inp[j]>0) o = inp[j]; else inp[j]=o; v.push_back(make_pair(inp[j],o)); } ~~~~~ I then sort this v vector and construct the answer array by using the values in the inp array. Finally, for any element if according to the input array, the first element greater than the current element(stored using a stack and array) is at an index before than that in the input array, then the answer is -1. The sorting step might be the time consuming step but I don't get how I am violating the time limit.

  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think your problem might be this line:

    while(z<ans.size())
    

    Your ans array is pretty big and never resized, so for every input you're going to be running this loop over all of ans.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me with Div2-D ? Not able to figure out the greedy approach.

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

English editorial anywhere?