Iceberg's blog

By Iceberg, 7 weeks 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

»
7 weeks ago, # |
Rev. 2   Vote: I like it +12 Vote: I do not like it

Good Luck in the Contest !

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

[deleted]

»
7 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

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

»
7 weeks 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!

»
7 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

Is there any editorial?

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

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

»
7 weeks 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.

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

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

    • »
      »
      »
      6 weeks 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.

  • »
    »
    6 weeks 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.

»
7 weeks 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.

»
6 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Any hints for L2

  • »
    »
    6 weeks 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.

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

      Thanks, I missed randomization idea.

    • »
      »
      »
      6 weeks 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
      
      
      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        • »
          »
          »
          »
          »
          6 weeks 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