I_Love_Tina's blog

Codeforces Round #410 (Div. 2)
By I_Love_Tina, history, 8 years ago, In English

Hi everyone!

I'm pleased to announce Codeforces Round #410 (Div. 2) that will take place on Friday, 17:35 MSK. I'm the writer of the round.

I'd like to say thanks to Alex netman Vistyazh and Marcel please_delete_account Bezdrighin for feedback and help in preparing the round and to MikeMirzayanov for awesome platforms : Codeforces and Polygon.

I hope you will like the problems.

Good luck and have fun!

UPD: Scoring distribution: 500 — 1000 — 1500 — 2000 — 2500

UPD 2. The round is finished. Congratulations to winners:

Div 2:

  1. Gonens

  2. Blue_Sky.

  3. kimnoia

  4. Guy

  5. jtnydv25

Div 1:

  1. OnionPringles

  2. unused

  3. uwi

  4. Reyna

  5. alexrcoleman

Editorial: Link

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

Comments Comments (146)
| Write comment?
»
8 years ago, # |
← Rev. 4   Vote: I like it +70 Vote: I do not like it

Why are Div.1 participants able to register in-contest and are not shown out of competition?

UPD: It is Fixed now.

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

Good luck to everyone!

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

Really Nice & Short Announcement... Hope to have the Problems will be similar to the size of announcement and interesting. All the best for all the contestants :)

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

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

    Don't worry :) This bug will be fixed soon.

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

I am afraid because your previous round was damn hard. :(

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

    Hard rounds are good because you always learn something new.

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

      But why learn things if it means losing juicy rating /s

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

        Then what for are you there?? To solve easy problems and get nice colour or to learn new interesting algorithms?

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

          Both. I mean, getting nice color and to learn new interesting algorithm

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

      that's true. but even A only ~60% solved in his previous round. wasn't that pathetic?

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

Is it rated, you know.

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

    That's not interesting and cool if you ask this question Do you think it's funny? Or you are so cool? Why the hell people don't understand this shit :/

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

It maybe the last round before retired,i hope this round quickly judged. Better rating! (:

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

I love this scoring distribution :)

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

God Bless Let's go...

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

Queue already 45 pages long...

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

queue :'(

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

This queue can make round unrated

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

Queue. :(

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

I submit, get WA in like 10 mins and lose points. Do smth please.

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

This queue made me lose 10-15 min, thinking that my solution is correct! :/

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

I tried to submit the solution for Q- A but after clicking on submit button it's not get submitted and the cursor is still moving from last 45 min...but my solution is still not in the queue list even why ???

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

WHAT IS PRETEST 8 IN PROBLEM A ITS DEPRESSING...

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

guys look at this Problem after Contest its really interesting Problem :) http://codeforces.net/problemset/problem/23/C

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

A pretest 8 Damnnnn

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

Interesting round! First time I solved all the problems (mentally) :D

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

How do I do C?

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

    You can make them all multiples of 2.

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

      But this is always minimal?

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

        Yes

        click

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

        Unless gcd is already greater than 1, yes this is always minimal. Because by the operation mentioned in the problem, you can never introduce a new odd factor which wasn't present previously in the array (you can easily prove this by setting a-b=k*n1 and a+b=k*n2 where k is odd , figure out how n1 or n2 will look like). The best you can do is introduce an even factor, namely 2

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

      I tried to do this but it gave me WA, though maybe my code is just wrong.

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

        check the following test:

        6
1 2 1 1 1 2

        Edit: Answer should be 5

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

      I wrote something like this, but it failed in pretest #4, did I just fail to implement properly?

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

    If gcd is greater than 1 the answer is 0, otherwise the only solution is to transform all the numbers to even numbers so they are dividable by 2.

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

How to solve D?

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

    The best-case scenario is to take the biggest K. After that I try to randomize the solution's sequence of length K, but TLE ....

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

      I did that and got AC :) maybe your random-sequence generation is too slow

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

    Fix k to floor(n / 2) + 1, then sort the array with a or b together. then choose 1,3,5,...,n (maybe one more number which optimize the answer, it depends on the parity of 'n') for array a obviously bigger than sum / 2. There is two condition now:

    1. if sum of b(all of the index we chosed) is also fit the condition, print answer
    2. if not, then (2, 4, 6, ...) + (one optimize the two sum) must fit the condition

    I almost solve it in time and submit in the last minute, but i forget to output k.....TT

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

How the hell do you solve C ???

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

    if gcd is 1, make all the numbers even.

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

    I proved this:

    a[i] = t*k1, a[i+1] = 2*k2 where gcd( a[i], a[i+1] ) = 1, then you can't make their gcd > 1 in less than two moves :)

    Proof:Let's show that it can't be made in only one move.

    b[i] = a[i] — a[i+1] = t*k1 — 2*k2,
    b[i+1] = a[i] + a[i+1] = t*k1 + 2*k2

    b[i+1] = b[i] + 4*k2.

    Assume b[i] = c*k2, for b[i] and b[i+1] to have gcd > 1 in this move itself. Notice that b[i] is odd.

    b[i] = t*k1 — 2*k2, b[i] = c*k2. This meaans t*k1 = (c+2)*k2.

    gcd(k1, k2)=1 from our initial condition that gcd=1. This means t=k2. But this contradicts the same assumption.

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

      There's no case where the answer is NO, right?

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

        1 1

        This case is where ans is NO.

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

          n >= 2

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

          Your testcase isn't valid.

          The first line contains a single integer n (2 ≤ n ≤ 100 000) — length of sequence A.
          → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          nope. answer is 1. after 1 operation- it turns 0 2 gcd(0,2)=2

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

        0 0

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

        True. [odd even] can be made [even even] in two moves, and [odd odd] can have either already gcd>1 or they can be made so in one move.

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

          ahhh i didn't pen and paper for [even even], i thought that if [even even] exist the answer will be NO, ahhhh what a day

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

      less than two

      do you mean <= or < 2? <= right?

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

        You can't make in less than 2, which means you CAN make in >= 2 moves by simply adding them together twice.

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

          Yes, sry I misread :D

          So 2 is always possible, interesting

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

I wrote something stupid for C and it worked. But still, could someone tell me the actual solution?

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

sequences sequences everywhere

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

What's the hack case for C?

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

    2 7 14

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

    Maybe n=2, a={3, 3}. Case of gcd(a1, a2,..., an) > 1, the answer is 0.

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 3   Vote: I like it +1 Vote: I do not like it 
    n = 3
1 1 1 => 3
1 1 2 => 1
1 2 1 => 4
1 2 2 => 2
2 1 1 => 1
2 1 2 => 2
2 2 1 => 2
2 2 2 => 0
    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

How to solve D? I think it is too hard for D problems in div 2 :((

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

How to solve A ?

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

My greedy algorithm for D works like this : sort by value of a in descending, then store it in temporary array A' sort by value of b in descending, then store it in temporary array B'

then greedily I pick between the larger point in A'[i] and B'[j] if the i-th and j-th index haven't been picked already. Wrong answer on pretest 7, can anyone give me a counter case for my algorithm?

Submission : Here

EDITED : I change my solution with random shuffle and get accepted. Looks like Luck beats hard work this time

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

    fonmagnus I also had the same mistake . What I did was pick max in A and B alternatively . It passed 7 but failed in pretest 8 :).

    Btw I think I got my mistake for 8 and tried submitting it but contest ended as my internet was a bit slow.

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

    I also checked that if I choose k-1 largest values in sorted A, what is the minimum value in the remaining sorted A that I can choose, and I discard all values( along with their Bs ) that are lesser than this smallest value.

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

is there a "NO" case in C?

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

My idea for problem C.

If their GCD is > 1 then for sure the answer is 0.

If not then we want to make their GCD > 1.

Assume that we want to make their GCD = x. Where x > 1

Then there should Exist an a[i] such that a[i] % x != 0 (else their gcd would have been >= x which is > 1).

So now we need to change a[i] to something which is divisible by x.

Assume that we will make the new a[i] using a[i + 1], by deleting both and putting a[i + 1] — a[i], a[i] + a[i + 1]

if initially a[i] % x = A and a[i + 1] % x = B, we need B — A to be 0 (B = A) because we need (a[i + 1] — a[i]) % x to be zero.

Then now we know that A should be equal to B, and since B + A = x or now we can say (A + A = x) then now we know that our x should also be even. and if x is even then we need their gcd to be divisible by 2.

Then try to make them all divisible by two with the minimum cost.

Then if there exist an a[i] % 2 = 1 & a[i + 1] % 2 = 1 then make them together with cost 1. else you will need to make every a[i] % 2 = 1 with the number before or after it with cost 2.

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

What was test-case 5 for problem A?

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

    Something like abccba. Answer is NO.

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

    I guess it like this: abcba

    Answer is YES.

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

    If string was already palindromic, it would be NO, since the problem says exactly one letter, not <= one letter. I also spent quite a while on this same bug :(

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

      OH No! I spend 2 hours debugging my code

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

      Not if the string is of odd length, one can change the centre character

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

        True that. Luckily my code is brute force, so I don't have that as a bug ;)

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

My solution of C:

1) find gcd of the sequence

2) go through the sequence two times: a) check for pairs (odd, odd) b) check for pairs(odd, even) and (even, odd)

but i still don't understand is it ok or not

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

    omg that thing worked

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

    so full explaination:

    check if the gcd of the seq is > 1 than ans is: YES 0

    else: go through the seq and do the operation once on pairs where both nums are odd

    go through the seq again and do the operation twice on pairs where one num is even and one num is odd

    answer is: YES

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

Very good tasks ! Harder than usual, I couldn't invent anything normal for fourth problem. Still I believe I could get AC with choosing random subarrays ( on first view and some easy probability it looks that you have 50% chance to guess answer each time), but I start to implement that idea very late and of course it is not expected solution.

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

Is E just a simple topological sort?

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

how to approach D?

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

Hi, Can anyone prove that making all numbers even in problem C will yield an optimal solution. I figured that but could not prove it :(

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

Question B, WA at test 94 :)

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

    What are you so happy about? Is 94 some lucky number? :)

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

      No. Just because am speechless. So why not just smile :)

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

How to solve D? Any hints?

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

    I used random_shuffle to solve it. In the example:

    100000

    1 1 1 1 ... 1 1 1 2

    2 1 1 1 ... 1 1 1 1

    We could easily find out that we should choose as many numbers as possible.

    So we choose 50001 numbers.

    Also, we could find out that we must choose number 2.

    So, the possibility of choosing the number 2 in the array A is:

    1-C(99999,50001)/C(100000,50001),approximately 1/2.

    So, the possibility of choosing the right answer is 1/4.

    We can see that the possibility is actually very high. I hope that my solution could help you:)

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

What a weak acmer I am!! I got 4 WA at the first problem.

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

Very cool problems!

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

Any deterministic solution for D?

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

    Check mine.

    Actually it is some constructive + working with different cases.

    Start with sorting all items by weight in B's in descending order, then declare all even-indexed (0, 2, ..) elements as "set1" and other as "set2".

    First observation: total in B's of "set1" is greater or equal then total of "set2", and the equality is only possible for even n and all B's equal.

    Second observation: total of "set1" minus total of "set2" is no more than largest (first) element of "set1", (draw a pic).

    Then calculate total in A's of "set1" and "set2" and declare one as answer, possibly adding one element from the other set. (For details check mine solution -- it is checking all cases).

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

LOL, are u serious about D tests ? 26562304

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

I passed D using randomized algorithm.

Just random k elements from A and B with equal indexes until correct answer got.

http://codeforces.net/contest/798/submission/26561705

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

    What's the complexity of that? how many time it spends finding the solution and why did you decide to code it? I mean, what was your insight?

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

      There is another similar problem using randomized algorithm in Codeforces

      Wait a minute, I'm seaching this problem.

      I will post this problem later.

      http://codeforces.net/problemset/problem/364/D

      Finally， I found it.

      It is really a hard task to find one problem from this large problemset.

      Almost one year ago, someone ask for me this problem. I do not think it can be solved by traditional algorithm. I mean maybe we can random.

      There is a simliar word in Today's Promblem. It's HALF. So， I try it with similar algorithm.

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

      These kind of randomized algorithms are called as Las Vegas algorithms . These algorithms always produces the correct result but gambles with the resources used for the computation .

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

    Here is another randomized solution!!! http://codeforces.net/contest/798/submission/26560973

    look at it :p . I found this pretty cool!

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

    Can anyone calculate the probability of getting the right answer? I think it's cool, and I didn't work this algorithm out during contest. Maybe we can prove this algorithm is right? (if the probability of getting the right answer if very big, like 99.999% :) )

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

WTF!! I didn't submit my solution for problem C because I didn't find the case for "NO".

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

So easy E, why only 3 ACs?

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

For problem D, anybody know how to approximate the probability of not getting a valid subset while taking one randomly? I got AC but it was just a feeling, couldn't get the probability

thanks :)

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

Sigh, I was solving the wrong problem A the whole time. I was solving "change at most one letter" instead of "exactly one letter", even if that was in bold in the problem statement :(

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

i am not able to submit solution.On clicking the submit button,nothing is happening.i am not getting why this is happening but because of this am not able to give contest nd also it is not sumbitting after contest for any of the problem.

→ Reply