When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

Dijkstra.'s blog

By Dijkstra., history, 5 years ago, In English

The 2018 Egyptian Collegiate Programming Contest was held yesterday this was a problem from it where he asks for

Where n<=10^5 and a[i]<=10^5 answer should be printed %10^9+7

I would appreciate any help in solving this problem and thanks in advance

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

| Write comment?
»
5 years ago, # |
Rev. 2   Vote: I like it +33 Vote: I do not like it
hint
solution idea
code
»
5 years ago, # |
  Vote: I like it +25 Vote: I do not like it

Mhm... nice problem. Do you agree, mnbvmar?

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it +27 Vote: I do not like it

    <3

    Story: We proposed this exact task (under a tiny bit different constraints, though) to our high school students back in 2015. I was quite surprised that apparently it has never appeared anywhere even though the statement feels really natural and obvious. So it seems it eventually did!

    I think tribute_to_Ukraine_2022 came up with another solution, involving...

    Spoiler

    I can't remember any details, though. Mind sharing (if you still remember it)?

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it +14 Vote: I do not like it
      Solution
»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone tell me why my solution gives TLE.

If I am analysing time complexity properly, my code should take $$$O(n + max(a_i)*log(max(a_i)))$$$ time per test case.

Submission : 111169206