Блог пользователя Wild_Hamster

ALGORITHMIST codechef contest
Автор Wild_Hamster, история, 8 лет назад, По-английски

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

  • Проголосовать: нравится
  • +53
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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)

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

      → Ответить
      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        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;
}
        → Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
»
8 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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].

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

      → Ответить
      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        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.

        → Ответить
      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        → Ответить
»
8 лет назад, # |
← Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

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

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

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

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

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

      → Ответить
      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +11 Проголосовать: не нравится

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

        → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +50 Проголосовать: не нравится

      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.

      → Ответить
      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +38 Проголосовать: не нравится
        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.
        → Ответить