I_Love_Tina's blog

Codeforces Round #410 (Div. 2)
By I_Love_Tina, history, 9 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?
»
9 years ago, hide # |
← 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
»
9 years ago, hide # |
 
Vote: I like it -12 Vote: I do not like it

Good luck to everyone!

→ Reply
»
9 years ago, hide # |
 
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
»
9 years ago, hide # |
 
Vote: I like it +50 Vote: I do not like it

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

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

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

Is it rated, you know.

→ Reply
  • »
    »
    9 years ago, hide # ^ |
     
    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
»
9 years ago, hide # |
 
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
»
9 years ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

I love this scoring distribution :)

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

God Bless Let's go...

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

Queue already 45 pages long...

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

queue :'(

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

This queue can make round unrated

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

Queue. :(

→ Reply
»
9 years ago, hide # |
 
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
»
9 years ago, hide # |
 
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
»
9 years ago, hide # |
 
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
»
9 years ago, hide # |
 
Vote: I like it -11 Vote: I do not like it

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

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

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

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

A pretest 8 Damnnnn

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

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

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

How do I do C?

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

How to solve D?

→ Reply
  • »
    »
    9 years ago, hide # ^ |
     
    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
  • »
    »
    9 years ago, hide # ^ |
    ← 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
»
9 years ago, hide # |
 
Vote: I like it +9 Vote: I do not like it

How the hell do you solve C ???

→ Reply
»
9 years ago, hide # |
 
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
»
9 years ago, hide # |
 
Vote: I like it +41 Vote: I do not like it

sequences sequences everywhere

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

What's the hack case for C?

→ Reply
»
9 years ago, hide # |
← 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
»
9 years ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

How to solve A ?

→ Reply
»
9 years ago, hide # |
← 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
  • »
    »
    9 years ago, hide # ^ |
    ← 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
  • »
    »
    9 years ago, hide # ^ |
     
    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
»
9 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

is there a "NO" case in C?

→ Reply
»
9 years ago, hide # |
← 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
»
9 years ago, hide # |
 
Vote: I like it +7 Vote: I do not like it

What was test-case 5 for problem A?

→ Reply
»
9 years ago, hide # |
 
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
  • »
    »
    9 years ago, hide # ^ |
     
    Vote: I like it +3 Vote: I do not like it

    omg that thing worked

    → Reply
  • »
    »
    9 years ago, hide # ^ |
     
    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
»
9 years ago, hide # |
 
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
»
9 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Is E just a simple topological sort?

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

how to approach D?

→ Reply
»
9 years ago, hide # |
 
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
»
9 years ago, hide # |
 
Vote: I like it +10 Vote: I do not like it

Question B, WA at test 94 :)

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

How to solve D? Any hints?

→ Reply
  • »
    »
    9 years ago, hide # ^ |
    ← 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
»
9 years ago, hide # |
 
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
»
9 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Very cool problems!

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

Any deterministic solution for D?

→ Reply
  • »
    »
    9 years ago, hide # ^ |
    ← 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
»
9 years ago, hide # |
 
Vote: I like it +15 Vote: I do not like it

LOL, are u serious about D tests ? 26562304

→ Reply
»
9 years ago, hide # |
 
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://mirror.codeforces.com/contest/798/submission/26561705

→ Reply
»
9 years ago, hide # |
 
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
»
9 years ago, hide # |
 
Vote: I like it -15 Vote: I do not like it

So easy E, why only 3 ACs?

→ Reply
»
9 years ago, hide # |
 
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
»
9 years ago, hide # |
 
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
»
9 years ago, hide # |
 
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