Если вы используете C++, пожалуйста, выберите в качестве компилятора при отправке решения: C++14 (GCC 6-32) или C++17 (GCC 7-32). ×

Блог пользователя I_Love_Tina

Автор I_Love_Tina, история, 7 лет назад, По-английски

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

  • Проголосовать: нравится
  • +240
  • Проголосовать: не нравится

»
7 лет назад, # |
Rev. 4   Проголосовать: нравится +70 Проголосовать: не нравится

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

UPD: It is Fixed now.

»
7 лет назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

Good luck to everyone!

»
7 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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 :)

»
7 лет назад, # |
  Проголосовать: нравится +50 Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +27 Проголосовать: не нравится

    Hard rounds are good because you always learn something new.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +14 Проголосовать: не нравится

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

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится -6 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится -28 Проголосовать: не нравится

Is it rated, you know.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    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 :/

»
7 лет назад, # |
  Проголосовать: нравится +38 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

I love this scoring distribution :)

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

God Bless Let's go...

»
7 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Queue already 45 pages long...

»
7 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

queue :'(

»
7 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

This queue can make round unrated

»
7 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Queue. :(

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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 ???

»
7 лет назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +52 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

A pretest 8 Damnnnn

»
7 лет назад, # |
  Проголосовать: нравится -19 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Народ как решаеться 2 задача? каким методом ? тут что то связання с префикс функциями?

»
7 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

How do I do C?

»
7 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

How to solve D?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 ....

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
    Rev. 6   Проголосовать: нравится +19 Проголосовать: не нравится

    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

»
7 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

How the hell do you solve C ???

»
7 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +41 Проголосовать: не нравится

sequences sequences everywhere

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What's the hack case for C?

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

How to solve A ?

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

is there a "NO" case in C?

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Как задача D решается?

»
7 лет назад, # |
Rev. 9   Проголосовать: нравится +7 Проголосовать: не нравится

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.

»
7 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

What was test-case 5 for problem A?

»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    omg that thing worked

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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

»
7 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is E just a simple topological sort?

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

how to approach D?

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 :(

»
7 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Question B, WA at test 94 :)

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

How to solve D? Any hints?

  • »
    »
    7 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    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:)

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

на чем B падает?

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Very cool problems!

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Any deterministic solution for D?

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

    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).

»
7 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

LOL, are u serious about D tests ? 26562304

»
7 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

I passed D using randomized algorithm.

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

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

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    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?

    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 5   Проголосовать: нравится +6 Проголосовать: не нравится

      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.com/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.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

      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 .

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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% :) )

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

So easy E, why only 3 ACs?

»
7 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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 :)

»
7 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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 :(

»
7 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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.