dragonslayerx's blog

Invitation To Alkhwarizm 2016
By dragonslayerx, history, 9 years ago, In English

Hello Everyone,

We gladly invite everyone to participate in Alkhwarizm organized as a part of annual Techfest of IIIT Allahabad–Aparoksha 2016.

The problem setters and tester are Xsquare, hagu, Divanshu, m17, dragonslayerx, ayush_awasthi. The problem setters have tried to bring many interesting problems for everybody this time.

The contest starts at 9:00PM (IST) on 3rd April, 2016. Check you local timezone here. It is an individual contest with 5 hours duration.

The Total Prize at stake is Rs. 50,000. For Indian Winners distribution is Rs 20,000, 15,000 and 10,000 for 1st, 2nd and 3rd rank respectively. Also CodeChef will provide goodies to International Winners.

The Registration Link for the prizes is here. Click here to Register

The Problem Set will consist of 10 Problems for various topics of Competitive Programming. It has problems of various difficulty levels and diverse fields so we hope everyone will find something of his taste. Editorials to all problems will be provided as soon as the contest ends. Follow the event page for more updates.

Link to Facebook Event — Event Page

Link to Contest — https://www.codechef.com/ALKH2016

Happy Coding!!!

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

Comments Comments (11)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

Will there be prizes for Non-Indian Winners too?

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

    Lots of exciting Codechef goodies including Tshirts and Pendrives to be given to Top 3 Non-Indian participants.

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

Update: The contest is going to start in 1 hr 30 minutes. Get ready :)

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

How to solve this problem : https://www.codechef.com/ALKH2016/problems/NRTKH

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

    The trick when we have something like 2 * f(a) = 3 * f(b) is to give a value to those letters, so if we make a = -2, b = 3, c = 0, we need to count the ranges [L, R] which sum up to 0 (forgetting, for now the condition that the range must have an a or b).

    Let's make an array pref[], pref[x] = sum [0..X], that is, the sum of values till index X. Now, if we have two different indices i, j, such that pref[i] = pref[j] this means we have found a range which we must count.

    Let's loop from the begin to the end of array. We are at index i now and will count how many ranges are valid that end in i, which is just the count of values that have same pref[i]. This can be done in O(nlogn) using a map in C++, for instance.

    So the only thing left is to discard ranges that only contain 'c'. Notice that this ranges are summed up in our final answer when we have a contiguous range of c.

    Here is my implmentation

    http://pastebin.com/7EbT1fHF

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

      @ivanilos Thanks a lot for your explanation and code :D

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      @ivanilos I have read your code but I am not able to understand how you are dealing with 'c'. Please describe it in detail.

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

        Did you get that the extra counting is because of contiguous 'c'? If so, notice that when looping through a string of 'c' when we are at the first 'c' there is only one string (that only has 'c') ending at this position. When we are the second position, there are two strings ending at this position, namely, "c", "cc", so that's why I increment the variable seg and subtract it from the result (it may change whether you increment seg before or after decreasing depending or your implementation, but that's the ideia).

        You may see that, in the end, what I am doing is just subtract all possible substrings of a contiguous range of 'c' — if it has len N it will have substrings

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

Where is editorial

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

Update: the editorials have been updated. Please check them at the following link. https://tp-iiita.quora.com/Editorials-of-Alkhwarizm-2016

→ Reply