darkshadows's blog

Invitation to the September Mega Cook-off 2014 on CodeChef
By darkshadows, 10 years ago, In English

CodeChef invites you to participate in the September Mega Cook-off 2014 at http://www.codechef.com/COOK50. This is the Mega Warm-up Contest for ACM ICPC Regionals (India). The top 100 Indian Students shall have their ACM-ICPC expenses reimbursed. Find the details here.



Time: 21st September 2014 (2130 hrs) to 22nd September 2014 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

Details: http://www.codechef.com/COOK50/

Registration: Just need to have a CodeChef user id to participate.

New users please register here

- Problem Setter : Lalit Kundu
- Problem Tester: Tasnim Imran Sunny
- Russian Translator : Sergey Kulik
- Editorialist: Devendra Agarwal
- Mandarin Translator: Gedi Zheng & Minako Kojima

It promises to deliver on an interesting set of algorithmic problems with something for all.
The contest is open for all and those, who are interested, are requested to have a CodeChef userid, in order to participate.

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

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

"The top 100 Indian Students" : Suppose I get a rank of 101 among Indians and some people among the top 100 Indians are not university students then would I be considered among the "The top 100 Indian Students" ?

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

Contest starting soon, let's brace ourselves for 404s :D

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

Quite nice problem, I think the hardest problem is a bit easy, but it is still interesting. Some students from my school successfully persuaded me to participate in such a Sunday midnight =)

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

How was SUBLCM supposed to be solved?

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

    There is a n * log(n) solution.

    1. A subarray from i to j is considered valid if non of two elements from it share the same prime divisor. In other words every two elements of the subarray are co-prime.

    2. Notice that a[i] <= 10^6. So we can easily get all the prime divisors for each 1 <= x <= 10^6. This can be done in n * log(n). Then we can use these precalculated arrays of divisors.

    3. We have two pointers identifying the borders of subarray candidate. We also have a set of all prime divisors of the elements in current subarray.

    4. We move right border. If all the prime divisors of the right-most element are absent in the set then new subarray is valid, add all new prime divisors to the set. If the set has any of prime divisors of the right-most element, then we move left border excluding prime divisors of the left-most element from the set. We move the left border until we eventually can add the right-most element.

    5. Each time the right-most elements is added we receive a valid subarray. Its length is answer candidate.

    Here is my code for this solution.

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

Hmm, I'm getting TLE in the hardest problem. The funny thing is, it runs in 3 seconds on the maximum random case and its runtime is pretty much fixed at O(20·(N + M)), so it probably fails because of the testing machine being slower than mine...

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

    My solution is also O(20 * (N + M)), but all the constant 20 comes from finding LCA of two nodes, the rest are finished in O(1).

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

      I've got more LCAs, but I don't like it when a problem's hard only because of constant-tight TL and (probably) slow testing machines.

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

        I was calculating 6 LCA's per query, cout'ing with "endl" instead of "\n" and doing lot of other unnecessary stuff, and it passed with time 33.89:)

        BTW, you said that you like CodeChef long contests for opportunity to fit into TL even with asymptotically bad solution, didn't you?:) What an irony:)

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

          Hehe, all Codechef contests seem to favour asymptotically bad solutions over good ones. Here, my solution got the best time in-contest, while it was definitely supposed to not pass at all.

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

            Yeah, and once i got 2 WA's, submitting unproven solution at some contest while saying to myself: "this one passed once before at same problem at CodeChef, it should be OK" :)

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

    You definitely have some bug, because current codechef testing machine are able to do about 2*10^8 operations per second.

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

      When just the input has 4 million numbers, it doesn't seem like much.

      UPD: Also, got AC now. I've got no bug, the testing machines are just slow — I know it because one of my codes in practice that TLEd was made with only straightforward for-cycles without breaks (so it had pretty much fixed runtime) and took 2 seconds to run on random case on my machine.

      Then again, it's not like I didn't consider SPOJ the worst choice for testing because of its speed even before this.

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

        scanf in my solution did well. I hope you don't use cin :) You can also try implementing your own nextInt() by getchar(). This trick was damned popular when they used Pyramid testing machine.

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

          Scanf isn't faster than optimized cin, it seems (I tried both and tested both on my machine). The difference is quite small, but using scanf didn't help me.

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

Test cases for SUBGCD are very weak. This solution passed — but it fails on following test:

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

    oops! apparently the easiest problem wasn't tested much :/ btw, considering that this was my first cook off as setter, i feel nice that it went good(even though problems were on a easier side).

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

Did anybody manage to solve WW2 without matrix exponentiation?

→ Reply