Utkarsh.25dec's blog

Invitation to CodeChef Starters 9 (Rated for Div-3) — August 17, Tuesday
By Utkarsh.25dec, history, 3 years ago, In English

We invite you to participate in CodeChef’s Starters 9 this Tuesday, 17th August.

Time: 8 PM — 11 PM IST.

Joining me on the problem setting panel are:

The video editorials of the problems will be available on our YouTube channel as soon as the contest ends. Subscribe to get notifications about our new editorials.

Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.

Hope to see you participating.

Good Luck!

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

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

Auto comment: topic has been updated by Utkarsh.25dec (previous revision, new revision, compare).

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

Btw, what is the reason of increase in frequency of division 3 contest, are you guys suffering from lack of DIV1 problems?

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

Why is everything only rated for Div3? Once you cross 3 stars you have to wait a year to participate in a rated contest.

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

    Probably because of lack of hard problems.

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

    Significant lack of Medium and Medium-Hard problems. As far as I know Div2s need at least 1-2 Mediums and Div1s need a 2-3 Mediums + 1-2 Medium-Hards so I guess nearly all of the ones that are good enough for rated contests get kept for Cookoff and Lunchtime.

    At least in my opinion its much easier to come up with good Easy or Easy-Medium level problems than tougher ones for 1700-2200 rated setters (which is the range 80-90% of Codechef setters fall in from my experience).

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

      2200 seems pretty high, I mean, we had a DIV2 round set by experts in the past and the last problem fared hard enough for the top competitors. I don't have any experience problem-setting, but I have heard one can create problems way harder than what they solve by starting backwards in the past, and a medium to medium-hard is like, idk, 1900-2300 in cf rating roughly?

      I think with the rating level of the setters they seem to have, division 2 rounds don't seem very far fetched but it is probably much more than rating when it comes to problem-setting, I suppose.

      With what I said above, I think CodeChef could atleast make more div2 rated rounds, like codeforces.

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

        I said its usually easier for setters in this range to set Easy or Easy-Medium, not that its impossible to set tougher problems.

        Yes, you're correct that working backwards from the solution is easier, and this does work for some setters. However I personally find it creates more boring problems.

        I usually like working from some random ideas / operations (formalizations of actual events are even better) to the solution. This is mostly limited by whatever looks at least somewhat solvable to me. The only Medium-Hard I set was originally an Easy-Medium which I later realized had another tougher observation that improved the complexity and made it a Medium-Hard level problem.

        Also my personal approximate conversions I use for Codechef difficulty to CF difficulty:

        Cakewalk: 800 — 1000

        Simple: 1100 — 1400

        Easy: 1500 — 1700

        Easy-Medium: 1800 — 2000

        Medium: 2100 — 2300

        Medium-Hard: 2400+

        Just my rough rules, the ranges can wary quite a bit. And similar to CF, a Medium in a Div3 only round may be easier than a Medium in a rated for all round.

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

        We are currently trying to improve the frequency of div-2 rounds.

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

how to solve CORONA?

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

    Create a fake node (say 0) and connect it to all the cities having hospitals with an edge weight of the cost of setting up a hospital. Also connect the original edges as given in the input. Now do a simple Dijkstra from the fake node. The resulting distance array you get is the required answer.

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

      You can also avoid the fake node altogether and just add the cities with their initial costs to the backing heap / pq of the dijkstra initially. If there is a better answer, these values will be ignored.

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

    End the pandemic

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

Nice problems, I enjoyed them.

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

    Hey, Did you manage to solve Fibonacci Sequence problem ? If yes, Then can you correct me where I went wrong.

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

      you have only two digits, also your logic is completely wrong

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

        EDIT: You are right, we shouldn't consider the frequency of 0s

        His logic is correct, you calculate the frequency of 1s and then multiply by 2^(sz — 1)

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

          ah, I saw 2^(sz-1) as 2^(sz)-1:)), then yes it's correct, but why does it work? Anyway I solved it with dp

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

      First of all we only care about the frequency of 1s (there are only 0s and 1s).

      Your approach is correct, but there will be an overflow in [size], using Fermat's little theorem calculating 2^((size — 1) % (MOD — 1)) is the same as calculating (2^(size — 1)) % MOD

      you can watch the editorial video for more information

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

Haven't given the previous Codechef Starters, but looks like a nice contest for beginners.

Some of my general thoughts on the problems:

  • Black Cells in a Chessboard — I really like this problem, its a straightforward cakewalk but its extremely natural and isn't just "do this".

  • Large Square — decent cakewalk, nothing much to say.

  • Bus full of passengers — Not too much of a fan, feels like "implement exactly what's asked in the question". I get that implementation is not exactly trivial for someone who's just starting with competitive programming, but still doesn't feel like a good problem.

  • Friend Groups In A Line — Nice idea. But I feel 0 friends = 0 friends groups is an unnatural edge case that should really have been in the samples, but that might just be my saltiness at having wasted 10 mins on this edge case talking.

  • Fibonacci concatenation — Cool maths, nice educational value to someone who isn't familiar with how to handle mod expo when the exponent can be massive as well. On that note, is there a way to solve this without utilizing a^(p — 1) = 1 to get a reasonable exponent?

  • India Flights Corona — Standard multi-source shortest paths problem, but still probably good enough looking at the Div3 and Div2 solve counts and since the contest is meant to be educational.

Also I feel there a massive jump in difficulty from P3 (Bus full of passengers) to P4 (Friend Groups In A Line). P3 is fairly direct and I think even newer participants should be able to solve it after some time, while the greedy for P4 has fairly tricky conditions that even slightly experienced participants might incorrectly construct.

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

    In Fibonacci concatenation there is one way in which we do not need to care that the exponent becomes really large. Since we only need to have terms like $$$2^{len[i]}$$$, let dp[i]= $$$2^{len[i]}$$$ Then the recurrence relation will be just dp[i]=(dp[i-1]*dp[i-2]).

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

    In P4, I used DP to solve. dp[i][j] (0<=i<N and 0<=j<3), where i denotes the index and j denotes the position of ith index (0 denotes i-1, 1 denotes i, 2 denotes i+1). Now recurrence relation was simple as well. For each 'i', I run for all the 9 possibilities of the previous index and current index, add 1 if the previous is not in range else it will be equal to the previous index value. Here N is the size of the vector which stores the indices of '1' in the given string.
    My code : https://ideone.com/wLzqs9

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

I respect initiative taken by codechef to encourage beginners as competitive programmers and I have found level of starters pretty good in such respects, but the point is what about of div2 and div1 participants? We just have two contests per month and that too sometimes get delayed. I request codechef admins to have some contests for div2 and div1 also.

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

:orz:, really orz problems. All hail Utkarsh.25dec

→ Reply