Codeforces Round 901 (Div. 1, Div. 2) Editorial

By Atomic-Jellyfish, 5 months ago,

• 5 months ago, # ^ | chill thanks for the round

• 5 months ago, # ^ | amazing round loved it

  • 5 months ago, # ^ | Wish you good luck in the future :)

• 5 months ago, # ^ | chill, in my opinion the round was great, ABCD and F were great problems (although D might be a bit too easy for a D?). It seemed that div1 was too hard but I guess that such things happen and can't be predicted. I'm looking forward to compete into one of your rounds again :)

  • 5 months ago, # ^ | The scoring for D justifies its difficulty. There was a huge difficulty gap between D and E though and that's the only issue. Nevertheless, amazing problems.

    • 5 months ago, # ^ | Next time I'll pay attention to the difficulty gap of adjacent problems :)

  • 5 months ago, # ^ | Thanks, welcome to the next Jellyfish Round :)

• 5 months ago, # ^ | it was a great contest the problems were very interesting I had so much fun so thank you <3

  • 5 months ago, # ^ | And thank you for supporting the round! :)

• 5 months ago, # ^ | It was my first contest, littrally I solved nothing. But it was a nice experience

  • 5 months ago, # ^ | Wish you get a higher score in the next round :)

• 5 months ago, # ^ | Sir, when will the problem ratings be displayed? Or are they supposed to be taken as the initial points (500, 1000, 1000, etc).

• 5 months ago, # ^ | maybe you are the king of dp :) (doge)

  • 5 months ago, # ^ | In fact, I personally think it's the number of dp problems is too much, but it seems like a lot of people thinks it's a math-y round X_X

• 5 months ago, # ^ | No need to apologize at all. I really enjoyed the round and think that no one should be blamed after their hard work. I admire your work.

• 5 months ago, # ^ | Don't feel guilty... Some people will never appreciate your hard work <3

• 5 months ago, # ^ | pls explain me why in Problem C my solution passed for only 60 iterations but otherwise it showed tle

• 5 months ago, # ^ | https://codeforces.com/contest/1875/submission/226075447 Change ur code a little bit(just removing maps cuz of shit const factor and adding vector as cnt). Always be careful with maps(never use it when it isn't necessary)

• 5 months ago, # ^ | Also it's not good to have #define int long long cuz sometimes u can get TLE cuz of that.

• 5 months ago, # ^ | Practice DP!!

• 3 months ago, # ^ | Can you explain your n^2log(n) solution of Div2 D. Jellyfish and Mex.

• 5 months ago, # ^ | Each person needs apples. We can divide each of the apples into pieces, then each piece is , Each person takes pieces. This is only possible since is a power of two, otherwise we would not be able to divide an apple into pieces.

  • 5 months ago, # ^ | Thanks

  • 5 months ago, # ^ | ← Rev. 3 →   0 thats almost right...consider n = 3 and m = 24 here m is not a power of two but its still possible....thats why actually m/gcd(m,n) should be a power of two ;)

    • 5 months ago, # ^ | Yes what I did was take gcd, divide it from m and n at the beginning, then multiply back at the end

      • 5 months ago, # ^ | In Div2C, Why the answer in the tutorial is m×|S|−n. Anyone help me pls, I was thinking from yesterday.

        • 5 months ago, # ^ | Everyone should have pieces( ), there are people and pieces (each one is a whole apple), and the number of apple pieces is added to exactly for each cut.

• 5 months ago, # ^ | In my opinion,if there are 7 apples for 4 persons,you should give 1 apple for each person,so there are 3 apples(3 pieces) now.And we know no one will get a whole apple(a whole piece),so we should devide every piece into two,now we have 6 pieces.After giving every person a piece,there are 2 pieces now.As what I just said,no one will get a whole piece,so we should devide every piece into two,now there are 4 pieces for 4 person,perfect!

int op=0;
while (n && op < 2000) {
    op++;
    cnt += n;
    n *= 2;
    n %= m;
}
if(n) 
    cout<<-1<<endl;
else
    cout << cnt << endl;

• 5 months ago, # ^ | ← Rev. 3 →   +4 suppose after some large no (let it be a) of iterations, let x be (n*2^a) then -> x%m (according to your code only) now, x%m to be zero m should be the divisor of x. now m can be in the form of something * 2^(something else). now this something cannot come from 2^a so it should come from n (see x=n*2^a) therefore m/(__gcd(n, m)) should not have any other prime factors other than two because 2 (in other words __gcd(n,m) should take all factors from m which are not 2) can be taken care by 2^a, but remaining factors have to be taken care by n itself. explanation might be bad english not my native language.

  • 5 months ago, # ^ | Thank you I got it.

  • 5 months ago, # ^ | Help me understand this in a better way, please.

    • 5 months ago, # ^ | ← Rev. 3 →   +2 If you can give everyone the same piece then (n * 2^k = 0) mod m, or n * 2^k = q * m. You can factor out gcd(n, m) to get a * 2^k = q * b, where a = n / gcd(n, m) and b = m / gcd(n, m). Now if b is a power of 2, then q = a and 2^k = b satisfies the equation. But if b is not a power of 2, then b has some additional factor(s) that is not found in a (because a is coprime to b) and 2^k (since b is not a power of 2). Also https://youtu.be/UvnVghpIjwk?si=rmsoD_dtVNUFOtLx&t=668

      • 5 months ago, # ^ | Thank you so much.

      • 5 months ago, # ^ | Can we say that if b is not a power of 2, then b must have some prime factors other than 2 that must be present in a for the equality to hold. But a and b are coprimes, so the only choice for b is to have prime factor of 2 only.

      • 5 months ago, # ^ | For 1875C — Jellyfish and Green Apple can you please explain: why __builtin_popcount(a) is equal to |S|?

        • 4 weeks ago, # ^ | Because m is 2 's interger power, (a/m) is equal to |S|,and so do(a);

• 5 months ago, # ^ | THANK YOU !!

• 5 months ago, # ^ | More simpler and optimised approach - If K is odd jellyfish can always take max of Gellyfish and give him his minimum, and then Gellyfish will try to get his maximum back in next move and then again jellyfish will take it back in another move and it continues this way until all K rounds. If K is even, jellyfish can choose not to move if his min is greater then Gellyfish max. But still in this case Gellyfish will try to take jellyfish max as it will benefit him, and again like the odd case the game continues but this time Gellyfish would have the last move. 226072584

• 5 months ago, # ^ | Usually the sum of over all test cases is such that an solution would remain (not ) even though you're answering test cases. However if is unbound, this doesn't stay true.

• 5 months ago, # ^ | i did not understand it clearly could you explain with this example?? 0 0 0 0 0 1 1 1 1 2 2 2 3 3 4

  • 5 months ago, # ^ | ← Rev. 2 →   +3 For this example, . Also , , , and . So 0, 1, 2, 3, and 4 (5 numbers) can be interesting values. And . We do DP only for these numbers. Let's see another example. 0 1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7. For this example only numbers 0, 2, 4, 6 (4 numbers) can be interesting. . And for any array count of possible interesting numbers won't exceed .

    • 5 months ago, # ^ | oh i got it! great solution bro loved it!!

• 5 months ago, # ^ | It is a really nice idea and it is sad that it's not possible to make this problem use it because convex hull trick will pass anyway.

• 5 months ago, # ^ | why is the contribution y* cnt(y) shouldn't it be mex * cnt(y)

• 5 months ago, # ^ | Actually complexity is or . Because you need too count numbers.

  • 5 months ago, # ^ | you don't need an extra log to count numbers, because we can ignore all values which are not less than n

    • 5 months ago, # ^ | Yep, but first you need to sort

      • 5 months ago, # ^ | again, you can use count sort, so it is still O(n) )

        • 5 months ago, # ^ | True, thx

• 5 months ago, # ^ | Reading array of n numbers already requires O(n). For a reason it can't be O(1).

  • 5 months ago, # ^ | Yes! Thanks for explanation.

• 5 months ago, # ^ | it's not O(1) you are summing the values.

• 5 months ago, # ^ | Can you elaborate?

• 5 months ago, # ^ | ← Rev. 4 →   +4 |S| is the number of pieces of apple each person is going to get , so m*|S| will be the total number of pieces they are going to get. Since each cut increase the number of pieces by 1 and initially there are n pieces when there are 0 cuts hence for x pieces we have to make x-n cuts and hence number of cuts will be m*|S| — n.

• 2 months ago, # ^ | ← Rev. 3 →   0 I was also stuck in how builtin_popcount_ ( or the number of set bits in a) is equal to the value of m. I got it like this: If each person gets a/b (simplest form of n/m) weight of apple: It is represented as 1/2^k + 1/2^l + .... and sum of all these individual parts for a person is equal to a/b. a will be the numerator . Also, we notice that on adding these we will get just some powers of 2 in numerator . and lets say 2^p + 2^q +.... =a So number of pieces for each person can be obtained as number of different powers of 2 that add up to form the numerator . ie (a), and this is just equal to the number of set bits in 'a'. Also, in one cut we get 1 extra pieces , so for m*|S| pieces , we need to make m*|s| -n cuts, as we already had n pieces when 0 cuts were made (as explained by the person above)

• 5 months ago, # ^ | ← Rev. 2 →   +24 It depends on what is ? is probability that both of them chose , possibility after destroying some roads. Let's say graph has 4 outgoing edges from 1, aka ,,,, Let , , , . During the first turn, Asuka will choose all nodes with equal probability, so for maximum probability to reach n, Jellyfish should choose , there . The second turn happens only if Asuka does not choose in the first turn. If still exists for the second turn, Jellyfish should choose it. , (Asuka chose 3/4 in the first turn and 2 in the second turn). If does not exist, then Jellyfish should choose , . (Asuka chose 2 in the first turn, and then 3 in the second turn) Jellyfish will not get a third turn; he will never choose , ,

  • 5 months ago, # ^ | Can you explain why f[i] = f[j]*p[j] ?

    • 5 months ago, # ^ | It's via linearity of expectation/probability. If one is at , the next possible outcome is one move to one of the nodes () with an edge and eventually moves to , or one remains stuck there. So, the probability of reaching from will be the probability of moving from to one of the adjacent nodes multiplied by their probability to reach , and (probability to reach after being struck on node ) multiplied by probability to remain stuck there. Sure enough, you can also add other non-adjacent nodes in this equation but the probability of reaching them from is .

      • 5 months ago, # ^ | Thanks, I see

  • 5 months ago, # ^ | By calculating, p=[0.25,0.25,0.125,0] , it also satisfies the condition. how can we be sure it satisfies the condition without checking all cases??

    • 5 months ago, # ^ | One cannot find all probabilities without checking all cases, just that you can memorise the subproblems via appropriate dp.

  • 5 months ago, # ^ | Thanks, I misunderstood the problem twice, but your explanation made it very clear why the 's would be different. But, the only issue is to calculate these 's in general, how did you extended this approach for any general outgoing edges?

    • 5 months ago, # ^ | ← Rev. 3 →   +21 Asuka chooses randomly with equal probability; by exchanging arguments, one can conclude that Jellyfish should always choose the one with the highest , still around. Sort all the possible nodes in the adjacency list in descending order; then, we want to find of each of them, with the condition that Jellyfish will always choose the first available one. We can define the following as the probability of selecting th person in a sequence of people. DP transitions

      • 5 months ago, # ^ | Probably the editorial was written on the same idea, but I was not able to understand it until you dropped a much simpler explanation. Thanks!

      • 5 months ago, # ^ | thanks dude, your explanation is really clear and understandable. and maybe a typo error that in the case " chose one of the left ", the probability should be (L-1)/(L+1+R) instead of (L-2)/(L+1+R)

        • 5 months ago, # ^ | Fixed. :)

  • 5 months ago, # ^ | How do you calculate p2? If Asuka chooses 3/4 in the first move, then this probability = 2/5 = 0.4, and from there, for Asuka to pick 2, it should be 1/3. So p2 should be (2/5)*(1/3) right?

    • 5 months ago, # ^ | There are only outgoing edges from , so possible choices are instead of . So, in the first move, Asuka has to select or , which has probability. In the second move, the remaining edges will be and ( or ); selecting will have probability . Overall

• 5 months ago, # ^ | ← Rev. 2 →   +3 Great observation! We could have had a harder version of the problem with

• 2 months ago, # ^ | You can even go down to a number as small as 100, since 2^100 is way greater than 10^9! Great solution, I didn't even think about brute forcing.

• 5 months ago, # ^ | Try this test case:

• 5 months ago, # ^ | The denominator on each slice needs to be a power of two. For example, you couldn't make of an apple with slices of , thus if and you can immediately say it's not possible.

• 5 months ago, # ^ | You have int overflow, use long long instead

  • 5 months ago, # ^ | Thanks, that does solve the problem. But one thing which I now started to have question is that why was I subtracting n from my answer.

    • 5 months ago, # ^ | You do sum+=min(arr[i]+1,a); which actually adds one more second than the tool is supposed to, the correct statement would be sum+=min(arr[i],a-1); You then subtract by at the end to correct the error.

• 5 months ago, # ^ | Think of it this way: [ a * ( cnt[b] - 1 ) + b ] + [ b * ( cnt [ c ] - 1 ) + c ] = a * cnt [ b ] + b * cnt[ c ] + c - a But since c must end up being 0, it becomes minus a, which is the original m

Your code here...
int n = in.nextInt();
            int m = in.nextInt();
            HashSet<Long> a = new HashSet<>();
            if(n % m == 0){
                pw.println(0);
            }else if((m & 1) == 1){
                pw.println(-1);
            }
            else{
                long l = n % m;
                long ans = 0;
                while(l != m){
                    if(a.contains(l)){
                        ans = -1;
                        break;
                    }
                    a.add(l);
                    ans += l;
                    l *= 2;
                    if(l > m){
                        l %= m;
                    }
                }
                pw.println(ans);
            }

• 5 months ago, # ^ | The sequence takes O(n) steps before it terminates. In your code, you check the whole sequence which goes up to 1e9, and the number of test cases is 2e4, so overall you do around 2e13 operations which gives you TLE.

  • 5 months ago, # ^ | ooohhh now i get it, thanks a lot

• 5 months ago, # ^ | Can you please explain ? What are the nodes of Bfs? and how is the time complexity calculated? Thanks in advance

• 5 months ago, # ^ | I used bfs each time and it finally passed because I found there were only a few situations (). After reading the solution, I think it's a good problem.

  • 5 months ago, # ^ | exactly 9216

• 5 months ago, # ^ | What is quadrangle inequality?

  • 5 months ago, # ^ | Why does a pupil need to know that? Stop learning useless algorithms. Mr. bilibilitdasc can learn it because he's already IGM.

    • 5 months ago, # ^ | ← Rev. 2 →   -22 Who are you to stop me?

    • 5 months ago, # ^ | fake it till you make it, or so they say

  • 5 months ago, # ^ | If a function satisfy , it is said satisfy the quadrangle inequality.

• 5 months ago, # ^ | 1874A is the same problem as 1875B

  • 5 months ago, # ^ | thanks

• 5 months ago, # ^ | ← Rev. 2 →   +3 Each cut increases the number of apples by 1. Since each person needs to get |S| apples in his account, final number of apples will be m*|S|. Since there were initially n apples, so we get the cuts by subtracting this from final apples, hence the answer m*|S| — n. Also, for the intuition why to multiply a group ans by gcd(n,m) (as you say) goes by the following example. Suppose n = 30, m = 48. Then a = n/gcd(n,m) = 5 and b = m/gcd(n,m).= 8. Ans for one group is = 8*2-5 = 11. Now the number of groups have become 6 i.e. gcd(n,m). Hence the answer will be 11*6 = 66, which is same as that given by taking all n and m (48*2 — 30) = 66.

  • 5 months ago, # ^ | Thankyou brother, got it:)

• 5 months ago, # ^ | Can I ask what's the game title?

  • 5 months ago, # ^ | Inscryption! You can find it on steam, I really enjoy it!

  • 5 months ago, # ^ | Inscryption, just the title.

• 5 months ago, # ^ | The funny thing is that without 1B the gap would've been smaller :)

  • 5 months ago, # ^ | This problem gets too little user feedback, and micho solved it in a fairly short period of time, so errorgorn and I misjudged its difficulty X_X

  • 5 months ago, # ^ | errorgorn solved it very quickly, and he thinks this problem is very easy. I can just orz errorgorn

• 5 months ago, # ^ | Oh i understand

  • 5 months ago, # ^ | can you explain...i am still not getting it

    • 5 months ago, # ^ | Because your are going to record the shortest path's source and destinations, and since there maybe some types of that will not exist in the , so except for all that is , there is another destination called "not exist", so the state is in total .

      • 5 months ago, # ^ | what do you exactly mean by "some types of (ai,bi,mi) that will not exist in the (a,b,m)" ? can you give any example...thanks a lot

        • 5 months ago, # ^ | For example, , in this case, pair exist and others like not exist, so you only need to consider the shortest path from to there specific , so except the state , in the pre-calculation there is another state which is "not exist"

          • 5 months ago, # ^ | okay..got it.....so it is just to save from unnecessary calculations, right. Thanks a lot

          • 5 months ago, # ^ | can you also attach your submission...tutorial solution is too complicated to understand

            • 5 months ago, # ^ | I haven't implemented this problem yet, maybe later.

            • 5 months ago, # ^ | I think the author used some math (base 5 number representation and bitmask) to encode the states. Let's see what does mean again? (thanks many helpful friend here helped me to understand it) First, let's clarify this: Given same state of two different bit and , no matter what we do, the resulting bits at position in must be the same. From then we can just care about different . For multiple bits that have same , we can use one to represent the whole group. Now, effectively all numbers can be seen as some special 8-bit numbers. The base, if is in range , then corresponds to 4 cases of some arbitrary we can make from some . If base equals , it means that there isn't any such that forms the configuration we're considering The exponent, from to , corresponds to the position, or more precisely the group I mentioned above. Take a look at this example: 00004002 is a base-5 number corresponding to a state: Last digit is . It means that the 0-th group, which is , has 3-th digit is , it means that the group contains no bit in it! For the remaining 6 groups, they just have the same So why do we have to represent data this way? In this representation, we see: Destination and Starting point are being tied together (with destinations as digits, and starting point as position (or call it order, exponent, ...)) Although we kind of "separated" individual bits to come up with the solution, yet in the solution they must be stored together !? Because each operation AND, OR, XOR affects each bit of the numbers. They're all transforming after each operation, so their values must be recorded and observed altogether.

              • 5 months ago, # ^ | really helpful explanation

              • 5 months ago, # ^ | Thanks for the explanation. It's really helpful.

• 5 months ago, # ^ | Suppose we start with , , . What are the possible reachable using the 4 operations given and the minimum number of operations to achieve that state? We use BFS for that purpose.

• 5 months ago, # ^ | Each state of the numbers is a node, each operation changing from one state to another is an edge. Therefore, a sequence of operations that transforms the init. configuration to the desired configuration, is a path between 2 nodes. And minimum number of operations is just equivalent to the shortest path. In this case, it's unweighted graph so BFS is sufficient

• 5 months ago, # ^ | When we use a tool at , the timer is incremented by , that is, (assuming it is less than ). So once the timer is decremented, becomes . If , then . Once the timer decrements, becomes . Hence the answer is min().

  • 5 months ago, # ^ | ok thanks !

• 5 months ago, # ^ | for each possible , and another corresponding to when there is no state for that .

• 5 months ago, # ^ | I think what is meant is that you store all in point value form , for points. Convenient is to use the points . All operations needed (summing, convolving two polynomials, shifting the polynomial with ) can be done in time linear in the size of the representation, so in . Afterwards, the only thing left is from the point value form of , going back to the coefficient form. This can be done with the lagrange interpolation formula in with some tricks (You need to first with brute force calculate the coefficients of the polynomial , and do polynomial division to obtain each of the summands of the lagrange interpolation polynomial.

  • 5 months ago, # ^ | Ah, now I understand! So let me rephrase it: For each , we want to evaluate . (I wrote to emphasize that we want to find a scalar, not a polynomial) To do so, let us fix : Then it is sufficient to find the sequence of , successively from the initial element to the final. The recurrence relation enables us to find for each in an time. Thus, can be found in an time. Therefore, can be found in a total of time. All that left is to do Lagrange interpolation, which I understand well. Thanks a lot for the explanation!

• • 5 months ago, # ^ | You forgot to output the newline character. use std::endl.

    • 5 months ago, # ^ | oh god，thanks

• 5 months ago, # ^ | We get the optimal solution if we use the tool when the timer is at 1. If we increase the timer past , it will be set to . We have two outcomes: timer change, increase of timer change, increase of

• 5 months ago, # ^ | I'll try to explain it as best as I can. When dividing the n apples among the m people, if n is greater than or equal to m, we can give each person n // m apples. After doing this, we can disregard how many apples each person has because they all have the same amount. We can now focus on the n % m remaining apples. Let's say a = n % m. If we have no remaining apples (a == 0), then we have finished. Otherwise, we have to make a cuts to now give us 2 * a apples. If (2 * a) % m == 0, then we have finished. Otherwise, we have to make 2 * a more cuts to give us 4 * a apples. We do this until (a * 2^k) % m == 0, where k is the minimum number that satisfies the equation. Now we have to figure out when there is no answer. In order for there to be an answer, (a * 2^k) % m == 0. This means that a * 2^k == q * m for some integer q. In order for this equation to be satisfied, all of m's non-2 factors must also be in a. If m had a non-2 factor that weren't in a, then it wouldn't be a divisor (it can have some factors of 2 that aren't in a because of the 2^k factor). This means that gcd(a, m) must have all of the non-2 factors that m has. This means that m / gcd(a, m) must be a power of 2. We can perform this check at the beginning of program and then proceed. Here is what I did: https://codeforces.com/contest/1875/submission/226131697

  • 5 months ago, # ^ | This was the best explanation for this problem, of which I came across. Thanks 123gjweq2

  • 5 months ago, # ^ | nice explaination:) thanks a lot

  • 3 months ago, # ^ | If m had a non-2 factor that weren't in a, then it wouldn't be a divisor (it can have some factors of 2 that aren't in a because of the 2^k factor). This means that gcd(a, m) must have all of the non-2 factors that m has. a * 2^k == q * m why q was not consider, can it have non-2 factors?

    • 3 months ago, # ^ | Let's ignore the 2^k for now. If a = q * m, it means that both q and m are factors of a. Therefore a must have any factors that q and m has. If a didn't have a factor that m has, for example, we could have something like 3^2 = q * (3 * 5), and there is no positive integer solution here for q. So, by this logic, we can see that all of m's factors must be present in a, so therefore gcd(a, m) = m, and m / gcd(a, m) = m / m = 1 (or in the original problem it must be 2^c for some c). So at the end of the day, q doesn't really matter at all.

  • 3 months ago, # ^ | ← Rev. 2 →   0 Thank you so much, you saved my life, oh, I'm really happy now that I found an explanation, I was so confused, I think you must be the maker of all editorials, I probably wouldn't understand without you why did we use m/gcd(m,n) at all, thanks very much :)

• 5 months ago, # ^ | "do nothing" and "won't swap" is the same thing.

• 5 months ago, # ^ | same doubt

• 5 months ago, # ^ | ← Rev. 2 →   0 I hope you understood the part where **m/gcd(n,m) is a power of 2 = 2^k** Consider n/m = (a*gcd(n, m))/m = a/(m/(gcd(n, m))) = a/(2^k) where 2^k>a Now divide "a" in the powers of 2. ( which are the set bits in the binary representation of a). Say the set bits are at position "i1, i2, i3, i4, and so on to ip" so a = 2^(i1)+2^(i2)+ ... + 2^(ip) n/m = (2^(i1)+2^(i2)+ ... + 2^(Ip))/(2^k) = 1/(2^(k-i1))+1/(2^(k-i2))+ ... + 1/(2^(k-ip)) All the k-i's belong to the set S. Hence, |S| = __builtin_popcount(a) = no. of set bits in a.

• 5 months ago, # ^ | Typo, thanks for the correction!

  • 5 months ago, # ^ | For 1875C — Jellyfish and Green Apple can you please explain: why __builtin_popcount(a) is equal to |S|?

    • 5 months ago, # ^ | For example, if a = 13, b = 32, each person will get 3 pieces of apple, a is 1101 in binary, 1101 = 1000 + 100 + 1（in binary), which is an apple piece with 8/32 kg, an apple piece with 4/32 kg, an apple piece with 1/32 kg.

      • 5 months ago, # ^ | ok i got this but why you have taken a = n / __gcd(n, m)??

        • 5 months ago, # ^ | We need to reduce it to its simplest fraction. for example, n = 5, m = 20, n/m = 5/20 = 1/4, the popcount of n is 2 but the popcount of a is 1.

          • 5 months ago, # ^ | sorry but can you explain detail why the answer in the tutorial is m×|S|−n. I understood the stuffs above but stuck with this.

• 5 months ago, # ^ | Hi! https://codeforces.com/blog/entry/120969 I have provided a bit more explanation here! Please upvote it you find it useful!

  • 5 months ago, # ^ | ← Rev. 2 →   0 Thanks that was way more clear. Atomic-Jellyfish please consider linking it in the editorial.

• 5 months ago, # ^ | "By greedy and induction" means, we can get the result of k rounds of the game from the result of k-1 rounds of the game, for example, if k=2, Jellyfish will know what Gellyfish will do in the next round, which is the result of k=1, this is "induction". The result of k=1 is very easy, which is written in the tutorial — swap the max and min. Thus when k = 2, you can predict what your opponent will do next, for each of your operational scenarios, you will choose the best one, this is "greedy"

  • 5 months ago, # ^ | nice thanks understood .

• 5 months ago, # ^ | ← Rev. 2 →   0 Somehow i managed to prove it myself. Let us assume that is a power of . So we can say that can be finitely represented as some binary representation like .Each individual people is going to get weight of apples and he will get this weight in denominations of . For each in we need to have exactly pieces . For an apple of weight we can get pieces each weighting and this will cost cuts. For each in we need to have exactly pieces each weighting and it can be done using number of apples having initial weight of and for each apples it will cost cuts . For each in we would need exactly cuts . Total number of cuts will be . We know that , then .So, the expression .

  • 5 months ago, # ^ | ← Rev. 2 →   0 "Since the number of apple pieces is added to exactly 1 for each cut, So we just need to minimize the final number of apple pieces." So is the final number of apple pieces, is the number of apple pieces in the beginning.

• 5 months ago, # ^ | ← Rev. 3 →   +8 I've understood the problem, I'am going to write up the solution in complete detail because I believe the solution provided leaves out a lot of detail that are not obvious at all First we need to encode reachability information from initial state of We do that by focusing on each bit of and as follows (since bits are independent and same bit combination goes together) We're going to represent reachability information from initial state as follows For each possible combination of initial state there are only 4 possible states it can reach to , and there are 8 possible initial states, so we can represent each of them using a 8-digit base 4 number, and we're only going to need possible configurations. Example : for configuration 00001003 initial state (0,0,0) can reach 3 = (1,1) initial state (0,1,1) can reach 1 = (0,1) all the other state can reach (0,0) What is the initial configuration ? It is simple, for each digit corresponding to , its value is simply Now, we want to find all such reachable configurations (cause clearly not all configurations are reachable), we do that by using the operations to define transitions Each configuration can reach to exactly 4 different configurations in a single step (using the different operations given as follows) Using operation op, we define the transition as For each digit corresponding to state , say it is we create new reachable state given by operation op (eg: in case of we have , ) Remark : We're changing all the digits because from a configuration of , in one operation it changes all of its bits, so the all 8 groups must be changed to reflect that. All the configurations reachable from initial config in this graph are exactly all those configs that are reachable from init config (preserving the number of steps), kind of obvious but this construction is quite meticulous Now that we have this graph we can do a BFS over it starting from initial configuration, and we can get all the states reachable from it along with minimum number of steps to reach that particular state. Now, given , we need to find a configuration where for each digit we have value at that digit, to find that we simply compute that configuration as say config and compute dist[config]. In case we get in consistency, while computing config i.e. if different bits of input corresponding to same values but has different value, then that configuration is not reachable. Doing this requires 5 states instead of 4. (so we'll instead encode using 5 base numbers, using 4 to specify state isn't set or we can say 4 is don't care) What if dist[config] == INF ? In this case we do not have any immediate inconsistencies, but the state is simply not reachable in the directed graph Hope that was helpful

  • 5 months ago, # ^ | Thank you, it helped me a lot

• 5 months ago, # ^ | The denominator on each slice needs to be a power of two. For example, you couldn't make of an apple with slices of , thus if and you can immediately say it's not possible.