### YouKn0wWho's blog

By YouKn0wWho, 3 years ago,

Greetings good people of Codeforces. I hope you're having a great week.

We are hosting a contest based on the problems of SUST Intra University Programming Contest 2019. The contest platform is Toph. It was originally hosted on SUST's online judge SourceCode.

The contest will be held on Friday, December 20, 2019 at 15:00 UTC+06.

You will be given 12 problems in total and 5 hours to solve them. The contest will follow standard ICPC rules.

The problem setters of the contest are ovis96, YouKn0wWho, foyaz05, avivilla, FrozenBlood, mk_Shahriar and Jubair_2147483647.

To participate all you have to do is to create an account on Toph. You can register here. The contest link is here: smash me.

We tried to create very engaging problems, compact statements and robust datasets for this round. We hope that EVERYONE will find the problems stimulating and interesting. You can also participate as a team.

Note to anyone who participated in the onsite contest, please refrain from sharing or discussing the problems here before the contest.

Good Luck! See you on the leaderboard!

UPD: BUMP! 1 hour to go, buckle up!

UPD: Editorials

• +64

 » 3 years ago, # |   0 What is wrong with this approach for the interactive problem ?: If xor of all elems(x) = 0, output -1. Otherwise, consider the largest bit set in x, and using OR queries and binary search find the first element that has this bit set. Let's call it i. If i = n, output -1, otherwise output i.
•  » » 3 years ago, # ^ |   0 Logic seems right,may be a bug in implementation
•  » » 3 years ago, # ^ | ← Rev. 3 →   +16 I looked at your code. Your logic is absolutely right. But notice that before asking any query your code prints "!". So ultimately your code is getting 'wrong answer'. And also the right format of printing the final answer is "!"+single space+final answer.Update: As I presumed, now your code gets AC!
•  » » » 3 years ago, # ^ |   0 where can i submit solution for practice :)
•  » » » » 3 years ago, # ^ |   +11 We will update the problems for offline practice ASAP.
•  » » » » » 3 years ago, # ^ |   0 Ok Thanks
•  » » » » » » 3 years ago, # ^ |   +5 Problems are open now! GL & HF!
•  » » » 3 years ago, # ^ |   0 Thanks, but it was giving correct output on my Laptop. I should have realized that the cout statement may also execute this way. :(I removed the space later because I was not able to find out what was the mistake with my earlier submissions. Thanks again.
 » 3 years ago, # |   0 How to solve I ?
•  » » 3 years ago, # ^ |   +3 Refer to this solution : https://ideone.com/imNQNu . Comment if don't understand.
•  » » » 3 years ago, # ^ |   0 Can you explain your dp state ?
 » 3 years ago, # |   +6 Will any editorial be published for this contest?
 » 3 years ago, # |   0 Any hints for Problem K?
•  » » 3 years ago, # ^ |   +10 If the $1^{st}$ element of a special sequence is $x$ then the special sequence will look like $x, m-x, x, m-x, x, ...$
•  » » » 3 years ago, # ^ |   0 Can you please elaborate a bit? Also x can be greater than m..
•  » » » » 3 years ago, # ^ |   0 Let $C_i$ be the number of integers $p$ such that $p \mod m = i$So the number of special sequences having $x$ as its first element is $C_x*C_{m-x}*C_x*C_{m-x}*...$Oh, and it doesn't matter if $x$ is greater than $m$. In that case, just set $x= x \mod m$.
 » 3 years ago, # |   0 What's the solution of problem G?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +13 Let $F(n)=1^2*2^3*3^4*....n^{n+1}$We can rewrite it as $F(n)=\frac{n!^{(n+2)}}{1!*2!*3!*...*n!}$ Finding n!Let $P(x)=(x+1)*(x+2)*...(x+B)$So $P(0)=B!$ $P(0)*P(B)=(2*B)!$ $...$Now for finding $n!$ we have to evaluate the polynomial $P$ on $\frac{n}{B}$ points $P(0), P(B), ..., P(\left \lfloor{\frac{n}{B}}\right \rfloor*B)$ and then we can multiply the remaining elements using brute force. Note that the remaining elements are less than $B$.Now we can use multipoint evaluation for evaluating multiple points faster. So We have solved the problem!But here is an idea of using the $32kb$ source code space we are given! Set $B=10^6$. Then we have to evaluate the polynomial on at most $1000$ points given that $n\leq 10^9$. We can evaluate them offline in $O(10^9)$ and save them in an array. Here $mod = 10^9+7$. So the array will occupy less than $10kb$ of space. So here we go! Now we can generate the value of $n!$ in $O(B)$ where $B=10^6$ in our case. Finding 1!*2!*3!*...n!We can use the precalculation idea from above again. Note that the precalculation won't take more than $10$ seconds.Now the solution to our given product for some $l$ and $r$ is $\frac{F(r)}{F(l-1)}$Link to the solution: smash me
 » 3 years ago, # |   +6 Any hints for E and J?
 » 3 years ago, # |   0 Were we supposed to use Cayley's formula in problem J? By cayley's formula we can find the number of times each edge will contribute to the answer.
 » 3 years ago, # | ← Rev. 2 →   0 For E I don't know why this idea is wrong:1) If there is a negative cycle in the graph output "NO".2) Find all the Strongly Connected Components of the graph and make an edge from node 0(weight of edge=0) to all the SCC in which indegree is 0. 3) now find distance of all nodes from node 0 and output the corresponding distance as the value of that node.
 » 3 years ago, # |   0 How to solve A?My thoughts: given $x = c+1, y = mx+c$.We have $y = m(c+1) + c$. From this, I concluded that as long as $y+1$ is not prime, that value of $y$ will be $y$-coordinate of some special point.So, I reduced the problem to finding smallest $y$ such that, $y - pi(y) == k$. ( $pi(y)$ is the number of primes less than or equal to $y$ ). How to efficiently calculate $pi(y)$? Also, is there another easier approach than this?
•  » » 3 years ago, # ^ |   0 SpoilerPrime Counting Function
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 I googled after ( and during ) contest and found that blog, but couldn't find good implementation of the Meisell-Lehmer algorithm. If you can, please provide some resourceAlso, was this the intended solution?