smokescreen's blog

By smokescreen, history, 6 years ago, In English

Hello Codeforces!!

This was our first attempt at making a contest.

I and my friend, a_kk , we both made a contest for our college. There were a total of 6 problems(4 easy and 2 medium) and participants were given 2 hours to solve them.

The problems are interesting. All those who want to try them are invited. If you're an expert or less, then definitely, you'll learn something :)

Link to the contest : link

It would be lovely to have feedback from your guys!

Happy solving!!

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

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

How to solve "Jitu and strings" if the no of swaps was given to at most K. Where K could be in the order of length of the string?

»
6 years ago, # |
Rev. 4   Vote: I like it +6 Vote: I do not like it

I solved 4 problems in 2 hours:

  • "A. hmrockstar at bank" — O(n), linear maximum search. Code.
  • "B. haaby's dream job — Digital Cleaner" — O(sqrt(k)), mathematics, dividers, combinatorics. Code.
  • "C. KJ and street lights" — O(n sqrt(n)) — SQRT-decomposition + linear search for the maximal sequence of zeros. Code.
  • "D. Jitu and Strings" — O(n log(n)) — polynomial hashes + binary search. Code

After 2 hours solved:

  • "E. Arun sir and his girlfriend!" — O(n log(n) * WORD_WIDTH) — sort + implicit prefix tree + binary search. Code

Nice problems, thanks! Is the contest already complete and can I open the source code of solutions?

And your problem D does not contain an anti-hash test :((

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

    nice to hear that u liked the problems :)

    As it was our first contest we didn't knew the testcases were weak for polynomial hashes.We were lucky that no one made a submission using similar solution to yours :P. We will try to add a anti-hash test case though.

    The solutions have been made public.

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

      Will you publish editorial?

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

        Yes, I've published the editorial.

        The editorial consists of brief explanation of the approach to solve the problem. Still, I have made my solutions available for reference. If there is still something unclear, just do tell us. We'll be happy to help. :)

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

          I solved the problem "E. Arun sir and his girlfriend!" and added the code. I think that this is easier, than jury solution in editorial.

          Solution: sort + implicit prefix tree + binary search, O(n log(n) * WORD_WIDTH)

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

            Should in problem B the answer of the test case 4 4 2-> 24 12 horizontal and 12 vertical.

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

              No. Please re — read the question. The grid is formed by n and m lines, so the size of grid will be (n — 1) x (m — 1)

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

                Oh sorry I got it now Thanks :) Can you help me in one more thing?

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

Nice problems. But can these problem be added in any vjudge contest? I tried, but vjudge couldn't crawl the problems. Any way to add in vjudge contest ?