Kilani's blog

By Kilani, history, 10 days ago, In English,

Hello everyone.

The problem set of the SPC 2019 will be available in GYM on Nov/09/2019 13:00 (Moscow time).

SPC is a training contest for Jordanians in summer.

The Contest will contain 12 problems written and prepared by Jester, Ayoub.aref and me Kilani.

The contest is around Div.2 difficulty, hope you enjoy your time and find interesting problems.

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

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C/D ?

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you tell me how can I view the tutorial

  • »
    »
    6 days ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    About C, The idea is that at any moment, $$$x$$$ is always a multiple of $$$a$$$. So you just need to break $$$n$$$ into its prime factors $$$p_1, p_2, p_3,..., p_k$$$ where each $$$p_i$$$ is a prime and they don't need to be pairwise different. The answer for this problem is $$$1$$$ $$$+$$$ $$$p_1$$$ $$$+$$$ $$$p_2$$$ $$$+$$$ $$$...$$$ + $$$p_k$$$ $$$-$$$ $$$k$$$. I will leave the proof for you as an exercise.

    For D, let's first check if the graph is already correct without the operator. Else, you must xor a non-empty set with some positive integer. If there exists edge of $$$u$$$ and $$$v$$$ and $$$a_u$$$ = $$$a_v$$$, then either $$$u$$$ or $$$v$$$ must be in the set. From here, the problem will become 2sat. To find suitable value so that it doesn't affect other edges, you can add every value of $$$a_u$$$ $$$xor$$$ $$$a_v$$$ to a set, and simply find the $$$mex$$$ of it.

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you please explain solution of problem J ?

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Another solution for D that doesn't use 2sat:

      Define the value of an edge connecting $$$u$$$ and $$$v$$$ as $$$a_u \oplus a_v$$$. As above, set $$$x$$$ to the mex of all the edge values. This guarantees that if an edge has exactly one endpoint which is toggled, the edge changes to $$$a_u \oplus a_v \oplus x$$$. Now consider the subgraph with only edges of value 0. We need to pick exactly one vertex associated with each edge. This is equivalent to checking if the graph is bipartite.

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve K?I dont know what the problem really requirements。