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

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

Hello CodeForces Community!

We are back with another set of brain racking problems this August Lunchtime 2018, a three-hour test to knack your coding abilities. There are more reasons to be delighted as ShareChat has opened some exciting job opportunities for professionals across the globe! More details can be found on the August Lunchtime contest page.

This time on the problem setting panel are:

  • Problem Setter: kingofnumbers (Hasan Jaddouh), allllekssssa (Aleksa Plavsic)
  • Problem Tester and Editorialist: Pepe.Chess (Hussain Kara Fallah)
  • Statement Verifier: Xellos (Jakub Safin)
  • Russian Translator: Mediocrity (Fedor Korobeinikov)
  • Mandarin Translator: huzecong (Hu Zecong)
  • Hindi Translator: Srijan Dubey
  • Vietnamese Translator: VNOI Team

Contest Details:

Time: 25th August 2018 (1930 hrs — 2230 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

Contest link: https://www.codechef.com/LTIME63

Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.

Prizes: Top 10 performers in Global and Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here: https://discuss.codechef.com/questions/51999/how-do-i-win-a-codechef-goodie. (For those who have not yet received their previous winning, please send an email to winners@codechef.com)

Good Luck!

Hope to see you at the contest!

UPD He did it again! uwi solved everything in last minutes and got the first place! Congratulations!

TOP 5:

uwi

Um_nik

KrK

Mrip

step_by_step

Big congratulation to winner of div 2 round receed.

Thanks for participation!

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

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

UPD: One hour before contest !

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

nice problem c but b was a bit bad,implementation-_-. nice problemset.

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

yet another greedy casework problem >_<

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

    I absolutely hated that problem. I've been getting WA for the past 1 hour, and can't even pass the 1st two sub tasks -_-

    The two groups problem was nice though.

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

      what is full solution for that,i only got 50 for X and two groups

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

        I'm not very good at explaining, but I'll try.

        First, try to visualise if there was a single array and you wanted to minimise (max-min). Bring all elements of the array in range [0,x-1] by taking modulo x, and count the number of operations done so far, let it be op1. (this count will be needed in full solution). Now, you have O(n) candidates for solution. sort the array after taking modulo, and you can see that either the answer is (arr[n]-arr[1]) or the answer will be (arr[i-1]-(arr[i]-x)) if we do one more operation, do this in decreasing order of i.

        After doing this for both arrays, we have 2 new arrays a[n] and b[m]. a[i] represents (max-min) after doing op1+i operations, and b[] is the same for the other array. Now take another observation, if I do -x on both arrays on every element my answer doesn't change, they're basically dummy operations. Now let's say you want a[i] + b[j] to be your final answer, that means you have done (op1+i) operations on 1st array and (op2+j) operations on 2nd array. Now you want to make them the same count, by doing the dummy operations. By bezout identity, you can see that it can be done if (op1+i)%gcd(m,n) == (op2+j)%gcd(m,n). then a[i]+b[j] can be one answer. Now simply divide both array elements into modulo classes of gcd(m,n), take minimum for each class, and update final answer.

        You can look at my code if you're having trouble understanding this.

        https://www.codechef.com/viewsolution/19864707

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

          got it

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

          can you explain why do we need to bring all elements of array in range [0,x-1]?

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

            For a single array, let's write arr[i] = a*x+b.

            If max(a)-min(a) > 1, we can always improve our answer.

            We brought all elements in [0,x-1] for ONE possible candidate answer, the most trivial one.

            After that we do -x on the maximum value, take the difference again, do -x on new maximum, take the difference again, and so on. After n such operations, we'll get our original reduced array back, with all elements now having -x done. So, our answer has to be amongst the previous O(n) candidates

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

    The task was much harder than I expected! I solved it and wrote correct code in 20 minutes, so I didn't see so many tricky cases, I had three "tricky" ifs (and case like x<n is obvious).

    At beginning, I planned to give next version:

    For each index i, we must have at least two indices j and l on distance not bigger than D.

    And then I realized 14 different cases and change it in this easier task(and much nicer than that version :P).

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

How to solve the last 3 problems?

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

how to solve problem JAGAM

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

    The game either lasts 2 turns or ends in a tie.

    1) If the first player can win in 1 move, print 1.

    2) If every possible move for the first player results in a state where the second player can win in 1 move, print 2.

    3) Otherwise, every player can do the opposite of his opponent's move, and the game ends in a tie

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

How to solve "GukiZ Has More Candies " ?

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

How to solve X and two groups?

I was using priority queue, in each turn reducing the maximum to less than second maximum by subtracting a factor of x from both top element. My idea was that in less than or equal to 2*(n + m) iterations we will obtain the optimum value, because after that the relative order will repeat.

But I was constantly getting WA on last subtask. Any reason why?

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

    My idea was that in less than or equal to 2*(n + m) iterations we will obtain the optimum value, because after that the relative order will repeat.

    That statement, unfortunately, isn't correct :(

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

      Can you disprove it or give a counter example.

      I actually proved it but don't know if I missed something

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

        Imagine that you have all the numbers belonging in the interval [0, x - 1] Let's sort both arrays, and make two new arrays, sdif and tdif , where sdifi = si + 1 - si (going circular), and same thing goes for the other array, Now, every move you make is a circular rotation of both arrays, and the current answer you're getting is 2 * x - sdifo - tdifo. For example, if gcd(n, m) = 1, we could have every possible combination of elements as first elements of the arrays (n * m combinations overall). I think this is a good counterexample and a good hint to the actual solution.

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

        You did.

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

        Take the set 1 1000000000 and x=1. It's clear that you need to make 10^9-1 moves, but you just make 2.

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

When the editorials will be out?
UPD: Still waiting for editorials :(