ISQUARE TSQUARE DISCUSSION

can anyone share the editorials of ISQUARE TSQUARE contest.

you can also share your thoughts and approaches to the questions.

it will be huge help for me and everyone else out their : )

(especially the last four questions)

3 Likes

@worldfinal pls share the editorials of problems at least for the last one.

In case the Reverse Coding sequence didn’t “click”, the subsequent member is a description of its predecessor:

19

one 1, one 9 → 1119

three 1s, one 9 → 3119

one 3, two 1s, one 9 → 132119

one 1, one 3, one 2, two 1s, one 9 → 1113122119

And because the maximum sequence member (N) that will be requested is 20, you should pre-compute the first 20 members rather than recompute on each input request.

1 Like

For Chocolate Pairs, you need to match up each chocolate with all the other chocolate that make it up to the right price.

One way to do this is collect frequency of each chocolate price, then work out from there how many ways there are to reach the target price. So given input of

21 8
6 5 4 3 2 1 5 4 3 2 1 4 3 2 1 4 5 4 5 4 6 

you can accumulate prices to get a 1-based frequency array of [ 3, 3, 3, 6, 4, 2 ]. Then multiply appropriate frequency groups and get the count for n/2 if present.

So for example with a target price of 8, and with 3 chocolate costing 3 and 4 chocolates costing 5, those contribute 3*4 = 12 options.

However with 6 chocolates costing 4, those alone contribute only (6*6 - 6)/2 = 15 options as you can’t pair a chocolate with itself and each pairing should only get counted once.

There is a naive method that works well also. Take each chocolate in turn and add to the pairs total the number of pairing chocolates you have already seen.

for Power of Power, if your language doesn’t have an equivalent of Python’s three-parameter pow(x,y,z) which efficiently computes x^y \bmod z, you will need to code that, for example by taking the mod continuous during exponentiation by squaring. Search for that phrase with “code” to find lots of examples.

Then the given expression is (n_1^{k_1})^{\large n_2^{k_2}} \bmod n is actually n_1^{\left(k_1 n_2^{k_2}\right )} \bmod n. In order to compute this you need a bit of number theory to know that for typical values of the exponent we can reduce \left(k_1 n_2^{k_2}\right ) \bmod \phi(n) where \phi is Euler’s totient without changing the outcome (provided we still have sufficient of the common prime factors of n_1 and n). Finding Euler’s totient can most easily be done by finding the prime factors of n and calculating as per the wikipedia article. Then you basically just need to handle the special cases of zeroes and small values of the exponent.

1 Like

for Knowledge is Fun, we basically have to maximize a linear function over the array with values taken in a given order.

I did this by extending stepwise from the shorter functions with fewer terms, for different portions of the array. Thus we can determine what the maximum value of E*X_i is for any given restriction on the start position of X_i - it’s just maximum up to that point. Then we can similarly get an array of values with the -D*X_j term added by finding the maximum across the array with that term and the maximum of the E*X_i term available to a given position, which we know from the first step. And so on adding each term using the previously defined maximum values per array position.

1 Like

In Big Tournament, there is a devastating shortcut to the right answer.

Of course it’s possible to model the games, or the successive rounds, to count games. But there is a much simpler route to the answer. By way of sneaking up on it, we’ll have a tournament with n=11 entrants, play a few qualifier games to get to a nice power of two, then run the rest of the tournament…

  a   b   c   d   e   f   g   h   i   j   k
  a   b   c   d   e  (f   g) (h   i) (j   k)   3 games
  a   b   c   d   e   h   i   j
 (a   b) (c   d) (e   h) (i   j)               4 games
  b   c   e   j
 (b   c) (e   j)                               2 games
  c   j
 (c   j)                                       1 game
  j

So, how many games? 3+4+2+1 = 10. And how many players left at the end? 1, the champion. And that’s because: everyone else lost exactly one game. So the number of games is exactly the same as the number of players that are eliminated; that is, n-1.

any other thoughts are also welcomed : )

plz share as much as u can

in Sum of Digits, again it is possible to model everything directly, including getting the recursive digit sum (RDS) of many numbers. However that way lies “TLE”, Time Limit Exceeded.

If we look at the RDS for some random consecutive block of numbers, a shortcut appears:

start: 2489
end:   2521

RDSs:  5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1

showing a repeating pattern of 1 2 3 4 5 6 7 8 9. This is related to the well-known divisibility-by-9 test.

A reasonable solution can be found by getting the digit sum at the start M and then moving if necessary to the first match F for the required RDS X. Then you can get the number of multiples of 9 to reach the final number N by dividing the remaining difference N-F by 9 and adding one (since F already qualifies).

Note that directly making RDS is not needed either; the RDS of M is just M \bmod 9, except for switching in 9 for 0.

@joffan Can you please elaborate Power of power more clearly.It will be greatly appreciated.

i got it now

thx for the help : )

I didn’t got this one may be u can explain it more clearly

@rajput1999 added example

@joffan has already answered almost all of the questions bro

u can go through them

@joffan has already answered almost all of the questions

thx to him u can go through them

nice thought :slight_smile: I appreciate it

… and that completes the set. I was (and still am) hoping maybe someone else would jump in with any other methods used for any of the problems.