Codeforces Round 512 (and Technocup — Elimination Round 1)
By KAN, 6 years ago, translation, In English

Hi all!

This weekend, at Sep/23/2018 16:05 (Moscow time) we will hold Codeforces Round 512. It is based on problems of Technocup 2019 Elimination Round 1 that will be held at the same time.

Technocup is a major olympiad for Russian-speaking high-school students, so if you fall into this category, please register at Technocup 2019 website and take part in the Elimination Round.

Div. 1 and Div.2 editions are open and rated for everyone. Register and enjoy the contests!

The Elimination Round authors are Roms, BledDest and adedalic. Thanks to Anadi who authored the last problem for div. 1 round and arsijo for his help in coordination. This round would also be not possible without the help of our testers: winger, Um_nik, AlexFetisov, Denisson, thank you so much!

Have fun!

Div. 2 and the Elimination Round will feature 7 problems, preliminary costs are
250 — 500 — 750 — 1500 — 2000 — 2500 — 3000.

Div. 1 will feature 5 problems, preliminary costs are 500 — 1000 — 1500 — 2000 — 2500.

The round is over, congratulations to the winners!

Technocup 2019 - Elimination Round 1

  1. 300iq
  2. sadovan
  3. voidmax
  4. karasek
  5. ----------

Codeforces Round 512 (Div. 1, based on Technocup 2019 Elimination Round 1)

  1. TLE
  2. webmaster
  3. sunset
  4. jcvb
  5. volamtruyenkyii

Codeforces Round 512 (Div. 2, based on Technocup 2019 Elimination Round 1)

  1. Chair_man_Xi
  2. icecuber
  3. yp155136
  4. xjd0623
  5. liyingyan7

The analysis is published.

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

Comments Comments (160)
| Write comment?
»
6 years ago, # |
  Vote: I like it +52 Vote: I do not like it

Clashes with open cup. Please delay the contest.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 4   Vote: I like it -97 Vote: I do not like it

    I have more downvotes than upvotes of this blog

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

    Unfortunately we can't postpone the round, because it is an Elimination Round for Technocup and was scheduled long before.

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

      y u do dis :'( please come up with a solution... both contests are so interesting...

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it -19 Vote: I do not like it

      You can delay only div1 + div2 rounds. Students can't participate in main round.

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

    I don't want delay.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -12 Vote: I do not like it

    It's clashing with AtCoder Beginner Contest 110 too. :(

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -12 Vote: I do not like it

    Just do both lmao.

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

Just before September CookOff On CodeChef — Two Consecutive Contests + Sunday

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

You didn't mention anything about the number of problems. Can you edit that please? Edited, thanks

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

Round 2^9 :D

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

There are gonna be statements in English for the Div.1 and Div.2 editions, right?

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

A bad time for Chinese students.

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

    Better than contests that started at 11:35p.m.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it -37 Vote: I do not like it

      But most high school students can't use computers between 10 and 10:30. So I think it is better to race earlier or later.

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

        But I don't think so. Codeforces is not only for high students.

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

          May I ask why high school students there can't use computers between 10 and 10:30? Just curious.

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

            Because most Chinese high school students will leave school at 10 pm, they need to go home to continue the competition.

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

              But I can register the competition because we have a holiday for Mid-Autumn Festival.

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

                Umm so you have to go to school on weekends...?

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

    This world needs one more cp platform for Сhinese, Japanese, Vietnamese and Australians.
    btw MikeMirzayanov can earn a lot of money by trading his cf system and installing it with Full Construction for anyone who could pay him some amount of money, so that person could hold contests there and get donations.

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

Another good time for Chinese Oier to enjoy the contest!

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

    But ...... many of HE->OIers doesn't have a holiday in Middle Autumn Festival...

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

      Still not so bad..(at least much better than 11:35 for oiers..) (why don't you use self-studying in the evening?:D

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

May I ask how many problems are shared between divisions?

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

    It's three in the previous contest.

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

    i think three

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

    I think (div.1 A=div.2 C) ,(div.1 B=div.2 D) ... (div.1 E=div.2 G)

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

      That's rather unlikely.

      If div1 is a subset of div2, then div2 would have to solve 2 extra problems than div1 while having the same time amount.

      My guess is div1 starts with div2D. Div1 version of this round wasn't there before, so I think a problem was added at some point.

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

Aren't 250 points for the first problem too less ?

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

    Wait for question to pop up.

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

    The question will have 2500+ submissions within 6-7 minutes, then :P

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

      Personally speaking, I will prefer to solve this question at last.

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

        I'm pretty sure that the optimal strategy is to always solve problems in increasing order of the time it takes to solve that problem. For example, if it takes you 1 minute to solve A and 3 minutes to solve B, if you solve A first you'll get 249+492=741 points, but if you solve B first you'll get 246+494=740 points.

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

          I would love to follow this stratergy but after getting soln. It takes me 5 min to code and test (due to my slow typing speed.) So I prefer reading all questions before starting.

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

            I agree with reading all problems before starting because there are many times where I get stuck on a problem believing "the ones after are harder" while I could've solve problem D way faster than problem C (or some other combinations). I failed a contest for not reading all the problems at the start before :(

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

          Not exactly. I think it's more of decreasing order of . For example, if it takes you 2 minutes to solve A and 3 minutes to solve B. Solving A then B gives you 750 - 2 - 10 = 750 - 12 = 738 points while solving B then A gives you 750 - 5 - 6 = 750 - 11 = 739 points.

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

            Yeah, i calculated something wrong. I'll check with a bunch of random inputs if your theory is correct.

            EDIT: It works on 500 million random contests with 4 problems each and 43 million random contests with 6 problems each. I think you're right.(I made each problem worth 250*(random number between 0 and 3) more points than the one before it and made the time required to solve a problem a random number between 1 and (problem number)*10.)

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

              Good job showing that you're a good scientist. thumbs up

              I think you should also try to prove it with a contest of 2 problems. You'll have a better understanding of why that's the case.

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

This is going to be my first contest ever. Wish me luck, guys. :)

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

Thanks to Mike Mirzayanov for the platform...

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

    Don't be angry with downvotes, you don't want Mike to see that. Codeforces community tryin to help you by hiding this comment

    → Reply
»
6 years ago, # |
← Rev. 4   Vote: I like it -22 Vote: I do not like it

Wish you all get failed system... Ok, that's a joke. Wish you all get high rating!

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

What will be the duration of the contest, <= 3 hours right? Otherwise it clashes with September Mega-Cookoff on CodeChef.

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

    If you go to the contests sections, you can see the duration of every contest (it's 2 hours btw!)

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

    "Mega-Cookoff"

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

round 1000000000

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

dont try to hack my solution .. warna kanpatti sek dunga.

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

    I prefer a hack rather than system failure. Since it gives me a chance to correct myself. I always pray that if my solution lacks something, then its better that it gets hacked.

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

upvote if u want to get upvotes.

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

who will give me the first upvote?

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

Geometry forces

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

today was a bad day , my mind completely shut off on B :( can anyone explain once the contest is over ?

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

    same here

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

    Mine did too when I first read it so I was like "you know what? Convex hull!" lol

    I got the convex hull out of the 4 points they gave us on the input and then, for each point, I tried to add it to the convex hull. If this point is in the new convex hull, that means this point isn't originally inside the polygon given (or it wouldn't be in the convex hull).

    I mean, I know there's probably a much easier solution, but that's what I came up with in a few minutes xD

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

      I was also inspired by the convex hull algorithm. I walked from anti-clockwise around the corners of the rectangle. Then for a given point I checked if the cross product of the vector from one corner to the next and the vector from one corner to the point was non-negative. If this is true for all corners the point is inside the rectangle.

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

    Div2 B Write equation of each line then divide rwctangle based on x coordinates and check if y lies below or above the line segments. Also do the case when n-d<d.

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

    Each line on the rectangle can be written as y = x + c or y = -x + c. Finding c for all 4 lines is trivial, as well as <= or >=. For every coordinate see if the inequality is true for all 4 equations.

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

    Look at the picture:

    These red lines are covering all of the points of the rectangle.
    Now focus on the topmost red line. What is common for all the points that lie on that line?

    All of the points on the top line can be descibed by this equality: y - x = 2.

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

      By the way, in general I know only about 4 equations which are useful in these types of problems:

      1. Horizontal line

      2. Vertical line:

      3. Diagonal line from top left to bottom right

      4. Diagonal line from bottom left to top right

      Diagonal lines are more difficult of course =)
      I need to constantly remind myself that I can add and subtract coordinates and get something meaningful out of it :)

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

    Since the coordinates are small , iterate through all the coordinates which lies on or inside the rectangle and mark them as 1. Now if the point lies outside the rectangle then the value of that point would be 0.

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

if i'am submit two time accepted to same problems, why i'am take point to the last submit?????

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

What is test 5 of B div 1 :(. Failed on it 3 times and can't find the mistake.

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

    I used the int version of popcount... wasted over 1 hour and 5 submissions

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

    Could've been something like

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

I was trying to solve E wth I smoked today

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

What is pretest 4 of Div. 1 D? T_T

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

    something like

    6

    17 17 73 73 163 163

    answer should be 262158769.

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

Can anyone explain Div1-B? I thought that for (l,r) to be good sum(l,r) has to be even and >= max element of (l,r). I couldn't do anything with this fact though. How can I approach this kind of counting problems?

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

    My approach -
    Considering the count of 1 bits as elements in the array.
    Sufficient condition -
    good sum(l,r) has to be even and sum(l,r)/2 >= max element of (l,r). And log2(1e18)<63.
    Then iterate until sum(l,r)<=126.
    Rest of r with even sum is good. At max 126 iterations.
    Time Complexity — O(126*n).

    Upd — 128 is loose upperbound. 64 is enough.

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

      I don't understand why you have taken 63, isn't 60 good enough? I used 60 and got the wrong answer on pretest 8 for whole contest

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

        Only statement on this case.
        "Take a loose upper bound. But it should not be large enough so to give TLE."

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

    I will try to explain my approach, though I failed on test 5 for unknown reasons: - For a certain r, you will store all "records" from right to left, which are new maximum numbers. You can see there are at most 60 values of this. Then you can simply binary search in this range for the rightmost index x that sum(x, i) >= 2 * bits. Then prefix sum in this range is easy.

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

      i failed on test 5 too and it turned out i was taking input as integers instead of long long (i was thinking the number of bits will fit into int)

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

        I failed on test 5 BECAUSE I USED __BUILTIN_POPCOUNT() INSTEAD OF LL. Gah screw me

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

          oof

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

            At least you got accepted man, I'm gonna go down to expert and then work my way back up now.

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

    As you said, you have to have:

    1. sum(l, r) is even
    2. sum(l, r) >= 2 * max(l, r)

    This is easy to prove, since your basic operation is decrementing one from two numbers in the interval (meaning that some of their bits cancel each other out).

    But we notice that max(l, r) <= 64, and the value of every element is at least one, so you can:

    1. Brute force intervals with length <= 64
    2. Count number of intervals that are longer than 64, with even sum

    code: 43313078

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

      You will have to brute force until 128.

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

        Well not really since max(l,r) is also counted in sum(l,r) so even if the other elements in the range are 1s your sum will exceed 2*max(l,r) after 65 elements or so.

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

          Got it.
          I took loose upper bound.
          I will pray that I don't get TLE and pretest cases are strong enough.

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

        You don't, since , so it's enough that the interval is longer than 64, since then .

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

    Thank you all very much!

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

      can you help understand this plz .. we are calculating for each number how many 1 in the binary representation right ? but why does it matter that the sum of 1 is even

      if we have 15 and 6 the sum of 1 is 6 which is even but xor isn't 0

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

        Cases where there are only two elements have one extra condition: Number of ones in al == Number of ones in ar

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

          doesnt that mean max element should equal or be less than half of sum of (1)

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

            I don't understand what you mean by that.

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

              if we have a number that has 8 ones in its binary representation and other 7 numbers that has only one one (lol one one) isnt that the same issue of the two numbers

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

                If I understand correctly what you are asking, this array will not be good, as the number with 8 ones can't have 0 ones even after xoring with all the other numbers. The condition that the numbers should be equal only applies where the subarray you're checking has 2 elements only.

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

what is the solution for Div2 D ?

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

Geometry forces. WTF?

A — too much troll problem. If a person couldnt solve problem A, what's he doing here? Why add such tasks in the competition?

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

B solution https://www.geeksforgeeks.org/check-whether-given-point-lies-inside-rectangle-not/

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

I think this is my worst performance ever, fell ashamed about this stupid bugs I had :(

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

    At least you failed while being in div1, something i can't say about me.

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

    Happened to me too :(

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

What is wrong with the following solution for div1D?

For each prime I can choose element of order p or order p - 1. Sort all primes and consider them from biggest to smallest if:

  • p is more than once than choose elements of order p and order p - 1

  • p is only once and our current answer is not divisible than p, than take element of order p

  • p is only once and our current answer is divisble by p than take element of order p - 1.

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

Is Div1D just making copies of p into p and p - 1 and taking LCM of everything, or is that wrong?

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

Codeforces? More like Mathforces.

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

Thanks codeforces for wasted an hour of mine for not specifying that "the segments should span the whole sequence" in Problem C

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

    "Note that each digit of sequence should belong to exactly one segment."

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

      ( T T ) . maybe the worst round I have ever had

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

hi how does one do problem D from Div 2? i was thinking along the lines of the shoelace method but didnt really manage to get far with that idea.

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

    AFAIK let it's height be h, and base length be b, now 1/2*b*h = n*m/k , so if 2*n*m%k != 0, then print "NO"

    else note than you can always get one value of b less than n and one value of h less than m just by dividing gcd's and simple manipulatins

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

      Why b * h is an integer ?

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

        since area of the triangle in coordinate form is

        1/2*sum(x1*(y2-y3)) = 1/2*b*h

        and the left side (after removing 2's) is indeed an integer

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

        If you have a triangle with points A, B, C; its area can be computed using cross product as 0.5*abs(AB X AC), where AB and AC are vectors going from A to B and C respectively. Since the points have integer coordinates, then b*h in 0.5*(b*h) must be integer.

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

    You can construct the triangle using the points (0,0), (a,0) and (0,b) for some values of a and b. The first thing to check is when you simplify the fraction by diving by gcds if the denominator is greater than 2 there is no solution. You can see this because of the shoelace method you mentioned. The key to finding a and b is when you divide by gcds first divide n and k by gcd(n,k) then take this new value of k and divide m and k by gcd(m,k). Then if in the end if your k is 2 your new values of n and m will work for a and b. If the new k is 1 you have to multiply one of these results by 2.

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

How to solve div2E (div1B) ?

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

What is wrong with this solution for Div2 D 43333417

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

    we aren't not allowed to see other's submissions until system pending is done.

    But maybe you're missing the case when n*m isn't divisble by k, but 2*n*m is .

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

      Oops, didn't know about that.

      I checked for that case. My code got WA on pretest 10. Thanks for your response

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

Does anyone have any idea what pretest 8 for Div 2E is?

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

is cf predictor broken? I know I'm not that good in div1 but I feel like being in the 2/3 place should not be a rating drop for barely above 1900 (I noticed people around me also had rating drops despite being like 1910)

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

    I feel like recently it's broken. 1 contest it predicted me having +112 when in reality, it's a mere +55. The second time not as broken, still, +102 turns into a +124.

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

how to change the username which is shown to others?

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

    you must wait until the new year

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

      really?

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

        Yes. This is kind of a Codeforces tradition — you have 10 first days every new year to have one chance to change your username.

        (i.e. this option will be available in 10 first days only, and you can use it only once per year)

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

WTF??!! 2 GEOM TASKS?? OMG F****G GEOMFORCES

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

I can't approach div1C by anything. Can somebody help me ?

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

    If you move boxes i ... i + k to positions x + i ... x + i + k, it costs:

    We want to choose the x that minimizes this. Note that the function is convex. We also have:

    Where comp(x, y) = 1 if x ≤ y, and  - 1 otherwise.

    Since the function is convex, therefore the difference is increasing, and cost(x + 1, i, k) - cost(x, i, k) only changes when x = (aj - j) for some j, we can just binary search the index j where when x = (aj - j), the change first turns positive. This is the minimum of cost(x, i, k). Then, we just need to calculate cost(aj - j, i, k).

    To do both, we store in a segment tree two values. For an interval [x, y] in the tree, we store:

    On the left side of j, the absolute value does nothing, and on its right side, it multiplies by  - 1. Therefore, we can easily calculate the cost.

    My solution is O(n log(n)^2), but a O(n log(n)) solution can be easily achieved by doing the binary search inside the segment tree.

    Code: 43339602

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

Thank you for the round, I really like the problems! Although I have no idea about Div.2 DEF, but thank you for the round!

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

Hi, This is regarding solution 43335491 for the problem 1058D - Vasya and Triangle , I have solved this question on my own ......I also matched my solution with 43330317 yes we have same variables declared due to which this misunderstanding took place and I m wrongly penalised....but as you can see there is a lot difference in my templates and him....which I always use. This is just a coincindence and I am Innocent. Kindly consider my submission. Thank you.

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

    Even with the different templates the main code is the same and that's definitive proof it's plagiarism

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

Submission 43333246

What those weird loops are for? Cheat detection evasion? The user did that regularly on their submissions.

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

    I think it is

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

      I do hope actions will be taken against them, if they are indeed cheating

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

My code is giving correct answer on local compiler but giving false answer on codeforces compiler. My whole contest went bad due to this error. Atleast my rating should be reverted back. 43309972

I checked test case 10 on codeblocks compiler as well as codechef IDE. Both of them are giving output as "Yes". My code is completely correct but still got WA.

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

    "Atleast my rating should be reverted back" "My code is completely correct"

    Stop with the trash attitude, you made a mistake, just own it.

    Here, i modified your code and it got accepted: https://codeforces.net/contest/1058/submission/43347029

    You had undefined behavior when accessing prefix_sum[pos] when pos = -1, so the output is never guaranteed to be the same.

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

      I didn't know there was undefined beahviour because as I said online compilers as well as codeblocks was giving me the correct answer, that's why I though my code was correct.

      If my code was wrong which you very correctly pointed out that it is, I wouldn't have written this comment. Thanks for your help.

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

I've solved div1 A

And I have a question, can anyone help me?

My solution of div1A used a valuable called "y1" , but I forgot to "define y1 _____y1".

And I passed the samples, pretests and main tests.

Why?

Here is a link of my solution :

![](http://codeforces.net/contest/1053/submission/43301181)

UPD: My question has already been solved.

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

I solved Div1C at 01:59:36, but Codeforces was down at that time... This is my first time to solve Div1C during a contest... QAQ

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

When there will be a list of those who have passed to the final?

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

Div.1 and Div.2 top 1 are both Chinese! They are sooo good at math (and coding)!

→ Reply