reality's blog

By reality, history, 4 months 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 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

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

»
4 months 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.

»
4 months ago, # |
  Vote: I like it -12 Vote: I do not like it

Good luck to everyone!

»
4 months 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 :)

»
4 months ago, # |
  Vote: I like it -6 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +50 Vote: I do not like it

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +9 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +27 Vote: I do not like it

    Hard rounds are good because you always learn something new.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

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

      • »
        »
        »
        »
        4 months 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?

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it +14 Vote: I do not like it

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

    • »
      »
      »
      4 months 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?

»
4 months ago, # |
  Vote: I like it -28 Vote: I do not like it

Is it rated, you know.

  • »
    »
    4 months 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 :/

»
4 months 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! (:

»
4 months ago, # |
  Vote: I like it +4 Vote: I do not like it

I love this scoring distribution :)

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

God Bless Let's go...

»
4 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Queue already 45 pages long...

»
4 months ago, # |
  Vote: I like it +4 Vote: I do not like it

queue :'(

»
4 months ago, # |
  Vote: I like it +2 Vote: I do not like it

This queue can make round unrated

»
4 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Queue. :(

»
4 months 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.

»
4 months 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! :/

»
4 months 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 ???

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What a delay...

»
4 months ago, # |
  Vote: I like it -11 Vote: I do not like it

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

»
4 months 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.com/problemset/problem/23/C

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    anyone who gave up and start reading comments and blogs!

  • »
    »
    4 months ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    They are not the same.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      I didnt say they are same

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why did you stop participating?

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        To stay out of cyan :) That place is scary

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          I was competing with you and always checked your score. Now I miss that =)

          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Maybe one day when I can be more courageous, I will submit again :)

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

    How do you find such problems? Did you do it before or did you make a google search?

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hint : He's actually in div 1.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it +20 Vote: I do not like it

        I am div 1 but I didnt find it. So I am a fake div 1 ????

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I didn't say that.

          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            Then what is the relation between being in div 1 and finding the problem ? As you gave it as a hint.

            • »
              »
              »
              »
              »
              »
              »
              4 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Chances of having solved it previously is higher.

              • »
                »
                »
                »
                »
                »
                »
                »
                4 months ago, # ^ |
                Rev. 2   Vote: I like it 0 Vote: I do not like it

                Well you are saying it in certainty but not "higher chance".

              • »
                »
                »
                »
                »
                »
                »
                »
                4 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                even if he solved it, I think it is remarkable to be able to be able to find the problem. I cant remember which contest half the problems I solved is at.

»
4 months ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

A pretest 8 Damnnnn

»
4 months ago, # |
  Vote: I like it -19 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +8 Vote: I do not like it

How do I do C?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    You can make them all multiples of 2.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But this is always minimal?

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
      • »
        »
        »
        »
        4 months 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

    • »
      »
      »
      4 months 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.

      • »
        »
        »
        »
        4 months 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

    • »
      »
      »
      4 months 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?

  • »
    »
    4 months 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.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
4 months ago, # |
  Vote: I like it +4 Vote: I do not like it

How to solve D?

  • »
    »
    4 months 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 ....

    • »
      »
      »
      4 months 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

  • »
    »
    4 months 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

»
4 months ago, # |
  Vote: I like it +9 Vote: I do not like it

How the hell do you solve C ???

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    if gcd is 1, make all the numbers even.

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it -40 Vote: I do not like it

        1 1

        This case is where ans is NO.

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it +21 Vote: I do not like it

          n >= 2

        • »
          »
          »
          »
          »
          4 months 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.
          
        • »
          »
          »
          »
          »
          4 months 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

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        0 0

      • »
        »
        »
        »
        4 months 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.

        • »
          »
          »
          »
          »
          4 months 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

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      less than two

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

      • »
        »
        »
        »
        4 months 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.

        • »
          »
          »
          »
          »
          4 months 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

»
4 months 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?

»
4 months ago, # |
  Vote: I like it +41 Vote: I do not like it

sequences sequences everywhere

»
4 months ago, # |
Rev. 2   Vote: I like it -6 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the hack case for C?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    2 7 14

  • »
    »
    4 months 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.

  • »
    »
    4 months 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
    
»
4 months 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 :((

»
4 months ago, # |
  Vote: I like it +6 Vote: I do not like it

How to solve A ?

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

»
4 months 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

  • »
    »
    4 months 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.

  • »
    »
    4 months 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.

»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

is there a "NO" case in C?

»
4 months 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.

»
4 months ago, # |
  Vote: I like it +7 Vote: I do not like it

What was test-case 5 for problem A?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Something like abccba. Answer is NO.

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

    I guess it like this: abcba

    Answer is YES.

  • »
    »
    4 months 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 :(

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

      OH No! I spend 2 hours debugging my code

    • »
      »
      »
      4 months 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

      • »
        »
        »
        »
        4 months 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 ;)

»
4 months 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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    omg that thing worked

  • »
    »
    4 months 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

»
4 months 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.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is E just a simple topological sort?

»
4 months ago, # |
  Vote: I like it +5 Vote: I do not like it

how to approach D?

»
4 months 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 :(

»
4 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Question B, WA at test 94 :)

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

        Yeah...a smile coupled with learning something new sounds like a good idea to me. :)

»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve D? Any hints?

  • »
    »
    4 months 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:)

»
4 months 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.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Very cool problems!

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Any deterministic solution for D?

  • »
    »
    4 months 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).

»
4 months ago, # |
  Vote: I like it +15 Vote: I do not like it

LOL, are u serious about D tests ? 26562304

»
4 months 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.com/contest/798/submission/26561705

  • »
    »
    4 months 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?

    • »
      »
      »
      4 months 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.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.

    • »
      »
      »
      4 months 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 .

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

  • »
    »
    4 months 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% :) )

»
4 months 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".

»
4 months ago, # |
  Vote: I like it -15 Vote: I do not like it

So easy E, why only 3 ACs?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Because it's not easy.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Maybe

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      From the editorial, it looks like it was just a topological sort. People were stuck on D for long time, plus long queues.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        toposort + avoiding quadratic time

»
4 months 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 :)

»
4 months 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 :(

»
4 months 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.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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