YouKn0wWho's blog

Contest Based on SUST Intra University Programming Contest 2019
By YouKn0wWho, 5 years ago, In English

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

  • Vote: I like it
  • +64
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Logic seems right,may be a bug in implementation

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it +16 Vote: I do not like it

    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!

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      where can i submit solution for practice :)

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve I ?

→ Reply
»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Will any editorial be published for this contest?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any hints for Problem K?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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, ...$$$
    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please elaborate a bit? Also x can be greater than m..

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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$$$.

        → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the solution of problem G?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +13 Vote: I do not like it

    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!
    Finding 1!*2!*3!*...n!

    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

    → Reply
»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Any hints for E and J?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply