Kilani's blog

[GYM] SPC 2019
By Kilani, history, 5 years 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

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

How to solve C/D ?

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

    Could you tell me how can I view the tutorial

    → Reply
  • »
    »
    5 years 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.

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

      can you please explain solution of problem J ?

      → Reply
    • »
      »
      »
      5 years 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.

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

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

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

Very nice problems! But I can't figure out how to solve some of them, could you please share the tutorial?

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

There are some mistake in problem I's statement:

  • The first type of query said that "print 1 if all values of $$$a_i$$$, such that $$$l \leq i \leq n$$$, are equal". I think it should be $$$l \leq i \leq r$$$.
  • It did not stated in the constraint part that $$$l \leq r$$$. I had to submit code with assertion to make sure that this case is not in the test
  • Not really a mistake, but:
$$$a, b \leq |10^8|$$$

And I thought that $|a|, |b| \leq 10^8$ for the entire contest time, which wasted about 2 hours of my contest time. This is not fun.

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

    We are extremely sorry for that. I'll fix the statement.

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

How to solve problem E?

→ Reply