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

Автор mohit_jx64, история, 15 месяцев назад, По-английски

Hello, Codeforces ( ^_^)/

Warm and friendly greetings from FooBar (Competitive Programming Club), IIIT-Delhi.

We have a variety of coding events hosted under our annual technical Fest — Esya'23 and are glad to extend an invitation for your participation.

The details for the events are as follows:

  • ProTrio [Registration Link]:
    • ICPC-style coding contest
    • Eligibility: College Students | Team Size: 1-3 members (same college)
    • Stages: preliminary (online) and final round (on-site)
    • Prizes: worth ₹40,000
  • ProCon Junior [Registration Link]:
    • IOI-style coding contest
    • Eligibility: High School Students | Team Size: Individual
    • Stages: preliminary (online) and final round (on-site)
    • Prizes: Multiple Bonus Points for IIIT-D admissions (each point ≡ 1 percentile jump in the JEE Main Score)
  • ProSort Euler [Registration Link]:
    • Math-based coding contest
    • Eligibility: Open to all | Team Size: 1-2 members
    • Stages: one final round (online)
    • Prizes: worth ₹25,000

Important Dates:

Registration deadlines:

Contest timings:

Note:

  • Further details can be found here.

  • Contest links will be shared with your registered email IDs.

Problems in these events are collectively authored and tested by kunalsrv20, Artemistic, shiv_codegen, deepcpp, BlackPanther112358, haajihaa2508, ojus_single and me.

Good luck, and hope you enjoy the contests! (。◕‿◕。)

Updates:

  • Preliminary rounds for ProTrio and ProCon Jr. will be held on Codedrills. Contest links will be shared on the registered email addresses. Late registration requests will be difficult to deal with so please make sure you've registered on Unstop before the due date.
  • ProTrio-Prelims-Contest-Link & ProCon-Jr-Contest-Link both contests are public.
  • ProTrio-Prelims-Editorial
  • ProTrio Prize Distribution for the Preliminary round:

Rank Team Name University Prize Distribution
1 skillIssu IIT Delhi Rs. 2500/-
2 728752-UC6313NG IIIT Hyderabad Rs. 1500/-
3 fightFight IIIT Hyderabad Rs. 1500/-
4 728752-UZP479L8 IIT Delhi Rs. 1000/-
5 728752-URN708B7 IIT BHU Rs. 1000/-
  • Top 51 teams have been invited on-site for the final round of ProTrio, where the top 5 teams will receive cash prizes, and the next 5 teams will receive goodies. (Invite emails have been sent)
  • Проголосовать: нравится
  • +69
  • Проголосовать: не нравится

»
15 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
15 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Saying as a setter and a tester, you will enjoy the contest └(・。・)┘

»
15 месяцев назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

As a setter and tester, I'm definitely sure that you'll AKA the contest. :))

»
15 месяцев назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

As a setter, the problemsets were fun to work on and I'm sure you will enjoy the events :) Good luck!

»
15 месяцев назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

As somebody who has both participated and organised Prosorts and other events at Foobar, I can say that you should definitely give it a try.

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

As a setter and tester, it is highly likely that you will enjoy the Bugaboos :)

»
15 месяцев назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится
»
15 месяцев назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

ProSort Euler doesn't allow students from different colleges?

»
15 месяцев назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Hey! Will the prelims be on codeforces? Also, can you provide us with the old archives?

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

can I join protrio solo? I don't have friends who know programming (even syntax ... forget about logic)

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

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

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

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

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

mohit_jx64 On the coderills page for the protrio contest it says Please make sure you login and verify your team before the contest .. So how to do this step ???

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

pardon me if its a dumb question.

i am participating first time in any online team coding contest

can you tell . if there are any rules about how the team should collaborate

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

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

»
15 месяцев назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

As a setter and tester, you will solve all problems in first try :)

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

How to find the sizes of connected components in xor 3?

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

can anyone tell the logic for Typewriter Game ..

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

    Google "Optimal Cache Replacement Policy"

    • »
      »
      »
      15 месяцев назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Yes, that was the main intuition of the greedy.

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

      but will the time limit not be O(n*k) in that case also

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

        Maintain your cache (aka keyboard in problem's words) as a set of pairs $$$(\text{next occurrence of value}, \text{value})$$$, you need to make $$$O(1)$$$ changes to this set every step. Submission Link

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

        The greedy idea is to keep filling up your 'cache' with characters until you hit size $$$k$$$. Now when you need to remove something from your cache you remove the character who's next occurrence is the furthest away from your current position.

        You can pre-process the next occurrence of every character in $$$O(n)$$$, and you can maintain the current state of the cache in a set, say pair {next_occurrence, a[i]}. Simulating the entire sequence is now $$$O(nlog(k))$$$.

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

How many team will be selected for the onsite round?

»
15 месяцев назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

We cheesed typewriter with an unintended solution. I wrote a greedy which always chooses to replace the least frequent character. My teammate wrote a greedy which always chooses the furthest character. Both of these individually give WA. But taking the min of the answers produced by both greeds passed

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

What were the intended solutions for A and second part of C? I have a feeling mine were different.

For A, I maintained a frequency table (stored as an std::map<int, int>) for each paranthesis depth. When opening a parenthesis of depth $$$d$$$ just add its color to the $$$d$$$-th frequency table.

When closing a parenthesis of depth $$$d$$$,

  • Answer for this parenthesis is the size of this frequency table.
  • Merge the $$$d$$$-th table into the $$$(d - 1)$$$-th, and clear the $$$d$$$-th table.

By using small-to-large merging you can do merges in $$$O(n \log^2 n)$$$.

For C, I just spammed FWHT thrice. Was the intended solution to use that there are at most $$$\sqrt n$$$ distinct values?

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

    A was intended to be solved using small-to-large merging, by constructing a tree from the parentheses. Although A could also be solved by mo's algorithm in $$$O(n \sqrt n)$$$.

    And yes for C the intended solution was to use $$$\sqrt n$$$ distinct values, so the final complexity would be $$$O(n \sqrt n)$$$. I'm not familiar with FWHT though...

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

      And here I was trying to use recursion, when will you upload editorial?

    • »
      »
      »
      15 месяцев назад, # ^ |
      Rev. 2   Проголосовать: нравится +36 Проголосовать: не нравится

      A can be done using segment tree also. Iterate over the indices of the string, maintain the first index after current index for every color. Then the problem reduces down to range sum, index update queries for a total of O(nlogn) time.

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

      I solved with MO's :)

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

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

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

will there be no prizes for the offlne onsite round of pro trio??

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

    I'm not sure what prizes you are talking about! But it's mentioned in the blog that top 5 teams in the finals will receive cash prize and next 5 will receive goodies. The prizes for preliminary round and final round are separate.

»
15 месяцев назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

But among top 50, only 11 team are from delhi.

aren't 11 teams too less. considering its IIIT delhi and there were 250+ teams registered.

( or I don't know maybe you guys have travel arrangement for outside delhi team, in that case my bad)

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

Can you check why our solution was giving runtime error on test case 4.

Submission link: https://codedrills.io/submissions/749386

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

    Hi Quick-One, thanks for pointing this out. We checked your submission and found there was a slight error with the test case due to which Python and Java codes can give runtime error on 4th testcase. We have rectified the same and re-judged all the submissions for the Problem : GCD Faceoff. Updated standings are also now visible here.

    There were 2 teams who faced this issue including you. I want to sincerely apologize for any inconvenience and frustration this may have caused you. To accommodate these changes in the standings, Top 51 teams will be now invited on-site for the final round of ProTrio, where the top 5 teams will receive cash prizes, and the next 5 teams will receive goodies.

    If you still have any concerns or questions, please do not hesitate to reach out to us. Thank you for your understanding, and we appreciate your support.

»
15 месяцев назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Editorial plzz Mohit bhaya

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

ProTrio Preliminary Contest Editorial

Problem A Colorful Parenthesis

Author: kunalsrv20

Intended Solution
Alternatives
Code (Intended)
Code (Using Mo's algorithm)

Problem B GCD FaceOff

Author: haajihaa2508

Solution
Code

Problem C XOR 3

Author: mohit_jx64

Solution
Code

Problem D A Grid is a Grid is a Grid

Author: ojus_single

Solution
Code

Problem E Typewriter Game

Author: shiv_codegen

Solution
Code