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!
I Love my country & toph also <3 See you all in the leaderboard !
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?
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.
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.
Problem B:
Verdict : Runtime Error. Code : ideone.com/gragGj
What's wrong with this solution? Please Help...
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.
How to solve C ?
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.
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)
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).
Hopefully I Got it. I find rolling hash doesn't roll in this problem as length is fixed. calculation is based on whether corresponding position of particular value is set or not. Thanks again.
May be your reference was https://www.youtube.com/watch?v=rA1ZevamGDc&ab_channel=AlgorithmsLive%21
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???
Toph's rating system
I didn't understand the rating mechanism so that I asked here?It seems to me unbelievable such rating changes.
You can share this at Toph community or in the blog of the contest for official response from toph.
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.
How to solve F?
Problem F : Editorial