allllekssssa's blog

Invitation to CodeChef August Lunchtime 2018!
By allllekssssa, history, 6 years ago, In English

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 [email protected])

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!

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

Comments Comments (26)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

UPD: One hour before contest !

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

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

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +28 Vote: I do not like it

yet another greedy casework problem >_<

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          got it

          → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            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

            → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

How to solve the last 3 problems?

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

how to solve problem JAGAM

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      lokpati see this...exactly this solution struck to me the moment I read the question.

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

How to solve "GukiZ Has More Candies " ?

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

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?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you disprove it or give a counter example.

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

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

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

        You did.

        → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

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

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

→ Reply