justHusam's blog

By justHusam, 4 weeks ago, In English,

Hello Codeforces,

I would like to invite you all to participate in the 2017 JUST Programming Contest 4.0 of Jordan University of Science and Technology. The contest was originally held on 16th of September , and it will launch in Codeforces Gym tomorrow Saturday 23 September 2017 14:30 UTC.

The problems were prepared by justHusam (Husam Musleh) and Vendetta. (Ibraheem Tuffaha).

Thanks to I-Love-Islam (Rami Sadaka) and The-Legend (Abdulmajeed Alzoubi) for sharing the ideas of two problems.

The duration of the contest is 4 hours, and the registration will be open 6 hours before the start of the contest.

Good luck for everyone, and I wish you all Accepted solutions.

Note: Don't forget to use fast I/O methods.

UPD: Registration is currently open.

UPD: The contest will start in 30 minutes.

UPD: Tutorial

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

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

Should it be done in team or individually?

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

    The onsite contest was made for teams of no more than Experts level, so a Candidate Master is preferred to participate alone.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is "Scanner sc = new Scanner (new File (PATH))" considered as a fast I|O method in java ?

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

    No. You need to use BufferedReader / PrintWriter instead of Scanner / System.out

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve A?

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

    Hint: Consider bits one by one.

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

    Sorry for the latency, you can check the editorial: http://codeforces.com/blog/entry/54840

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

Could you share F's tests, or it's generator please?

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

    Why do you want to see the tests or the generator?

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

      I couldn't figure out why my code was giving WA, but it's working correctly now, so never mind.

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

Can someone explain the solution for F ?

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

    You can calculate the number of palindromic substrings for each string, and map strings, to their index. After that you reduced the problem to a max range query.

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

      We calculated the no of palindromic substrings in O(30*30) time. Is it expected one ?

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

        Yes, it runs fine, in case my solution passed in 1746 ms.

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

          Can you share your solution please :)

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

            https://ideone.com/U1GmWp
            It's basically what bazsi700 explained, I counted the value of palindromes for every string, mapped the strings with a trie and used a sparse table to do the queries

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

              Could you please tell me why I'm getting TLE on test 2 with this code? https://ideone.com/4TrlFW

              I wrote I/O as you did to be sure it wasn't that.

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

                Well, it's better to use sparse table and unordered_map in your code, but you would receive wrong answer because what calculate the length of a C string is strlen, since you are using sizeof, it's the same as to add the same thing for all values of strings. And you have to treat the case when l > r.

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

                  Yes I noticed the case when l>r, and I didn't know about strlen, thank you very much. But the TLE is because of the segmentTree factor which is a little bit worse than sparse_table?

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

                  Probably yes, try to optimize the query in the range and how you find the index of some string, I used a trie for example.

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

        That only means O(104 * 30 * 30) ≈ O(107). If you are getting TLE, then other part of your code is too slow. You must use fast IO.

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

    Sorry for the latency, you can check the editorial: http://codeforces.com/blog/entry/54840

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

Can someone give a hint on E?

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

    Meet in the Middle

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

    Think about divide and after join

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

    Sorry for the latency, you can check the editorial: http://codeforces.com/blog/entry/54840