darkshadows's blog

CodeCraft IIIT Hyderabad(Programming Contest)
By darkshadows, 10 years ago, In English

Hi,

I am happy to extend you to the invitation to participate in annual programming contest of IIIT Hyderabad. It's an ACM style programming contest, except that it's for individuals and not teams.

You will have a chance to devour some really nice(hopefully!) problems. I think considering the wide difficulty levels in problems everyone will find some interesting/challenging problems to solve.

It begins on 25th Jan, 2015 at 1400 IST.
To see time in other time zones: http://bit.ly/1u8sdBI
Visit http://felicity.iiit.ac.in/threads/codecraft/#content for rules.
Register here: http://felicity.iiit.ac.in/register/
Join facebook event page here for further notifications: https://www.facebook.com/events/378291325683458
Also, there will be some attractive prizes for winners(to be announced soon).

By the way, here's the leaderboard for last years contest:

Happy Coding!

Contributors(setters and testers):
1nikhil9 aka_007 alok123t ashu1461 darkshadows darkscale karanaggarwal pulkitg10 sak_agg sherlock_holms tanmaysahay94 Baba thunderking viv001

UPD1: Prizes worth 20,000 INR to be won.
UPD2: Here is the contest link: http://felicity.iiit.ac.in/codecraft/public/
UPD3:
Like all good things, this one must come to an end as well. Yet another successful CodeCraft comes to an end.
With 2982 submissions, this was one of the most prolific editions of CodeCraft!
tourist wins CodeCraft '15 with 10 correct solutions.
anta comes a close 2nd, also with 10 accepted solutions.
natsugiri comes 3rd with 9 submissions.
Here's the link to the scoreboard:

Just like last year, 1 problem went unsolved. But, we'll be accepting solutions for the next 48 hours, in case you want to try out the problems at your pace.
Editorials will be released in a day or two.
Hope you enjoyed the event. See you next year!

UPD: Here are the detailed editorials by jury: http://codeforces.net/blog/entry/16099
For practice use gym: http://codeforces.net/gym/100589

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

Comments Comments (48)
| Write comment?
»
10 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Your website for event is awesome , specially soundtrack

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

Gender: Male — Female — Other There's no Other gender o.O

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

    Look up hermaphroditism. There are other cases too which might fall under the category "other".

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

      You seem to be pretty knowledgeable about this matter.

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

The website is really good. However, how can one view his contest/submission history? The username appears un-clickable at the moment.

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

A gentle reminder! Contest begins soon.

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

Link for the contest? Where to find it?

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

Where's the contest link.?

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

How i can submit my code -_- ?

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

    Hi, You have to go to Overview section. Its the standard dom format.

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

What a Java-friendly contest.

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

How to solve qutree? Was it possible to get AC with O(m^2) solution?

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

    I guess they set m <= 10^4 just because the answer is bounded by 10^18 in this case.

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

    Sqrt Decompostion on euler tour

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

    I solved it with O(m^2 lg).

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

    Jury solution was O(n sqrtm logn). Using sqrt decomposition of queries(updating the whole tree when queries exceed sqrt m).

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

      The same can be done in O(n * sqrt(n)) in offline mode.

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

where can we find the editorial for the contest???

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

How to solve DSET?

IMHO:

1) for every i: si is a segment from left position to right position

2) only adjacent si can be equal

I have a solution with binary search, but it's O(Answer * log3(n)) for every query. It's too slow. it's smth like this


long long i = 0;
while (i < n) {
   long long r = binsearch(from = i, to = n - 1);
   ++ans;
   i = r + 1;
}
// binsearch(from = i, to = n - 1) - binary search that finds the right most position r: s(r) == s(i)
// s(i) - function that find's left and right positions where number i can be placed, it's a binary search on left position, where size of "subtree" of this position is calculated so it's O(log^2(n)), right position can be find in O(log(n)) because it's only need number of "ancestors" of position.

How to solve it faster?

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

    Solution with complexity O(log(N)) exist. Editorials will be posted soon. Till then the judges is on for up solving, although the contest leader board is different.

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

where can I try to submit my solution to the problems ??

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

How did you guys solve CWAYS? I failed so hard on that problem. TT

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

    Number of safe paths from (1, 1) to (n, m) is equal to (all paths from(1, 1) to (n, m) (which is binomial)) minus sum_over_all_i(good path from (1, 1) to (x[i], y[i]) and then any path from (x[i], y[i]) to (n, m)). So we need to count the same, but for smaller rectangles. Looks pretty messy but hope it makes sense.

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

      Ohhh that makes sense. Thanks a lot!

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

      I got TLE for that with fast expo and memoization. How do you optimize?

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

        I can share my code if you give me a hint about how to pull my solution out of the website :)

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

        Maybe you can precompute the inverses of all the factorials (1!-200000!) first, so you can evaluate C(n,r) faster.

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

          Wouldn't that take O(nlogn) time and that would be the same as computing the inverse online won't it?

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

            Use fact invFact[n] = (n+1) * invFact[n+1] % p. Just calculate invFact for 200000 in logn time then use above fact to calculate every other value in O(1). This will take O(n) overall.

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

              Oh wow I didn't know such a property existed :D Awesome! Can you give me a link to the proof of this property?

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

                This can be easily seen

                invFact[n+1] = 1 / (1*2*3....(n+1)) % p
invFact[n+1] = inv(1) * inv(2) ...inv(n) * inv(n+1) % p

                invFact[n] = 1 / (1*2*3...n) % p;
invFact[n] = inv(1) * inv(2) ...inv(n) % p
or
invFact[n+1] = invFact[n] * inv(n+1) % p
invFact[n+1] * (n+1) % p = invFact[n] % p

                Here inv(i) is (1 / i) % p

                p > n and prime

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

                  Great!! That was really helpful, thanks a lot! :D

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

Problem — Laughing Out Loud

Problem Link

I calculated for every O in the string number of L left to it and right. and add product of this to the final result .
My code
It gives correct answer on sample cases but did not pass the submission in contest.
Does my approach is wrong or there is some other way to calculate it

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

    You should cast ints to long long because it might overload. As I remember, size of s can be 1O^6; therefore, In an example like LLLLLL...OLLLLLLL..., it would overload. Instead of casting, you can also use vectors of long longs, which is generally faster, but it uses more memory.

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

Some of the past problems in codecraft: 2011 in Spoj: http://apps.topcoder.com/forums/?module=Thread&threadID=698512&start=0 2013 in Spoj: http://apps.topcoder.com/forums/?module=Thread&threadID=779918&start=0&mc=5 2014 in CodeChef: http://www.codechef.com/CDCRFT14

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

For all thode who could not give the contest, it has been added to the GYM section and will start in a few minutes. http://codeforces.net/gym/100589

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

    Looks like tests for Desolation of Smaug are incorrect :( Can someone discuss it with me in private?

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

Here are the detailed editorials by jury: http://codeforces.net/blog/entry/16099

→ Reply