teja349's blog

Invitation to CodeChef June Cook-Off 2019 sponsored by ShareChat!
By teja349, history, 6 years ago, In English

Greetings Codeforces Community!

CodeChef’s June CookOff, sponsored by ShareChat is almost here. Prepare to face the problem set that we have been busy brewing. This is your opportunity to showcase your programming skills amidst the best programmers in the world and better your ratings.

As a bonus: ShareChat — India’s fastest growing social network is seeking both interns and full-time employees to join their dynamic team. To be considered for the roles, all you have to do is fill the form provided and participate in the contest. Visit the contest page for more details.

We are on the hunt for a Mandarin Translator to help translate problem statements for our monthly contests. This will be a long-term commitment with translations required thrice a month. If you think you are up to the task, then do get back to us at problems@codechef.com.

There’s no time to waste, so start flexing your programming muscle. I hope you will join your fellow programmers and enjoy the contest problems. Joining me on the problem setting panel are:

  • Setters: kingofnumbers (Hasan Jaddouh), Erfan.aa (Erfan Alimohammadi), solaimanope (Mohammad Solaiman)

  • Tester and Editorialist: teja349 (Teja Vardhan Reddy)

  • Statement Verifier: Xellos (Jakub Safin)

  • Mandarin Translator: huzecong (Hu Zecong)

  • Vietnamese Translator: Team VNOI

  • Russian Translator: Mediocrity (Fedor Korobeinikov)

  • Bengali Translator: solaimanope (Mohammad Solaiman)

  • Hindi Translator: Akash Shrivastava

Contest Details:

  • Start Date & Time: 23rd June 2019 (2130 hrs) to 24th June 2019 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone

  • Contest link: https://www.codechef.com/COOK107

  • 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 top 10 performers in Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here: https://discuss.codechef.com/t/how-do-i-win-a-codechef-goodie/7344

(For those who have not yet got their previous winning, please send an email to winners@codechef.com)

Good Luck!

Hope to see you participating!!

Happy Programming!!

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

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

Thanks for the contest!

My thoughts on Div 2: I felt the problem quality was generally strong, but the difficulty distribution could have been a bit better. In particular, it seemed like there were three easy problems, one medium-easy problem, and one particularly hard problem. Although the hard problem was particularly nice, it was a fair bit more difficult than most problems on the late end of Codechef Division 2 rounds.

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

Hi everyone. So, for question SUBSETS, my approach was as follows:

  1. Precompute (sieve) all primes upto $$$10^{\dfrac{16}{3}}$$$ which is roughly $$$220000$$$.
  2. Then I will see (i,j) pairs, such that they form not special pair.
  3. Then subtract these cases from total $$$2^N$$$.

UPD: (Adding more about how I was/am calculating bad subsets)

Example:

$$$N=4$$$, $$$A$$$$$$=$$${$$$1,4,8,20$$$}

Initialize $$$cnt=N-2=2$$$

So, first I see that $$$(1,4)$$$ has no problem, then $$$(1,8)$$$ is a problem, so I subtract $$$2^{cnt}$$$ ( number of subsets with $$$1$$$ AND $$$8$$$, and decrease $$$cnt$$$ (now $$$cnt=1$$$), then $$$(1,20)$$$ no issue.

Again $$$cnt=N-2=2$$$. Now consider $$$(4,8)$$$, since I have considered all values to left of $$$4$$$, it means if some value to left of $$$4$$$ has problem with $$$4$$$ or $$$8$$$ then I have already counted its subsets, and I shouldn't count again. So I check to left of $$$4$$$, how many values have problem with either $$$4$$$ or $$$8$$$, let's denote it as $$$done$$$. Then $$$cnt=N-2-done$$$, and $$$(4,8)$$$ is problem, so subtract $$$2^{cnt}$$$ and decrease $$$cnt$$$ for $$$(4,20)$$$. And so on.

So, in all I do this, $$$ans=2^N=16$$$.

  1. $$$(1,4)$$$ => no change
  2. $$$(1,8)$$$ => -4
  3. $$$(1,20)$$$ => no change
  4. $$$(4,8)$$$ => -2 ( 1 already counted with 4 )
  5. $$$(4,20)$$$ => -2 ( 1 already counted with 4 )
  6. $$$(8,20)$$$ => -1 ( 1 already counted with 8, 4 already counted with 8 )

So, final change is $$$(-9)$$$. $$$ans = 7$$$.

But, I had a lot of trouble calculating what to subtract. Can someone help me with this?

My code : here

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

    My solution was:
    First we can factorise numbers and create a graph where there is edge between two nodes i and j if their pair is good. Now, we can see that answer is number of cliques in this graph. So, we can use meet in the middle approach. We divide all vertices in two sets and in each set calculate for each submask for vertices if thery are a clique or not. Now we take sum over subsets of one set. And then iterate over submasks of other set. We can calculate for this submask which mask of nodes in other set which are adjacent to all nodes in this submask. So, we add the corresponding sos value to answer. I couldn't fix bugs in my solution and my pc crashed midcontest:( Finally ac in practice code

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

      Yeah I also thought about graphs at first. But I don't like graphs and also don't know a lot of tricks and am not comfortable with graphs so I didn't do it that way.

      But, yeah, I thought of the same thing, we need to find number of Complete Graphs ( I assume that is same as clique ) as subgraphs in the graph created by joining edge between indices that form good pair.

      But again, I feel (intuition) like there is simpler solution instead of doing graphs, meet in the middle and what not.

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

      I did this but i couldn't get the part with sum over subsets faster than $$$O(2^\frac{n}{2} * n^2)$$$, so it was TL. Can it be done faster?

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

        I represented graph's adjacency matrix in form of bitmasks and got $$$O(2^{n/2}*n)$$$.

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

          I mean I do that too to match first half against the second. But how does it help in precalculating the number of submasks-cliques?

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

            Let mask be mask of some subgraph you have already selected and now you want to see if some i vertex can be inserted in it. Then, if( (adj[i] and mask)==mask) then you can directly add it. So, you just need to iterate over all masks and then run a loop for which new vertex to add which is $$$O(n*2^{n/2})$$$

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

            So, it seems they went bonkers this time. Editorial is already up.

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

            SOS dp

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

      Surely they didn't intend to crash your PC. But maybe they did xD?

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

Can anyone explain the solution of Secret Recipe

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

    We essentially have two cases.

    1. The chef runs directly away from a single enemy but eventually gets caught without assistance from any other enemies. Obviously, this enemy must be faster than the chef.

    2. Two enemies run towards the chef from different directions. The chef runs to the point where the two enemies meet and gets caught when the enemies meet at that point. (If the chef can't make it to that midpoint before getting caught by one of the enemies, this is equivalent to case #1.)

    Computing the minimum time it would take for the chef to be caught in any of the Case #1 scenarios can easily be done in O(N) with some basic math. Case #2 is a bit more complicated because we have O(N^2) pairs of enemies that could help catch the chef. The problem we have now is finding the appropriate pair to catch the chef fastest.

    Surprisingly, binary search helps us accomplish this task. We binary search on the answer, the time it takes for the chef to be caught. Suppose we want to check whether the chef can be found in T seconds. Then, we pick the best enemy to run in each direction by selecting the one who will get the furthest running in that direction, based on their starting position and T times their velocity.

    If the best enemy to run towards lower positions is a different enemy from the one best suited to running towards higher positions, we can simply check whether these two chefs can meet within T seconds. If the same enemy can get to the lowest or the highest position of any of the enemies, though, we do casework on whether this particular enemy will run towards lower or higher positions. In each case, we pick the remaining enemy best at running in the opposite direction and check whether this enemy, along with our best enemy, can catch the chef in T seconds. If neither of these cases allow us to catch the chef in T seconds, then doing so is impossible.

    Finally, to get our answer, we simply take the minimum of the answers given by our two original cases.

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

I'm very curious to hear about the thoughts of Div 1 coders who left Secret Recipe for last. As a Div 2 participant, I didn't find it ridiculously hard, but it was the least solved problem in both divisions. The questions SUBSETS and IDXSUM seem much harder conceptually from a quick glance at their editorials.

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

How to solve slush question without Bi < Fi constraint (Bi and Fi can be any value between 0 and 1e5)?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    This wouldn't change the solution in any way, as the problem stipulates that Chef must sell a customer their favorite flavor if that flavor is in stock. So, whether we add Bi or Fi doesn't depend on their values--only on which flavors are available.

    EDIT: This is incorrect, see the below comment. I suspect that this problem actually becomes rather difficult with this constraint eliminated, and maybe even impossible with the given input size and time limit. I'll think about it some more and will post an update if I come up with a solution.

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

      Actually, solution will change because you can finish stock of some other drink which will be demanded later earlier. With the constraint Bi<Fi it was always unoptimal. But now it can also be optimal.

      → Reply