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

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

Hello Codeforces Community!

CodeChef invites you to participate in CodeChef August Cook-Off at http://www.codechef.com/COOK61.

Time: 23rd August 2015 (2130 hrs) to 24th August 2015 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

Details: https://www.codechef.com/COOK61

Registration: Just need to have a CodeChef handle to participate. For all those, who are interested, are requested to register in order to participate.

Prizes:

  • Top 10 performers in Global and Indian category will win a cool CodeChef T-shirt.

  • Top 50 Indian performers will be provide with a reimbursement (for travel and registration) of upto INR 1500 for ACM ICPC 2015 regionals.

It promises to deliver on an interesting set of algorithmic problems with something for all.

Good Luck! Hope to see you participating!!

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

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

Please note that as a part of Directi's GoforGold initiative, 150 students will be provided with a reimbursement (for travel, registration etc) of upto INR 1500 for ACM-ICPC regionals.The reimbursement is provided based on the performance of the students in the below mentioned contests (top 50 performers in each of the contests will be provided with the reimbursement*). For any queries related to this initiative, feel free to get in touch with the team at [email protected].

Please make sure to avail this initiative too :)

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

Gentle Reminder! Contest begins in around 2 hours. Also, as the editorialist, I'd like to say I personally found the problems really interesting. I am sure anyone participating will enjoy the contest. :)

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

How to register

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

    You mean register on website? There is no specific registration required for the contest. You can start solving after loggin in.

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

I think, may be this is the first problem we are going to see : Error 502/503/504 :D

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

I can only see a blank page.

UPD: it's better now (note: "better" doesn't mean good, just "it does load after a lot of labour pains").

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +34 Проголосовать: не нравится

to admin :

next time copy question and paste in pastebin 1 min beefore contest

then post link here :P

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +34 Проголосовать: не нравится

IT'S SOOOO SLOW!

»
9 лет назад, # |
Rev. 4   Проголосовать: нравится +28 Проголосовать: не нравится

The problems are great,

The only problem is that i cannot see them

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +27 Проголосовать: не нравится

codechef_sucks :(

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

The worst part is that I can't just wait for the page to start working, I have to press f5 every 1-2 minutes. Please at least autorefresh. What year is it?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится -10 Проголосовать: не нравится

    I think main issue is the number of requests are more than server can handle right now. Auto-refresh will escalate the issue in my opinion.

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

      If server cannot handle so many participants, you should just limit registration. At least then participants will have a decent time solving the problems instead of everyone having a bad time not being able to see the problems or submit.

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

      a humble request to not let the same thing happen for icpc-online tests

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

the worst part i coded up a solution and was not able to submit for the next 15 minutes as the submission page wouldn't open :(

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

I would to thank the Codechef's team to help me learn HTTP status codes like 1. HTTP 500 : Internal Server Error 2 .HTTP 502: Bad Gateway 3. HTTP 503: Service Unavailable 4. HTTP 504: Gateway Timeout Thank you seriously :)

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

24/08/2015, 2353 hrs IST : The site is up and working. We have extended the contest further by 20 mins. The contest will now end at 0050 hrs IST. We truly regret the inconvenience.

Note: The rankings page will be accessible only after the contest will end. We have taken it down as of now.

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

Nice tests for Chef and the Number Sequence — my full search solution works 9 seconds in CF custom invocation and still gets AC; I see another AC solution working 15 seconds at CF (it takes over 6 seconds to solve 4 queries) and passing at CodeChef.

Or maybe that's all about fast servers at CodeChef :)

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    What do you mean by full search?

    About the "fast servers" comment: my solution takes 3.8 on Codechef, 6 on Codeforces for bad input, 3.3 on Codeforces for random input.

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

      OK, not exactly full search, sorry for this misleading statement:)

      I implemented DFS which tries all possible sequences and classify them by endpoints of LCS of size 1, 2, 3, ..., 16. Here is it — link.

      It is going to work slow when permutation is given in input and asked length of LCS is around n/2.

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

        That's not really full search though... You do your memoization with some strange hashing (wat?), but it's basically the same idea as the expected n^2*k*2^n solution (2^n since the endpoints are strictly increasing), right?

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

          Seems so... I wasn't thinking about it during contest — first I switched to the next problem and later I had to leave it at all (didn't plan such a long contest :) ), now I've read editorial and a few codes — looks like you are right, this solution isn't so bad :)

          The reason behind hashing is the fact that I missed part about "strictly increasing" while working on solution. Now I see that all hashing can be made using DP table. Thanks for making it clear :)

»
9 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится
»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

My page were loading and loading , and finally i found a page loaded THE CONTEST HAS ENDED :P :P

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

I was struggling with the cards problem. Some ideas:

  • we can partition all cards into chains like (a,b),(b,c),...,(x,a);
  • chains of length 1 can be combined into a single contiguos sequence (initialize answer), otherwise are useless;
  • we can combine chains of length >= 2 by some rules; the rules are a bit tricky and I am not sure I got them correctly;
  • then we can iteratively expand set of reachable chain lengths and update answer correspondingly;

Is it right direction?

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

    Yep

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      According to the editorial, we iterate over all m (from 2 to n) and try to break each cycle into chains of length m or m+1, and take max value among all such m. Why? I understand that only chains with difference in length <= 1 can be combined but what use is it to break all chains into the similar length? Does it ensure that all of them can be combined?

      I think this is explained in these lines "First, we place all chains of length m+1 and then all chains of length m and now if we build our answer by putting elements from each chain one by one, this criteria will always be satisfied(Can you prove it?)." in the editorial but it was not clear to me.

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

You can access editorials for the first 4 problems here: https://discuss.codechef.com/tags/cook61/

For 5th problem, I am still not clear with the approach. So, I think by today I should be ready with a draft of editorial.

»
9 лет назад, # |
Rev. 3   Проголосовать: нравится +13 Проголосовать: не нравится

"with something for all." Codeforces analogy of what they did is making a combined division contest with div2A,div2B,div1C,div1D,div1E (seriously, it's even worse, number of solvers = {2800,1600,13,10,0}). If they would just change the first 2 to div1 A and B it would fix 2 problems at once: 1) combined with Fear_Is_An_Illusion's idea of moving problem statements elsewhere the server would get like 10 times less requests and 2) would provide more than 0 interesting problems for most purple and yellow coders. EDIT: By interesting I mean having a reasonable chance to solve during the contests without being very easy. Solving very hard problems after contest is still interesting.

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

    According to announcement, top50 Indian performers will be provided with a reimbursement for ACM ICPC regionals. I see 3 people with Indian flag (are all 3 of them eligible & going to participate in regionals?) among those who solved 3 or more problems. For other 47 slots it turns into "who can solve A+B faster?" where single wrong answer leaves you basically without a chance. It doesn't sound cool at all. I am curious — setters were expecting such distribution and roulette for getting announced prize, or they simply overestimated level of Indian contestants so much?

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

      We were expecting that SEQLCS will be solved by slightly more people.

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

      Hehe, I was whining about it to all my friends because I got a WA in B and got kicked to rank 77 or something :P

      Interestingly, inn that problem, I noticed that n = 1 is a corner case but then I did if(n == 1) puts("-1"); like an idiot XD

      And yeah, they definitely overestimated Indians' level. Recontest pls?

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

While the last three problems were really interesting, the difference in difficulty between the first two and last three is too much.

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

>fail.jpg

So... I suppose this contest should be unrated. And the reimbursement doesn't seem very fair either.

As for me, I did the contest while travelling and only had battery for slightly more than 2.5 hours, so any time extensions didn't matter. The problems seemed pretty good, although a bit overly hard (the idea of what to bitset in SEQLCS really isn't very clear at first) — but better to have too hard problems than too easy ones.

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

Sorry, for asking a dumb question, but how to submit problems after contest? I'm trying to submit a solution here https://www.codechef.com/submit/CARDLINE. All what I can see, after submitting a solution is the following message: "Wrong login or password!".