Wild_Hamster's blog

ALGORITHMIST codechef contest
By Wild_Hamster, history, 8 years ago, In English

Since the last blog about codechef Algorithmist was deleted, we can discuss it here.

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

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

I've tried local variables,global variables,cin/cout,scanf/printf and still assert(n>0); fails everytime.
How are people getting AC? (I'm pretty sure there is no problem with assert function since assert(n<=100) does not give RTE)

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

    do you know, what did I try?

    getline(cin, s);
while (getline(cin,s))
{
  getline(cin, s);
  array p = parse_into_array(s); //it's pseudocode
}

    I assumed, that t and n are incorrect, but at least they are placed in right lines. But when I asserted (s.size() <= 2) for odd lines(where should be n), it failed.

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

      Me and Bedge were just guessing the number of cases in the input is not same as the value of t. But seems like it is more than that OMG

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

        I know, how they generated the testcases.

        cout << 1000 << endl;
for (int i = 0; i < 10000; i++)
{
 cout << rand()%36-15 << " ";
 if (rand()%10 == 0)
  cout << endl;
}
        → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Output 0 for n<=0. (I don't know why, but it pass all test)

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

      I hope they rejudge all the solutions after correcting the errors.
      rohit_0809 and renesmee, please do so.

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

        When they said:

        All test cases are fine.

        And after a long explanation...

        All test cases are correct...

        And they suggested us...

        kindly remove the assert(n >= 0) that causing runtime

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

Should have taken screenshots of the comments on the previous one before it got deleted. :D

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

How did you solved LUCKY PAIRS ? I solved it with storing vectors in a each segment tree node and then binary searching the values less than for any x, but I think there is some simpler approach because it got so fast submissions.

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

    I didn't solve it and I can't submit it, but here is part of code:

    Spoiler

    The part of code with O(n2) can be simply done with segtree. We need to answer for each i = 0... n - 1, how many numbers in pref[0, i - 1] are greater, than suf[i].

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

      I did this too. I did that segtree stuff by storing vectors for each node and then sorting and binary search on them. I am just wondering if there is simpler version of that segtree.

      My solution

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

        Why do you need so hard segtree? We need only 2 operations on segtree:

        for i in 0... n - 1:

        • Answer += sum on the segment arr[suf[i] + 1, n]
        • increment arr[pref[i]]

        Even fenwick tree will fit fine there.

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

        Suffixing the original array based on the length of q points which you can perform and just build a segment tree or Fenwick tree.

        Now start with prefixed and start updating the segment tree with new length which will be left if we remove ith element from some suffix.

        Suppose you had 2 2 2 2 initially, Now when you remove 2nd 2 from beginning you would have reduced a 3 size suffix to 2 this you need to update same in segment tree by decrementing number of suffixes of size 3 by 1.

        Hope it helps.

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

These things happen when problem setters blindly copy paste everything like course assignments.

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

So can somebody give AC solution for the task with "fine testcases"?

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

    Here

    I don't know what the issue was because mine passed in a single run.

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

      ok, I got it, for negative n it outputs 0. My code was outputting the answer from last adequate queue.

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

    You are talking about problem A — Chaos Is A Ladder?

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

    Expand the "Successful Submissions" bar on the right. link

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

I solved A without memoising my dp then too it passed alongwith the case n<0 :P

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

Surprised, it seems that the data was updated and submissions of problem A were rejudged.

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

    Yeah, it seems they did. Kudos to them for not ignoring the problem.
    Also congrats for first place!

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

      Thanks, now I am curious about the distribution of prizes haha.

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

        I too apologize for the inconvenience caused..we'l make sure this does not occur ever again...and congratulations to the top performers !

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

      Thanks bro for showing kindness!! First of all heartiest Congratulations for all top performers.Secondly,I am very very sorry for whatever happened yesterday.Because of solutions getting accepted and our tester was bit over confident about his test file, i was ignoring the matter. But, at the last moment (nearly 30 minutes were left towards the end of contest), we came to realize that there was serious glitch in test file.I was seriously dumbstruck at that moment.It was very much depressing and unexpected for me.I deeply apologize to all the coders who suffered because of me.Being the organizer, i know i am the culprit.Please please forgive me for this blunder.I know, i wasted your precious time and being a coder, i can understand how it feels.Your anger is totally acceptable for me.I am extremely sorry and, i will ensure that it never happen in future.
      Just to minimize our fault, we have rejudged all the solutions of ALGOA. Rank-list has been updated.Prize distributions will be announced soon on our Facebook page.Again, i will say, i deeply regret for all the inconvenience caused.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +38 Vote: I do not like it
        1. Write a validator for each problem. Always.
        2. Check your tests again if participants ask you. The fact that some people get AC's doesn't mean a lot — maybe they are lucky and handle invalid inputs the same way you do, and maybe outputs are invalid but they made the same mistake as in the intended solution.
        → Reply