K_queries's blog

Invitation to CodeChef Starters 125 (Rated till 6-Stars) — 13th March
By K_queries, history, 3 months ago, In English

We invite you to participate in CodeChef’s Starters125, aka International Coding Marathon, in collaboration with Technex'24, IIT (BHU), this Wednesday, 13th March, rated for till 6-Stars(ie. for users with rating < 2500).

Time: 8:00 PM — 10:00 PM IST

Joining us on the problem setting panel are:

Special Thanks to Vaibhav kingmessi Khater, Nachiketa Atekichan Sharma and Anshiv sv1shan Singla for their valuable feedback.

ICM is the flagship CP event of Byte the Bits, the set of programming events organized under Technex, the annual techno-management fest of the Indian Institute of Technology (BHU), Varanasi.

ICM

Prizes

Note: Prizes are only for Indian College participants (for division 1 only).

  • Winner: $$$20,000$$$ INR

  • $$$1^{st}$$$ runner up: $$$15,000$$$ INR

  • $$$2^{nd}$$$ runner up: $$$10,000$$$ INR

  • Rank $$$4^{th}$$$ to $$$8^{th}$$$: $$$1,000$$$ INR

Please fill out this form to avail them.

Some of out previous rounds:

Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest. The video editorials of the problems will be available only to Pro users.

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
  • +97
  • Vote: I do not like it

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

As a valuable feedbacker, I assure that I was forced to comment on this blog.

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

Mr_Misogynist orz

I salute your noble spirit.

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

Will division 2 participants(Indian College students) not be eligible for the prizes ?

→ Reply
»
3 months ago, # |
← Rev. 2   Vote: I like it -9 Vote: I do not like it

Will Indian high school students(division 1) be eligible for the prizes?

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

As a Setter,I assure you that I don't know any problem.

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

Reminder

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

is div2 rank 1 is not counted in price?

→ Reply
»
3 months ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

The tests for the problem ATBO seems weak. For example,
1
6
1 2 3 4 5 6
15 -5 -4 -3 -2 20
should give YES as output, but most of the submissions giving NO are accepted as well.
My accepted submission which gives YES as output.
The logic behind my submission is that given numbers a, b, c, d, e, f we can change the sequence to abcde, -e, -d, -c, -b, bcdef after applying a few operations. The same pattern can be continued when the sequence is longer.
For example, this accepted submission gives NO for this testcase.
Please rejudge this problem @ satyam343

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

    Can you please explain your solution and how you came up with it ?

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

    if that is the case, then it is unfair for all since they skipped that problem by seeing accepted Better option is ig remove that problem contribution from ranking

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it -7 Vote: I do not like it

      I agree.

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

        It will be unfair,better option is ignore this.It was not intentional,just move on.

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

      Agree, although I solved this problem if it has this many weak test cases it's better to have a fair judgment by removing such a problem.

      One more counter case

      we can achieve a sequence $$${(a_1 + a_2 + a_3 + a_4, a_2, a_3, a_4, a_5)}$$$ from $$${(a_1, a_2, a_3, a_4, a_5)}$$$

      Proof of the above

      My ACed Submission will fail on this!

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

        No this is not counter case bro. Ans is aggressively no Sum1 != sum2

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

        after an operation the sum of array doesn't change so there is no way your countercase works.

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

        After the 3rd step the value of a1 will be a1, but not a1+a2+a3+a4

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

    Disclaimer 1: I solved it in the intended way.

    Disclaimer 2: the contest is not rated for me.

    There's an established policy on codechef that a rejudge (i) only happens if the test cases were wrong, not weak, and (ii) cannot change AC to non-AC.

    It makes a lot more sense than any other resolution proposed here. It is unfortunate, but the best course of action in this case is to do nothing and hopefully learn from this mistake so that it doesn't happen again.

    Fortunately, codechef rating system is very forgiving, so one such contest will not influence your rating significantly. Those who got AC with a wrong solution will likely lose some rating in the next contest, and those who spent extra time getting the correct solution will gain some rating in the next contest.

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

Video Editorial for div2. B(Minimal Binary)

YOUTUBE EDITORIAL LINK : --Click Here

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

Here's a very simple way to naturally arrive at the solution to "Bucket Game" from today's Starter, the reasoning of which you can also reuse in future Game theory problems.

There exists a concept of mirroring which is useful in these problems. Moves can be mirrored if the number of entities in the game is even (whether or not mirroring is useful depends on the particular problem, but you should think about mirroring at least once, and then discard it if it's not relevant).

If you have a single pile, then you can keep mirroring your opponent's move to win that pile. Winning is only possible if the number of elements in the pile are even. Even if you have infinite piles with even number of stones, you can just mirror the moves on the pile that the opponent chose. Hence, the first player on a set of even piles will lose each pile. Therefore, it is never optimal for the first player to pick an even pile, unless no option's remaining. Hence, let's keep all the even piles in one area. And all the odd piles in another area. It's obvious that no one will touch the even pile until the very end.

The first player will of course make a move on the odd pile, which would then become even, and it would be shifted to the even section. After which, no one will use them till the very end. The second player will also do the same, i.e, pick an odd pile.

So, each player will keep alternating between odd, odd, odd, odd, etc. Notice that there's no strategy involved for the remaining even piles, i.e, the player who gets those remaining even piles is already decided based on the alternate sequence above. So if you can't control who gets to walk away with the big chunk of even pile, what is the next best thing that you could do? Of course, you should greedily maximize your score, by taking a pile with 1 immediately (the opponent would do the same).

Hence, you can just simulate the entire process. Sort the array so that the pile with 1 stones are at the front. Then, in each move, each person will greedily take the available 1, once the 1s are consumed, the game is fixed, i.e, everyone has to blindly select one odd pile untill none remain, and one person takes the chunk of even piles accumulated.

Code

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

    that's clever. I didn't about this fact and hence missed the problem.

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

Please look into re-evaluation of the question "Operating on A" with strong test cases @satyam343 The problem is accepting wrong logic solutions due to weak test cases. It is unfair for a ratest contest to ignore such misjudgements. A possible test case is: 1 6 2 1 -3 4 2 3 6 -3 -1 2 -4 9

Correct answer is YES as we can apply operation on i=4 and then on i=2, but many solutions with output NO are getting accepted.

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

My soln discussion stream

→ Reply