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

Автор reality, история, 8 месяцев назад, По-английски,

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 yosei-san 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. RAG3

  5. jtnydv25

Div 1:

  1. OnionPringles

  2. unused

  3. uwi

  4. Reyna

  5. alexrcoleman

Editorial: Link

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

»
8 месяцев назад, # |
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.

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

Good luck to everyone!

»
8 месяцев назад, # |
  Проголосовать: нравится +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 :)

»
8 месяцев назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

I hope I won't feel too much down tomorrow :|

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

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

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

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

    Hard rounds are good because you always learn something new.

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

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

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

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

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

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

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

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

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

Is it rated, you know.

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится +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 :/

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

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

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

I love this scoring distribution :)

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

God Bless Let's go...

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

Queue already 45 pages long...

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

queue :'(

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

This queue can make round unrated

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

Queue. :(

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

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

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

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

»
8 месяцев назад, # |
  Проголосовать: нравится +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 ???

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

    same is happening with me too. Trying to submit the solution from past 40 mins. Not Working :(

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

What a delay...

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

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

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

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

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

A pretest 8 Damnnnn

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

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

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

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

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

    перебор

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

      эх зря не попытался ( думал по времени не пройдет

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

        Я тоже так сперва думал, но потом перемножил 3 числа 50 * 50 * 50 и успокоился.

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

          я также перемножил эти 3 числа но не успокоился думал префиксами решаються

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

          там 50 * 50 * 50 * 50

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

How do I do C?

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

    You can make them all multiples of 2.

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

      But this is always minimal?

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

        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

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

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

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

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

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

    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.

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

    This is what I did: NO is never an answer because you can make all of them multiples of 2. So check the gcd of all the numbers. If it is >1 we are done. Else for every odd number try to find an adjacent odd number. Now you can do the given operation to get multiples of two. If an odd number does not have an adjacent odd number then choose an adjacent even number and apply the operation 2 times.

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

How to solve D?

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 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 ....

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

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

  • »
    »
    8 месяцев назад, # ^ |
    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

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

How the hell do you solve C ???

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

    if gcd is 1, make all the numbers even.

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

    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.

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

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

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

sequences sequences everywhere

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

How to solve C?

I can get gcd using Euclidean Algorithm(if you know any better idea, can I ask you to tell any idea).

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

What's the hack case for C?

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

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

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

How to solve A ?

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

    remember that we must change a character. first compare s[0.. n/2-1] and s[n-1.. n-1-(n/2-1)]

    YES : only one difference || ( n % 2 == 1 && every character is equal )

    NO : (Actually using 'else') ( n % 2 == 0 && every character is equal ) || more than 1 differences

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

    Go from 0 to string.size /2, check how many pair char is different, let's call it n.

    if n == 1 => YES

    else if n == 0 && string.size % 2 == 1 ==> YES // most failed here, included me.

    else => NO.

»
8 месяцев назад, # |
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

  • »
    »
    8 месяцев назад, # ^ |
    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.

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 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.

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

is there a "NO" case in C?

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

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

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

»
8 месяцев назад, # |
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.

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

What was test-case 5 for problem A?

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

    Something like abccba. Answer is NO.

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

    I guess it like this: abcba

    Answer is YES.

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

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

»
8 месяцев назад, # |
  Проголосовать: нравится +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

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

    omg that thing worked

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится +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

»
8 месяцев назад, # |
  Проголосовать: нравится +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.

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

Is E just a simple topological sort?

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

how to approach D?

»
8 месяцев назад, # |
  Проголосовать: нравится 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 :(

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

Question B, WA at test 94 :)

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

How to solve D? Any hints?

  • »
    »
    8 месяцев назад, # ^ |
    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:)

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

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

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

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

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

Very cool problems!

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

Any deterministic solution for D?

  • »
    »
    8 месяцев назад, # ^ |
    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).

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

LOL, are u serious about D tests ? 26562304

»
8 месяцев назад, # |
  Проголосовать: нравится +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

  • »
    »
    8 месяцев назад, # ^ |
    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?

    • »
      »
      »
      8 месяцев назад, # ^ |
      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.

    • »
      »
      »
      8 месяцев назад, # ^ |
        Проголосовать: нравится +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 .

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

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

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

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 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% :) )

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

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

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

So easy E, why only 3 ACs?

»
8 месяцев назад, # |
  Проголосовать: нравится +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 :)

»
8 месяцев назад, # |
  Проголосовать: нравится +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 :(

»
8 месяцев назад, # |
  Проголосовать: нравится +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.

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

I lost 1 hour to implement DFS in java for B but I got TLE on case 9... Anyone know why? https://pastebin.com/B42rBZgQ