rivalq's blog

Invitation to CodeChef Starters 93 (Rated for All) — 7th June
By rivalq, history, 17 months ago, In English

We invite you to participate in CodeChef’s Starters 93, this Wednesday, 7th June, rated for all coders.

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

Note that the duration is 2 hours. Read about the recent CodeChef changes here.

Joining us on the problem setting panel are:

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 for all users for 1 day as soon as the contest ends, after which they will be available only to Pro users.

We’re hiring! If you’d like to intern at CodeChef as a Learning Content Creator, click here.

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.

Are you ready to dance to the rhythm of Ariana Grande's songs while coding? We sure are! Join us for an unparalleled contest experience. And before you go, drop your favorite Ariana Grande song in the comments. Let's see which tune gets the most love!

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

Comments Comments (43)
| Write comment?
»
17 months ago, # |
  Vote: I like it +3 Vote: I do not like it

orz

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

rivalq saar ORZ

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

Ariana Grande? I listen to Blinding lights (by TheWeeknd) more while coding.

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

can you stay up all night? (giggity)

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

My favourite song is "Break up with your girlfriend" as this song motivated me to breakup with my anime waifu and touch grass

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

Reminder: Contest starts in 3 hours.

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

"Positions"

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

"7 Rings" is the best song by Ariana Grande. Try proving me wrong!

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

In problem "GREEDY" can be replace the same character with different brackets if they are separated? i.e. can "bab" be replaced by "())" ?

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

How to solve NASA

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

    number of palindromic numbers below 2e15 are 427

    so precalculate all those number and iterate in array and see how we can form those numbers

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

      but checking xor for all i and j pairs in 10^5 length array would be fine ? I precomputed palindrome numbers , stuck on xor part

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

Why is Kosaraju TLE'ing on SORTP9

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

    Were you storing all the edges?

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

      (⁠ノ⁠ಥ⁠,⁠_⁠｣⁠ಥ⁠)⁠ノ⁠彡⁠┻⁠━⁠┻

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

      I don't think checking for SCCs is required at all. A simple DFS should be fine.

      Let $$$v_x$$$ be the node representing the value $$$x$$$, and $$$i$$$ be the node for index $$$i$$$ ($$$1 \leq i \leq N$$$).

      Observe that if an edge $$$v_a \rightarrow v_b$$$ exists, then $$$b$$$ is a submask of $$$a$$$, which means $$$\neg a$$$ is a submask of $$$\neg b$$$. So the edge $$$v_{\neg b} \rightarrow v_{\neg a}$$$ also exists.

      For simplicity, consider the path from node $$$i$$$ to $$$j$$$ that passes only through some value nodes:

      $$$ i \rightarrow v_{\neg A_i} \rightarrow v_{x_1} \rightarrow v_{x_2} \rightarrow \cdots \rightarrow v_{x_k} \rightarrow v_{A_j} \rightarrow j $$$

      It's easy to see that a path from $$$j$$$ to $$$i$$$ is guaranteed to exist:

      $$$ j \rightarrow v_{\neg A_j} \rightarrow v_{\neg x_k} \rightarrow \cdots \rightarrow v_{\neg x_2} \rightarrow v_{\neg x_1} \rightarrow v_{A_i} \rightarrow i $$$

      Or instead: proof by AC :)

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

In Thank U, Next, why is distance the number of nodes and not the number of edges in the path?

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

What is the logic for Thank U, Next

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

    something like a multisource Dijkstra, idk what else to call it

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

      Then how will know that which mail carrier node is closest to the specific node ??

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

        using a distance array and updating it with maximum possible available nodes

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

        multi source bfs read this topic .u will be able to do it very easily .can be extended by multi source dijktra to solve the problem very standardly

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

    BFS. Put every node x[i] in a p_queue acc to their d[i] and do bfs if d[i] become 1 for any node remove it from queue. Once your queue become empty check every node is visited or not

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

    You take the initial k vertices put them into a heap kind of thing, sorted by their ranges, extract the vertex with the largest range, delete it from the heap, update the max range of every other vertex reachable from the extracted vertex, (val-1, if val is the range of the extracted vertex), also add into the heap new vertices which have not yet been deleted from the heap with their respective ranges, do it until the heap is not empty. Now, if every vertex has at least once been extracted, HURRAY!

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

NASA can be just solved by this lmao:

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

    sorry i am noob but why did you stop at 32823 but not continued from 32923 let suppose

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

      see the constraints of elements of the array, they are till 2^15

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

      32923 crossed our given range (2^15). xor operation can not produce more value than input.

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

        xor operation can not produce more value than input

        This is not quite correct. For example $$$1 \oplus 2 = 3$$$, which is larger than $$$1$$$ or $$$2$$$. The xor operation cannot make higher bits $$$1$$$ than the highest bits of the input values. Mathematically stated:

        If $$$0 \le a,b < 2^n$$$ for some $$$n\in \mathbb{N}$$$, then $$$0 \le a \oplus b < 2^n$$$.

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

          sorry for that.. i actually mean the same.. as input < 2^15 then sum of 2^0 t0 2^14 is 2^15-1 as u said. Thanks for find my mistakes

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

How to solve Greedy ?

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

    Using DP.

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

    Notice that the string can be split into maximal segments of consecutive characters. In each such segment, all characters must be equal to each other, but characters for all segments can be chosen independently of each other.

    Now, consider some bracket sequence. Convert this into a sequence of integers: ( gets replaced by $$$1$$$, ) gets replaced by $$$-1$$$. Now, the bracket sequence is an RBS iff

    • all prefix sums are non-negative, and
    • the sum of all elements is zero.

    Since all characters within a segment need to be equal, a segment of length $$$len$$$ will change the prefix sum by $$$+len$$$ or $$$-len$$$. $$$-len$$$ is not possible, if this would make the prefix sum negative.

    Now, we create an array containing the lengths of all segmets of equal characters (in order). Now, we calculate all possible prefix sum values at the end of each segment using knapsack dp in $$$O(n\cdot \text{number of segments}) = O(n^2)$$$. If we can get a prefix sum equal to $$$0$$$ at the end, a solution exists. We can find this by doing backtracking on the dp array.

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

Why was this contest rated for 7-star coders, above other Starters? I felt the problems were quite easy for a "div 1" contest.

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

    It is true that this contest was easier than some previous "Rated for All" Starters. But as mentioned here, we do expect it to be sometimes less challenging for the highest rated participants now. The range of "Rated for All" contests has increased, and so there will be some contests where IGMs solve all problems without too much sweat.

    We just feel that there are enough users in the 7-star range as well, who find these challenging enough to have it be rated for all. For eg. in yesterday's contest, there were 25 7-star coders, and 8 of them solved all 7 problems. But 10 couldn't solve 1 problem and 7 couldn't AC 2 problems. Given that we definitely cannot have contests every month where the number of AKs is 1 or 2, we feel that having occasional easier Rated for All contests is a better compromise than having much fewer Rated for All contests.

    Maybe from the next time, we'll also add something along the lines of "We expect it to challenge IGMs" or "We expect IGMs to AK the problem set" in the intro blog. Would that help?

    → Reply