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.
Also, there will be an interactive problem. If you don't know about interactive problems, please refer to this article.
Good Luck! See you on the leaderboard!
UPD: BUMP! 1 hour to go, buckle up!
UPD: Editorials
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.
Logic seems right,may be a bug in implementation
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!
where can i submit solution for practice :)
We will update the problems for offline practice ASAP.
Ok Thanks
Problems are open now! GL & HF!
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.
How to solve I ?
Refer to this solution : https://ideone.com/imNQNu . Comment if don't understand.
Can you explain your dp state ?
Will any editorial be published for this contest?
Any hints for Problem K?
If the $$$1^{st}$$$ element of a special sequence is $$$x$$$ then the special sequence will look like
Can you please elaborate a bit? Also x can be greater than m..
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
Oh, and it doesn't matter if $x$ is greater than $$$m$$$. In that case, just set $$$x= x \mod m$$$.
What's the solution of problem G?
Let
We can rewrite it as
Let
So
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.
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
Any hints for E and J?
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.
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.
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?
Prime Counting Function
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 resource
Also, was this the intended solution?