Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

Блог пользователя Kilani

Автор Kilani, история, 4 года назад, По-английски

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.

Анонс SPC 2019
  • Проголосовать: нравится
  • +52
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve C/D ?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Could you tell me how can I view the tutorial

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      can you please explain solution of problem J ?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

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.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve problem E?