curly_braces's blog

Criterion 2020 Round 7 announcement
By curly_braces, history, 4 years ago, In English

Hello Codeforces!

Tomorrow, on September 11, 2020 at 15:00 BDT we will be hosting Criterion 2020 Round 7 on Toph. Toph is a Bangladeshi contest programming platform.

The contest will have 5 or 6 problems and will run for 2 hours 30 minutes. This contest is rated for all participants. You can register for the contest here..

The problems were authored and reviewed by De.Wilde, fire_tornado, Hasinur_, Atondro_Wahid, pranonraian, gola and me.

Thanks to TarifEzaz for his unconditional support and hjr265 for the best contest programming platform in Bangladesh.

We're inviting you all to participate in this contest. Hope you will enjoy the problem set.

Good luck!

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

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

I Love my country & toph also <3 See you all in the leaderboard !

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

Nice problemset. D was very tricky :p I solved it with intuition. Do you guys have rigorous proof of the solution?

Also, how to solve E?

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

    Problem E:

    Consider query for x. from the value of x we can derive at which cycle of operations it occured and for which element of P it occured. Let’s say we get x’th element in S from Py in it’s Z’th cycle.

    Let’s call the segment from P[i] to P[i+1] a block. Now if we look at different values of in S which came for Py, you’ll notice that inside a block, the values increase uniformly. if you are between P[i] and P[i+1], the values will increase by i+1 in the next cycle.

    Now we need to find which segment our result will be occuring in. This can be done using a dp and doing a binary search or you can use two pointers(you may need offline query there).

    Now you have to find how many cycles passed before reaching that block(dp) and what’s the last position where you end up after those many cycles. another dp(or can be done iteratively if you are using offline query).

    Be careful about the last position before this block calculation.

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

    Problem D:

    Case 1: sum of the rest < Biggest

    We are putting all the objects in two points in a single line that goes through the centre, heaviest one at a point and the others at the opposite. if you don't put them in the same place the vectors will only divert the centre of gravity outside of the line and the concentration of those vectors at the opposite point will be lesser. so the centre of gravity will travel more towards the heavy object which will only worsen our result.

    Case 2: sum of the rest >= Biggest

    We are calculating the concentration of mass at the opposite point of the heavy object. As the sum is more, so we need to reduce some mass. By changing the angle of an object we can do that easily thus reaching equal concentration of the heaviest object. So the centre of gravity will be at the centre.

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

Problem B:

Verdict : Runtime Error. Code : ideone.com/gragGj

What's wrong with this solution? Please Help...

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it 
    bool mtrx[n][n];

    This line was giving RTE. This is a 10^5*10^5 array. Which is far over than memory limit. You can use a map instead of an array.

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

How to solve C ?

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

    Problem C:

    Let's first solve the problem considering the array as a string with lowercase latin letters. Then the greatest value at any position will be at most 25. At every position we can keep a mask of 25 bits, where the bit corresponding to the value of that position will be on and all other bits will be off. For example, if there is a value 5 in the ith position, then the mask for the ith position will have the 5th bit as on and all other bits as off. Now the problem is converted to "How many subarrays [L,R] are there where the XOR of all masks of positions in range [L,R] is 0". This can be done by keeping the prefix XOR and for any position, we need to find the prefix XOR of the current prefix and add to the answer the number of times this XOR value occurred earlier.

    The original problem can be solved in the same way, but we cannot keep a mask of 2 * 10^6 bits. Instead, we'll keep the hash of a mask of 2 * 10^6 bits (can be the hash of a string of length 2 * 10^6 with 0s and 1s in every position). While calculating the prefix XOR hash, we just need to flip the position in the current hash corresponding to the current value and add to the answer the number of times this hash occurred earlier.

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

      gola Thanks for your comment. I got the first part of your solution idea. I have no clue about implementing for the original constraints. Can you please refer some article on this concept or if possible share some implementation idea ? (I have some knowledge about rolling hash only)

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

        This is a very good video on rolling hashes. From here you can see how to calculate the hash of a frequency table and update frequencies in O(1). The same concept and implementation can be used to maintain a binary hash with updates such as setting and resetting a bit position (same as increasing or decreasing the frequency of the value corresponding to that bit position).

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

I had one question regarding rating changes.The guy who stood first had initial rating 1800 and his rating became 1885 and the guy who stood 22th had initial rating 1500(Unrated) .But his rating became 1901(401 rating increase!!!). How is that possible or it is just a bonus rating for a newcomer???

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

    Toph's rating system

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

      I didn't understand the rating mechanism so that I asked here?It seems to me unbelievable such rating changes.

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

    The Glicko-2 rating system takes the unreliability of the current rating into consideration. So if you think about it, a newcomer's default 1500 rating really doesn't mean anything and is really not a reliable representation of his/her performance. The rating system, as a result, yields greater change for these cases.

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

How to solve F?

→ Reply