ALGORITHMIST codechef contest

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

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

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

algorithmists, deleted

Wild_Hamster
7 лет назад
30

Комментарии (28)

Показать архивные | Написать комментарий?

Vicennial

7 лет назад, # |

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)

→ Ответить

Wild_Hamster

7 лет назад, # ^ |

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.

→ Ответить

percywtc

7 лет назад, # ^ |

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

→ Ответить

Wild_Hamster

7 лет назад, # ^ |

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;
}

→ Ответить

nuip

7 лет назад, # ^ |

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

→ Ответить

Vicennial

7 лет назад, # ^ |

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

→ Ответить

percywtc

7 лет назад, # ^ |

+17

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

→ Ответить

Errichto

7 лет назад, # ^ |

+36

Wrong usage of meme.

→ Ответить

satyaki3794

7 лет назад, # |

+11

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

→ Ответить

percywtc

7 лет назад, # ^ |

+51

And here it comes... :D (I knew it, rohit_0809)

P.S. Not the newest version, sorry.

→ Ответить

torquecode

7 лет назад, # |

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.

→ Ответить

Wild_Hamster

7 лет назад, # ^ |

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

Spoiler

while (cin >> n)
    {
        f.clear(); // f is map
        for (i = 0; i < n; i++)
            cin >> a[i];
        for (i = 0; i < n; i++)
        {
            pref[i] = f[a[i]];
            f[a[i]]++;
        }
        f.clear();
        for (i = n-1; i >= 0; i--)
        {
            suf[i] = f[a[i]];
            f[a[i]]++;
        }
        ans = 0;
        for (i = 0; i < n; i++)
            for (j = i+1; j < n; j++)
            {
                if (pref[i] > suf[j])
                    ans++;
            }
        cout << ans << endl;
    }

The part of code with O(n²) 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].

→ Ответить

torquecode

7 лет назад, # ^ |

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

→ Ответить

Wild_Hamster

7 лет назад, # ^ |

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.

→ Ответить

masterwayne

7 лет назад, # ^ |

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.

→ Ответить

chintu

7 лет назад, # |

← Rev. 2 →

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

→ Ответить

Wild_Hamster

7 лет назад, # |

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

→ Ответить

torquecode

7 лет назад, # ^ |

Here

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

→ Ответить

Wild_Hamster

7 лет назад, # ^ |

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

→ Ответить

percywtc

7 лет назад, # ^ |

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

→ Ответить

Vicennial

7 лет назад, # ^ |

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

→ Ответить

BuilderBob

7 лет назад, # |

-6

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

→ Ответить

percywtc

7 лет назад, # |

+19

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

→ Ответить

Vicennial

7 лет назад, # ^ |

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

→ Ответить

percywtc

7 лет назад, # ^ |

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

→ Ответить

renesmee

7 лет назад, # ^ |

+11

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

→ Ответить

rohit_0809

7 лет назад, # ^ |

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

→ Ответить

Errichto

7 лет назад, # ^ |

+38

Write a validator for each problem. Always.
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.

→ Ответить