Adam.Aly's blog

OI Contest #1 Review
By Adam.Aly, history, 2 years ago, In English

I hope you enjoyed the contest.

(If you didn't join the contest you can virtual participate it or enter as practice through this link and tell us your review)

The Editorial will be posted soon.

We want to know your review for today's problems.

A. Infinitely Repeating

  1. Perfect
  2. Good
  3. Normal
  4. Bad
  5. Didn't read

B. Way To Market

  1. Perfect
  2. Good
  3. Normal
  4. Bad
  5. Didn't read

C. GCD Problem

  1. Perfect
  2. Good
  3. Normal
  4. Bad
  5. Didn't read

D. New Path

  1. Perfect
  2. Good
  3. Normal
  4. Bad
  5. Didn't read

E. Bit Madness

  1. Perfect
  2. Good
  3. Normal
  4. Bad
  5. Didn't read

Thanks for your review and if you have any additional comments about the contest you can comment below.

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

»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Link is not working to open the contest

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

    Sorry for the inconvenience, I sent the link without the invitation. It is correct now you can try it.

    → Reply
»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Auto comment: topic has been updated by Adam.Aly (previous revision, new revision, compare).

→ Reply
»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Nice Contest, I Enjoyed Most of the problems

One suggestion though, please avoid using doubles and floating point problems in OI Style, and test the problems before running the contest

Other than that the contest was perfect :)

→ Reply
»
2 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Average contest

Pros : Nice Problems

Cons : No Enderman Statements

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to get the exponent of $$$a$$$ in D? If you could quickly get an exponent of $$$a = 2^{x}$$$, then there is just a simple observation that for every edge you just need to consider it's most significant bit (if edge has weight 0 then just remove it and split the tree into 2). Then the problem reduces to finding path with maximum sum in a tree which is a classic problem. So you just check if the sum is greater than or equal to x.

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

    To get the exponent, it can be shown that for any power of two $$$h$$$ having $$$d$$$ digits there is not any other power of two having the same $$$d$$$ and the same $$$d$$$-th digit ($$$\lfloor \frac{h}{10^{d-1}} \rfloor$$$). For example, let's consider $$$256$$$ the next power of two ($$$512$$$) differs in the last digit ($$$5$$$), based on this $$$log_2(256)$$$ is the same as $$$\lceil log_2(200) \rceil$$$ because there is not any other power of two having the same number of digits and the same $$$d$$$-th digit, now let's represent this as a mathematical formula, let's call the $$$d$$$-th digit $$$r$$$, $$$\lceil log_2(r \cdot 10^{d-1}) \rceil$$$ which can be also written as $$$\lceil log_2(r) + (d-1) \cdot log_2(10) \rceil$$$ and can be easily calculated.

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

    there is just a simple observation that for every edge you just need to consider it's most significant bit

    I don't think that this is correct, what if you had $$$111_2$$$ ($$$7$$$) and $$$110_2$$$ ($$$6$$$) their product is $$$101010_2$$$ ($$$42$$$) having $$$6$$$ bits. But if you made them $$$100_2$$$ and $$$100_2$$$ ($$$4$$$) their product is going to be $$$10000_2$$$ ($$$16$$$) having only $$$5$$$ bits

    → Reply