Iceberg's blog

Invitation to Winter Cup 6 Online Mirror (ICPC Rules, Teams Preferred)
By Iceberg, 8 months ago, In English

Hello CodeForces Community,

We are happy to invite you to participate in Winter Cup 6.0 Online Mirror Contest. The mirror is scheduled to take place on Codeforces at [contest_time:479486] and will last for 5 hours.

Winter Cup is a prestigious annual competitive programming contest held by ACM, INSAT Student Chapter. It unites Tunisia's brightest minds in a thrilling display of skill and innovation. Widely regarded as the nation's best competition, aside from the official ICPC regional contest.

The contest consists of 15 problems created and prepared by Iceberg, OussamaJB and ramizouari with difficulties from div2A to div1D.

We would like to thank :

Enjoy solving !

You can find here links to Winter Cup 4 and Winter Cup 5

UPD : Editorial

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

»
8 months ago, # |
← Rev. 2   Vote: I like it +12 Vote: I do not like it

Good Luck in the Contest !

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

[deleted]

→ Reply
»
8 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Good luck to the participants, I hope you enjoy the problemset !

→ Reply
»
8 months ago, # |
  Vote: I like it +15 Vote: I do not like it

Good Luck Guys. Hope you enjoy the problemset. Give us your feedback later!

→ Reply
»
8 months ago, # |
  Vote: I like it +14 Vote: I do not like it

As a tester I really enjoyed this year problemset! GJ guys!

→ Reply
»
8 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Good luck to the participants ! As a tester I enjoyed the problems!

→ Reply
»
8 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Is there any editorial?

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    The editorial is out. Check the link in the post.

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

I feel no. of participants in round do not justify the problem quality. Every problem had something unique and interesting.

Thanks to the authors really enjoyed the Problemset. Kudos.

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    CAn you share your approach for problem F find the tree?

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      This problem requires observation, Try to build a tree with some property and you will get the answer.

      First we have to take care of $$$v_i = i$$$ then we cannot construct tree.

      Now if our $$$ N = 2$$$ we will always have a tree. Given in sample case.

      For $$$ N > 2 $$$ if we have all nodes from $$$1, 2, ..., N$$$ in the $$$v$$$ array, tree cannot be formed. Because we cannot have all the nodes which are leaves.

      Now consider if a node is not present in the tree, you will always construct a Star Tree with this node in centre. So answer is Yes.

      → Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Thank you for your comment, we were really happy reading your feedback. I also wanted to say that we just released the editorial.

    → Reply
»
8 months ago, # |
  Vote: I like it -18 Vote: I do not like it

Excited for Winter Cup 6.0. A prestigious event showcasing Tunisia's top talent in competitive programming.

→ Reply
»
8 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Any hints for L2

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    if we find an index $$$j$$$ such that $$$a_j$$$ is a prime > $$$n/2$$$

    then for each $$$i \neq j$$$ ;$$$ \ lcm(a_i , a_j) = a_i \cdot a_j $$$ ; (so we can guess the whole array)

    because $$$a_i$$$ can't be equal to $$$a_j \cdot q$$$ where $$$q > 1$$$ otherwise it will exceed $$$n/2$$$.

    And we have $$$ m \approx \frac{n}{ln(n)} - \frac{\frac{n}{2}}{ln(\frac{n}{2})} $$$ primes > $$$n/2$$$

    $$$m/n > 1/30$$$ so we can use randomization.

    try 100 indices and check if one of them is prime $$$> n/2$$$

    and then we can guess the whole array.

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

      Thanks, I missed randomization idea.

      → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it 
      I have a doubt here!

n/ln(n)  is approximately the number of primes <=n right

n/ln(n)  - (n/2)/ln(n/2)   is basically number of primes > (n/2)

What is this thing like  m/n > (1/30)  and randomize idea , i am beginner in randomize idea
Can you elaborate a bit or some related resource
      → Reply
      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        errichto's video

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

          I have seen this But never solve a problem which uses randomization idea Can you elaborate this question a bit more, it builds analogy for me like where and how to check if randomization work or not

          → Reply