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

Автор SureYeaah, история, 5 лет назад, По-английски

Hey Codeforces!

NJACK the programming club of IIT Patna presents to you our annual algorithmic event ByteRace 2k19. The contest will take place on HackerEarth on 15th November 21:00-23:30 (IST)

The contest will be ACM-style with 7-8 problems.

Thanks to the following people for making the contest:

Nightmare05 ck98 scameeer hackcyborg darklight13 LightYear leviOosa

Link to the contest: https://www.hackerearth.com/challenges/college/byterace2k19/

Prizes :
1st Prize 7500 INR
2nd Prize 5000 INR
3rd Prize 2500 INR

HackerEarth T-shirt to top-5 Indian participants.

For prizes fill the following form :

https://forms.gle/K2ueg7QXkH9R2hqR9

  • Проголосовать: нравится
  • +56
  • Проголосовать: не нравится

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

Reminder Contest will start in 6 hours from now.

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

Who are eligible for the prizes in this contest?

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

    For cash prizes it is global i.e literally anyone and for HackerEarth T-Shirt winner must be Indian resident.

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

Update

Contest starts in an hour. This thread can be used for post contest discussions.

All the best for the contest.

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

Proof for last problem?

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

    I'll publish the editorial in less than 6 hours but meanwhile just a hint think pigeonhole, and sorry bro just was really stuck in assignments

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

Idea for 1-2-3 subsequence??

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

    In every node of segment tree keep values len[i][j] — length of longest increasing subsequence in this node of numbers from i to j.

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

      So each node will contain the longest non-decreasing subsequence of following types right smallest value=i and largest value=j i=[1,3] and j=[i,3]. Then it will become easy to merge two nodes.

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

        If in node v we have len[i][j] = x -> means that the maximum possible length of longest incresing subsequence of numbers i, i + 1, ..., j (within node v). For example, if node v corresponds to array [1, 2, 1, 3], then len[1][2] = 2, len[1][3] = 3.

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

    To answer query $$$(l, r)$$$, suppose you choose all 1's in range $$$(l, i)$$$ all 2's in $$$(i + 1, j)$$$, and 3's in $$$(j + 1, r)$$$ for some $$$i, j$$$.

    Let's say $$$cnt_j[i]$$$ is the occurrence of $$$j$$$ in $$$[1, i]$$$

    Now you have to maximise

    $$$ ( cnt_1[i] - cnt_1[l - 1]) + (cnt_2[j] - cnt_2[i]) + (cnt_3[r] - cnt_3[j])$$$
    $$$ = (cnt_3[r] - cnt_1[l - 1]) + (cnt_1[i] - cnt_2[i]) + (cnt_2[j] - cnt_3[j])$$$

    for some $$$l - 1 \leq i \leq j \leq r$$$

    First term is constant and the maximum sum of second and third can be maintained with a segment tree.

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

How to prove that $$$2^n$$$ / 4 + 1 is actually enough in the last problem?

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

We will publish the editorial soon.

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

Deleted.

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

Please move problems to practice section

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

    Please go through this link Byterace. Problems are available in practice section.

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

      Although I'm able to submit, but here's how the problem's page looks like:

      image

      Also, please make the test cases visible. That'll be helpful.

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

        Although they have written this, But you will be able submit it. Just try it once. I have also tried to submit right now and able to submit it.

»
5 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
For the rhombus problem will this be sufficient? 
1. Finding the primes using seive of eratosthenes. 
2. For each prime check how many points satisfy the given condition.
3. Print the maximum number of points. 

Do anyone have more elegant method than this or is this the only way? Thanks enjoyed the problems. 
  • »
    »
    5 лет назад, # ^ |
    Rev. 5   Проголосовать: нравится +10 Проголосовать: не нравится

    My initial approach was-

    1.Store all points perpendicular distance from line x+y=0(1st and 3rd quadrant) or x-y=0(2nd and 4th quadrant) in a vector and sort it (Every distance will be of form |x+y|/sqrt(2) or |x-y|/sqrt(2))

    2.For each prime number P between 0 to 3*10^6 (which I have pre-computed using Seive of Eratosthenes) calculate

    upper_bound( P+k/sqrt(2) ) minus lower_bound( P /sqrt(2))

    which gives me the number of points inside the shaded region

    Screenshot-2019-1116-131727
    pic hosting
    https://imgur.com/lvuexwC

    3.I iterate over all primes store the maximum of this result every time

    I was getting wrong answer in one test-case still , so I removed the sqrt(2) from everywhere ( since it occurs everywhere and removing it would result in no change in the answer because we just have to count the number of asteroids ) and got AC!

    It was a good problem requiring multiple concepts involving Mathematics,Sieve,BinarySearch,etc

    Cheers! :)

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

      Firstly, you don't need $$$4$$$ quadrants, you can simply move all the points in the first quadrant by changing $$$(x, y)$$$ to $$$(abs(x), abs(y))$$$ and it will not change the answer. Now, a rhombus is reduced to a line having a slope $$$-1$$$.

      Secondly, a line passing through $$$(x, y)$$$ having a slope $$$-1$$$ will meet the axes at points $$$(x+y, 0)$$$ and $$$(0, x+y)$$$. A rhombus in our case corresponds to a line with slope $$$-1$$$ passing through $$$2$$$ points of the form $$$(a, 0)$$$ and $$$(0, a)$$$, for some $$$a \ge 0$$$.

      Now, the problem is simply this: For a prime no. $$$p$$$, you have to find how many points $$$(x, y)$$$ have $$$(abs(x) + abs(y)) - p \le k$$$. If you use a frequency array, with $$$freq[i] =$$$ no. of points having $$$abs(x) + abs(y) = i$$$, the problem is reduced to obtaining the sum of $$$freq[p .. p + k]$$$, which can be computed using prefix sums over the frequency array, and you do this for all primes $$$p$$$, and take the maximum over them, which will be the answer.

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

what should i do to recieve my prize ?

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

Guys please be patient I will publish the editorials today within 6 hours along with proof for last question, we were really screwed up with assignments and presentation in our college, kindly understand and bear with me, but I promise it'll be out as soon as possible

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

All the prize winners, please wait our team will reach out to you within a week. Thanks for giving the contest and making it a huge success.

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

Update: Results and Editorials published here 71483. Thanks for your patience.