adurysk's blog

ACM ICPC Preparatory Series — Cool Prizes to be won!
By adurysk, 9 years ago, In English

We gladly invite all the programmers around the world to take part in the " IPC ACM ICPC PREPARATORY SERIES "

Yes! There is Huge cash prize at stake!

This is a team contest (upto 3 participants in a team) of 5 hours each with ACM ICPC rules, organized on CodeChef. This is a unique series of 12 contests, where there is a separate cash prize for the problem setters as well. There are 9 problem setting teams consisting of around 7 problem setters each. Problem setting teams compete among themselves to make better problem sets.

Cash Prizes

For the final winners in rest of the world category:

  • 1st Prize: $1000
  • 2nd Prize: $500
  • 3rd Prize: $200

For the final winners in Indian category.

  • 1st Prize: INR 50,000
  • 2nd Prize: INR 25,000
  • 3rd Prize: INR 10,000

Eligibility Criteria

The IPC programming series, though aimed at ACM ICPC aspirants, is not limited to them. Anyone who wants to try their hand at the problems from some of the finest programming minds in India can do so. Yes! It is open to all the programming enthusiasts across the globe.

Registration

You can register for the contest at https://www.codechef.com/teams/register/IPC15P1A

To know more about what IPC is, and for further details about schedule, event format and rules, please visit https://www.codechef.com/ipc/2015

UPD1:

With a lot of twists and turns in the leaderboard, the first contest of the series has concluded with the team sequoia winning! Congratulations! The complete leaderboard is available here. The problems can be seen here. The editorials are available here.

UPD2:

The second contest of the series will be starting in less than 22 hours!

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

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

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

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

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

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

dis luks awsum

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

Exciting.............

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

We are allowed to use only one computer to write code right ?

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

    Its not mandatory to use one computer, you can use multiple computers.

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

      I keep in mind the fact that organizers can't check that every team is using only one PC, and also I understand that it sounds fine to use multiple computers when teammates are participating online from different places, but if you mean "multiple computers at the same time" — what is the point in preparation to ICPC while practicing some contests which are completely different from ICPC? You can't use multiple PC at WF and at most of regionals/qualifiers.

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

        Maybe removing prizes from the contests and imposing the one computer a team restriction would ensure that the teams do the contest sincerely and don't use multiple computers.

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

What is the estimated difficulty of those problemsets (both eliminations and finals)?

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

    This is a hard question to answer. Though we did not put any limit on how much hard the hardest question should be, we tried to see that there is good gradient in the difficulty of the problems and that there is good variety in the topics. We also tried to ensure that the problems are genuine and not easily searchable on google.

    The teams which are making the problem sets have wide variety of people ranging from green coders in CF to past ACM ICPC World Finalists.

    So, you should be expecting some, if not, more challenging questions in both eliminations and finals! :)

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

My submision on Magical Strings getting TL. (I used DSU structure in my solution.) What is intended solution? Or how can I speed up my solution to meet TL.

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

    You need to process all palindromes with the same center together, i.e. for each center you only need to know the maximum radius of the palindrome with that center. Our solution.

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

      agree. For this reason I had added this piece of code.


      rep(i, m) {
      int l, r;
      scanf("%d%d", &l, &r);
      --l, --r;
      if (seen[l].count(r)) continue;
      for (; l < r; ++l, --r) {
        if (seen[l].count(r)) break;
        join(l, r);
        seen[l].insert(r);
      }
    }

      I thought that marking just processed part of palindrome and not repeating it is enough... somehow can not get why this is not the same to what you are saying...

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

        After removing additional log(N) factor (which appears because you are using sets instead of straightforward true/false tables) from your solution it passes in 0.7 seconds.

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

I don't really understand the rules. Is $1000, $500, $200 the prize for today's contest or the whole series?

Nevermind, I can see now that the prize is for the whole series

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

    The prizes $1000, $500, $200 are for the top 3 spots taking into consideration of the cumulative score of the final 3 contests, and not for the first 9 contests. The first 9 contests serve as the elimination contests to the finals. Sorry for the inconvenience.

    Please check https://www.codechef.com/ipc/2015 for all the details regarding the contest series.

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

problems are not available in practice. I keep getting this message "Problem is not visible now. Please try again later."

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

    They have been. Can you check again and if it still does not work, send me a snapshot of what you get?

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

      it works now for me. Unfortunately, I do not remember the text of the message. :(

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

The last problem was nice, thanks. But the previous problems could have been harder, I think :)

The competition between problemsetters is an interesting challenge, I've never seen this before. I'm just curious, how do you plan to rank the problem setting teams? Will it be some voting, or maybe some criteria based on the final standings of each contest?

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

    The last problem was supposed to be easy-medium and we expected a lot more ACs on it before the start of the contest :P Thanks for the feedback.

    Yes, we are planning to use voting from a selected pool of people. Rating will consider the following in that order, most important one at top:

    • Uniqueness of the problems. Copying or doing simple modifs to existing problems is bad.
    • Clean contest — Proper testing, no issues after start of contest with test data, clear statements.
    • Team effort. We want everyone from the team to contribute and learn.
    • Good difficulty gradient.
    • Good Editorials.

    You can refer this, this, and this to know about how we started this initiative :)

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

      How to solve "Max Subarray GCD" ? The editorial doesn't help much . Thanks in advance :D

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

        I solved it using binary search + sparse table — http://ideone.com/54qCmX :)

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

        Hi , i am the author of the problem and here is the expected solution

        We can perform a binary Search on answer 

         while l < r: 
             mid = (l + r) / 2 
             if check(mid): 
                 l = mid + 1 
             else: 
                 r = mid

        Now we just need to write an efficient check function

        Now suppose we want to check if any subarray of size 'X' exists which has GCD >= K , To do this , we divide the array in blocks of size 'X' and calculate the prefix and suffix GCD for each block , this will help us calculating the GCD of any block of size 'X' in O(1) time with O(N) pre processing.

        The complexity of this solution is O(N * LOGN * P) where P is time taken for calculating GCD

        http://ideone.com/UKdXBa

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

          It was really helpful , i think it would be really awesome if the problem authors themselves would have written the editorials and uploaded them on codeforces too, apart from codechef as the forum here is more active :)

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

I am the leader of team "BlundersPride" who have set the second contest of the series. There are some nice problems which you might enjoy. A lot of effort has been put to prepare the contest and editorials.

Some trivia: the team name is derived from this certain brand of Indian whisky! img

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

Any possibility the contest could be moved to avoid collision with COCI#3? COCI has been scheduled for that time slot for a long time now.

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

    Oh, we didn't know this when making the schedule, else we would have definitely tried to avoid the clash. Now, we think it's too late to shift the contest to another day, and shifting it by 1 hour or more will be too late in the night for Indian participants.

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

So, contest has been on for around 4 hours. The problems are a little tougher than we had expected them to be. One problem is still unsolved.

Team FacelessMen and sokian and Team ptnk1316 have solved 6 each.

Team zenith_vn(ngfam_kongu, I_love_Hoang_Yen) and Team aimfund(zeliboba, yarrr, ValenKof) have solved 5 each.

Contest has been extended due to a jury mistake in a problem. It is open till 3:00AM IST.

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

What is the solution of problem KingTour?

The best I could think of was a matrix exponentiation solution with each matrix of dimension 400*400. Other people seem to have used a solution where the matrix was 100*100.

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

    You don't need all 400 states. Since the field is symmetrical, instead of saying we are i cells from the right border, we can say we are m — 1 — i cells from the left border (0-based).

    So you can do i' = min(i, m — 1 — i), j' = min(j, m — 1 — j), which brings the size of the matrix down to 100. You can also swap i' and j' if i' < j'. The size will be <= 55 then.

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

    KingTour can be solved easily by using this awesome trick explained by misof. :)

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

How to solve "counting zigzag sequence" and "queries with pairs"? BTW, the problems were really great , thanks for that :)

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

    The editorial for Queries with Pairs is available: Editorial.

    For Counting Zigzag Sequences, you can maintain a Hashmap with  < val, state >  as keys, corresponding to last element of the sequence (and the count of all such sequences as the value for that key). States can be 0,-1 or 1 0→ odd element , 1→ even element (x+1) , -1 → even element(x-1).
    You can update the Hashmap while traversing the array. The complexity of this solution would be O(NlogN)

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

      Thanks for your reply . Sorry, i couldn't understand your approach for "Counting Zigzag Sequences" completely . Can, you please explain the state transitions in a little more detail :)

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

        Have a look at this solution, coded by zenith_vn. It's neat and concise and you can understand the transitions easily. We'll be uploading the editorials today as well. Solution

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

I've solved three problems already, but now when I'm trying to submit next one — I am receiving "You are not allowed to take part in this contest. You may need to contact the contest admin to give your permissions." message. Something went wrong?..

Upd. Seems to be working fine now :)

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

That awkward moment when you can either solve a problem or simply submit some naive solution in Java and get AC — I'm really curious about motivation behind setting TL to 6 seconds for this problem (with Java and that strange non-ICPC multipliers for bad languages rule it becomes 12 seconds).

Also I like these formally correct constraints, MOD<=100000 — when it is even <=10000 in fact :)

Now I am waiting too see editorial for PSEQ, in order to know — is it fine that exhaustive search without any prunings and breaks runs in 0.2. I was a bit surprised :) I have no idea about its complexity, but it sounds risky.

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

    "multipliers for bad languages" :( feelings have been hurt

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

    I was the author of the problem PSEQ. The expected solution had a time complexity of around 3^7*600 . Exhaustive search was supposed to TLE but sadly it passed. Regarding the TL set in MODQ we had tested for bruteforce solutions in C++ and it was TLE'ing but had no idea that with Java even a bruteforce solution would pass .

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

      Using the fact that number can't have more than one prime divisor larger than and running dp where state is described by mask of primes up to 17? Thanks for a nice problem :) Sadly, most of teams used different approaches.

      Moreover, some solutions are using straightforward greedy heuristic, which is obviously wrong.

      A test:

      1
6
6 6 10 10 15 15

      Answer for it is 3, not 2 :)

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

        Yes that was the intended solution . Unfortunately i could not take into account all the greedy approaches :( and set appropriate input . I however hope that you liked the problemset :). Is there any input for which the bruteforce solution will TLE ? If yes how to generate one ?

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

          It depends on bruteforce you are using :)

          I have no idea how easy to crack smart solutions are; however, I submitted most naive one, which doesn't stop searching even after finding perfect solution. As a result, for test consisting of two copies of every product of two primes below 150 I got

          10
--------------------------------
Process exited after 538.5 seconds with return value 0
Press any key to continue . . .

          I'll not even try to wait while it will compute answer for worst possible case — for my solution it is simply set of all numbers which have more than 1 prime in factorization.

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

            There were cases where i had used all the numbers from 2 to 300 twice. But all bruteforce solutions solved it within 1s.

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

              Naive optimization: whenever you see a number which has only 1 prime divisor, you can take it safely (unlike more general "sort them by number of primes and pick greedily", this one should be fine — because removing this number from your answer may give you space for no more than 1 other number).

              I used it, so for your test my solution picked all primes in range 2..300 first of all, and then had nothing more to do :) But if you'll remove primes (and their squares, cubes, ...) — it will make things much worse for this particular implementation.

              Once again, such straightforward tests are still easy for bruteforces with at least basic optimizations, and it feels like well-optimized bruteforces may work fast on all possible cases, but I have no idea how true it is.

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

      Bruteforce(with slight precomputations) passes even in C++ for MODQ....

      Solution

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

I am curious why the constraints of good rectangle were set to 1<=n,m<=1e5 and then have no case with n=1e5,m=1e5,k=1.

The answer for that case will exceed 64 bit integers and should have been put in the test cases. Our solution used long doubles and was giving some small error for that case and solutions printing (ll)round(ans) will also give wrong answer.

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

String swap 2 was a copy of a problem C in cf round 276

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

In Grid Game how to check whether the xor of x, x+2, ..., x+2m-2 is 0 or not .

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

    If x is odd, then each number above has last bit 1, so their XOR will have last bit 0 or 1 depending on m. If x is even, then each one of them is even so, last bit of their XOR will be 0.

    Now, write them like y, y + 1, ..., y + m - 1, where (integer division). Now, this is a contiguous range of numbers. Can you find xor of numbers 1, 2, ...N in .

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

      How to calculate xor in O(log N) . Sorry, i'm unaware of the concept :(

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

        You can count parity of 1's at any place/position easily. One straightforward idea is to use digit dp. I think there might be observation based recursive kind of solutions too.

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

when will the editorials be published of 2nd and 3rd contest ??

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

    For the second contest, 6 out of the 9 editorials are done and you can find 4 (other two will be available by morning) of them here. The other three will be available very soon.

    → Reply