Блог пользователя mohammedehab2002

Автор mohammedehab2002, история, 3 года назад, По-английски

Hey everyone!

I'd like to invite you to participate in the ECPC 2019 Kickoff contest on gym on Wednesday, 08:30 UTC. The contest was originally held in Cairo in 2019, and we woke up today and decided to publish it.

The problems were created by me, TripleM5da, KhaledKEE, Mohammad_Yasser, Dark, and Jester. The contest will include 14 problems, and you'll have 5 hours to solve them.

We hope you enjoy it :D

Анонс ECPC 2019 Kickoff
  • Проголосовать: нравится
  • +64
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

PS: Osama_Alkhodairy was a tester.

»
3 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Thanks for uploading contest in gym! But i have 2 questions:

1) Is it team contest?

2) Is it suitable for master(s)?

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

    1) Yes

    2)During the official contest the top 3 teams consisted of masters and one of them had a grandmaster however none of them solved all the problems (not going to say how far they were thou) so yes even grandmasters will have fun participating.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks again!

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

      Where can I find the official scoreboard and the editorial of this contest?

      Note: thanks for uploading the contest, my team enjoy to solve the problemset

      • »
        »
        »
        »
        3 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +23 Проголосовать: не нравится

        Congrats for the win!

        So there's no detailed scoreboard, but the top 3 teams all solved 11 problems, and they were mostly masters and 1 GM. We didn't prepare an official editorial, but I'm guessing people will discuss the solutions in the comments. I see no teams solved I, so I'll start the discussion with its solution.

        I's solution
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve problem K, please?

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится
    Solution for problem K
»
3 года назад, # |
Rev. 8   Проголосовать: нравится +15 Проголосовать: не нравится
Solution for problem J
Solution for problem E
Solution for problem C
Solution for problem D
Solution for problem H
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What is the expected solution to H?

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +19 Проголосовать: не нравится
    H's solution
»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

How to solve problem B?

  • »
    »
    3 года назад, # ^ |
    Rev. 7   Проголосовать: нравится +2 Проголосовать: не нравится

    It is obvious that we should increase the length of a shortest side of the triangle. You can calculate the optimal increase using ternary search.

    Code

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      wow, I was doing 3 ternary searches to check which side I should increase.

      For some reason something went wrong.

      thank you!

      UPD: I changed this line in ternary search:

      (f1 < f2) ? l = m1 : r = m2;

      to this:

      (f1 > f2) ? r = m2 : l = m1;

      and I got accepted

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +22 Проголосовать: не нравится

    It also can be solved without ternary search: for two fixed triangle sides $$$a$$$ and $$$b$$$, the area is maximized when the third side is equal to $$$\sqrt{a^2 + b^2}$$$, that is, the angle $$$\alpha$$$ between $$$a$$$ and $$$b$$$ is $$$\frac \pi 2$$$. This is because the area is equal to $$$\frac 1 2 a b \cdot \sin{\alpha}$$$. Using this, we can just get as close to this value as possible.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can anyone please explain how to solve L?

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится
    L's solution
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      I solved problem L using relation $$$E((x+1)^2)=E(x^2)+1+2*E(x)$$$, if we generalize this relation for $$$K$$$ , we can use binomial expansion to calculate $$$E(x^k)$$$ from $$$ E(x),E(x^2)....E(x^{k-1})$$$.

      `

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve problem F? I couldn't get any further after simplifying the sum to $$$ (m1) \times(\sum_{x=l}^{r}((m2 \times x )+ x)-\sum_{x=l}^{r}((m2 \times x) AND x))$$$ where m1 is the minimum slope and m2 is the difference between the two slopes.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    The expression boils down to sum( (x<<s1) ^ (x<<s2)). Lets count for every power of two how many times it appears in the expression, fix the power of two K, and now we need to count how many binary strings less or equal than X exists such that exactly one bit from {K-s1,K-s2} is on, its classic dp on digits.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I try to submit this code several times but i get wrong answer in pypy2 but it run in my pc can someone help me to get this code accepted in pypy2?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

in problem M i take input with this way inp=open('lis.in','r') but it gives me RTE what is wrong and sorry for my bad English

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    i just add .strip() to second line and it get accepted Your code because when you add strip to readline() it remove '\n' this character from the string .

    hope it well__

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

WA on test 12 — Problem J

Try this test case
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can we solve Problem F, if $$$s1$$$ and $$$s2$$$ are not powers of $$$2$$$?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hi! can anyone share problem A solution. I am getting runtime error. Also why the third sample input has 39 as answer. It should be 36 I guess?