AlphaGaurav's blog

By AlphaGaurav, 7 months ago, In English

Hello, Codeforces!

The Competitive Programming Club of IIIT Lucknow is happy to invite you to participate in Dream In Code '24 which will be held on Thursday, April 11, 2024 at 20:00 IST (UTC+5.5).

You will have 2 hours to solve 8 problems (one of the problems has 2 subtasks), the round will be held as a Codeforces gym contest and will therefore be unrated.

The problems have been prepared by members of the club, atharv_tiwari, AnikateKoul, akshitnandan, saavrm and Ankit_102.

The prizes for the winners are as follows:
1st place: 5,000 INR
2nd place: 3,000 INR
3rd place: 2,000 INR

(Prizes for international winners will be transferred via crypto)

Thanks to MikeMirzayanov for the great platforms Codeforces and Polygon which allowed us to setup the contest easily.

You can access the contest using this link.

Good luck and have fun!

The Dream in Code series is part of Equinox, the Annual Techno-Cultural fest of IIIT Lucknow. The contest is open for everyone and we would love to see your participation in the contest.

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

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

As a setter, the problems are really interesting and I recommend everyone to participate.

»
7 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Excited>>>

»
7 months ago, # |
  Vote: I like it +2 Vote: I do not like it

No Prizes?

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

    We were awaiting confirmation from a couple places, hence the delay. The prizes will soon be updated in the blog now

»
7 months ago, # |
  Vote: I like it +4 Vote: I do not like it

The registration is now live!!

»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

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

Late announcement

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Super excited for the contest !

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Will there be editorial or PCD?

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

    Hey! If you have any doubts about the questions, you can message me or any of the writers. We will assist you directly. If you feel a more general discussion would be better, you can comment your idea or doubt under this blog :)

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice contest,i implemented Matrix Exponentiation for the first time today.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain E and F.

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    For E, you can maintain two sorted multisets $$$m_1$$$ and $$$m_2$$$: $$$m_1$$$ holds all the current elements of $$$a$$$, and $$$m_2$$$ stores the differences between consecutive elements of $$$m_1$$$. Now to make an update:

    • Find the elements before and after $$$a[i]$$$ in the $$$m_1$$$, let them be $$$l$$$ and $$$r$$$
    • Erase $$$a[i] - l$$$ and $$$r - a[i]$$$ from $$$m_2$$$, insert $$$r - l$$$
    • Erase $$$a[i]$$$ from $$$m_1$$$ and insert $$$val$$$ into $$$m_1$$$.
    • Now similarly to the first part find the neighboring elements of $$$val$$$ and update $$$m_2$$$ accordingly
    • Return the smallest element in $$$m_2$$$

    For F, you can maintain a 2D DP array where $$$dp_{i, x}$$$ stores the maximum coop value among the first $$$i$$$ groups only at most $$$x$$$ people can be used from group $$$i$$$. To calculate this, let $$$c_{i, x}$$$ be the maximum coop value we can get in the first $$$i$$$ groups if exactly $$$\min(a_{i-1}, x)$$$ people are used from group $$$i$$$. This can be calculated simply: $$$c_{i, x} = \min(P_i, P_{i-1})\times\min(a_{i-1}, x) + dp_{i-1, P_{i-1} - \min(x, P_{i-1})}$$$. Once $$$c$$$ is calculated, $$$dp_{i, x} = \max_{0\leq j\leq x}(c_{i, j})$$$, which can be done efficiently by taking prefix maximums. The answer will just be $$$dp_{n, a_n}$$$.

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    For F:
    The intuition is that you will decide for a group $$$i$$$ that some $$$j$$$ people that will cooperate with some $$$j$$$ people from group $$$i - 1$$$. This will leave maximum $$$count[i - 1] - j$$$ people to cooperate with the $$$i - 2$$$ group if it exists. This should give you an idea of using a 2D array to store at what group you are going to work at are and how many people from that group to choose.

    This code does the same. [submission:256149281].

    Since the constraint mentions that the total number of people and groups $$$\le 10^5$$$. Therefore looping over all the people in group is possible as the total iterations are $$$n + \sum_i^n count_i$$$. Also we are only considering $$$i$$$ and $$$i - 1$$$ at any iteration. Therefore, we only use $$$dp$$$ with first dimension 2.

    At the end of each iteration of the outer loop($$$i$$$) we copy all elements changed(updation of $$$dp[1]$$$) in the inner loop($$$j$$$) to $$$dp[0]$$$.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For A How would we solve it for A[i] ^ A[j] == 1 and we need to find the largest A[i] * A[j]?

Just a alternate problem which I thought of while solving the problem.

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

    just check consecutive numbers where the first number is even

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

      Can you elaborate.

      A[i] ^ A[j] won't result in 1 for all even odd pairs right.

      Since 15 ^ 16 = 31.

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

        the smaller number should be even, it is always true in that case

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

    Its saying that A[i] ^ A[j] 's first bit should be 1, i.e. any of the odd-even pair will suffice this condition. Reread the question again, its taking & with 1.

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

      I was thinking of a alternate similar problem.

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

        Oh, then A[i]^A[j] can be 1 iff they both have all the same bits except the bit at 0th position, so they must be a n and n^1 pair. You can hash the whole array and search for n^1 for every other number, if it exists.

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

    you can maintain set and iterate form 1 to n , for each index find the (1^a[i]) in set if it exist update the answer

»
7 months ago, # |
  Vote: I like it +17 Vote: I do not like it

What's the intended solution for problem G?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me why this code gives RTE Problem D : [submission:256406705]