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

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

Topcoder SRM 706

Time: 11:00 am EST Saturday, January 21, 2017

Calendar: https://www.topcoder.com/community/events/

Update: Sorry but the link to the time was wrong, please click again and see local time in your timezone.

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

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

Auto comment: topic has been updated by cgy4ever (previous revision, new revision, compare).

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

Update: we added one more SRM on Jan 11th and moved the SRM on 14th to 21st.

So we will have 3 SRMs in January! See details: 705, 706, 707

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

This SRM conflicts for 35 minutes with the Facebook Hacker Cup Round 2 on the same date. Given that Round 2 is only 3 hours long this 35 minute overlap is fairly significant, and given that Facebook announced their time first, I think there should be some consideration given towards moving this SRM round in my opinion.

Edit: For reference here is the link to the time of the Facebook Hacker Cup Round 2, as we can see it starts just 1 hour after the Topcoder round begins.

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

    Ok, we moved it to 1 hour earlier, so you can see the system test result of this SRM before Facebook Hacker Cup.

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

Auto comment: topic has been updated by cgy4ever (previous revision, new revision, compare).

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

cgy4ever is this time correct for SRM 706?

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

Finally, you did it! The contest will be on weekend and I can participate! What a pleasure =)

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

Auto comment: topic has been updated by cgy4ever (previous revision, new revision, compare).

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

Can someone login to arena.topcoder.com?

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

Anyone using KawigiEdit on the Topcoder Arena?

I get an alert saying java.lang.Exception: actGenerateCode is currently disabled. Used to work fine before. Has any one else experienced this error from KawigiEdit?

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

Does it possible to open code editor in web arena in fullscreen? Challenge someone while reading only 11 lines of code at a time isn't comfortable.

Also I noticed that code from the web arena can be copied without any effort. I don't think that code extraction during challenge phase comply with topcoder rules :)

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

    I couldn't copy code within the Java applet as well. I don't know if that's a bug or a feature :(

    However I was able to copy-cut-paste using KawigiEdit.

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

How to solve Div 2 1000 ? Thanks in advance.

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

How was Div2 1000 supposed to be solved?

My initial idea how was to sorta map the given integers to new integers —

for example: 5 2 5 4 -> 1 2 1 3

and then find no. of increasing subsequences of length 3. However this seems to not consider several subsequences that may be allowed.

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

I am getting redirected from Topcoder Web Arena indefinitely. How do I fix this?

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

    This issue has been there for over a month. I don't even know where to report it.

    Either clear your browser cache or log in from incognito.

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

      They don't think they have a problem:

      Hi Egor,

      We've not been able to replicate on our side nor have we received any other complaints so I would like to make sure we're going about it the same way. Can you please send me a short video of the issue when you get a chance?

      Thank you, Valerie

      Can all of you, people, report the problem so that they start thinking that this is a serious issue?

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

div2 codes: http://ideone.com/CSvHOR
short description for every solution:

ThreeIncreasing (div2-easy)
SellingFruits (div2-med)
MappingABC2 (div2-hard)

div1 codes: MovingCandies, MappingABC, CoprimeNeighbors
short description for every solution:

MovingCandies (div1-easy)
MappingABC (div1-med)
CoprimeNeighbors (div1-hard)
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    hello Errichto can u describe problem-> MappingABC2 (div2-hard) more clearly . i did not understand your solution .

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      1. Do you understand the meaning of the "three indices" in my solution?
      2. For a moment forget about the initial sequence with numbers. Do you know how to e.g. count strings of length 10 with letters A, B, C, so that those three indices will be at positions 2, 5 and 7?
      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        i didn't understand meaning of three indices and also example given in 2nd comment. total strings will be -> 3 * 1 * 3 * 3 * 1 * 3 * 1 * 3 * 3 * 3 = 2187 may be....

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

          It should be 2 * 1 * 2 * 2 * 1 * 2 * 1 * 3 * 3 * 3. (EDIT: small typo)

          Do you know how to check if one string is a subsequence of the other? For each letter in a shorter string we should greedily choose the closest possible matching letter in a longer string. The "three indices" are indices of letters matched in a longer string (assuming that a shorter string was "ABC").

          For a string BCCBACABABCABCC the three indices would be at positions marked bold: BCCB A CA B AABBA C ABCC

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

            ok i got it . in given example BCCBACABABCABCC first occurrence of shorter string "ABC" at position BCCB A CA B AABBA C ABCC. but above if we want to count 10 length strings where restrictions that at position 2 -> "A", at position 5 -> "B" and position 7 -> "3" than these position contain 1 but remaining position can contain any three characters ( A, B, C) so all remaining position contain 3.

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

              If we say that the first 'A' is at position 2, the very first can be only 'B' or 'C'. Similar thing happens later: we say that the first 'B' after first 'A' is at position 5.

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

                u want to say that at 2nd position -> 'A' and after it first 'B' will be at 5th position so between 2 and 5 there will be only two character possible which are -> A or C so we uesd ..... 1 * 2 * 2 * 1 ....

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

                  yes

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

                  ok i got it.i understood meaning of indices. can you explain last concept which is , how can i transformed given numbers in letter (A, B, C)

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

                  It's described in my first comment. After fixing the three indices we know for which position what letter(s) can't be there and thus we know for every number (value) what letters it can't be transformed into. We should multiply numbers of allowed letters for all appearing numbers.

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

                  okk i got it completely . thank you ... thank a lot .. can i ask one more question , which type of technique or algorithm use for this type of problem. how can i think mathematically for this type of problems...

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

                  I don't how to call this technique. Don't care about it, just solve problems.

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

Here is a very similar problem to Hard: http://artofproblemsolving.com/community/c6h627236p3763526 about existence of such an infinite sequence. However unfortunately its solution doesn't help in any way to today's problem (even though it exists, but all given examples grow exponentionally). I used a pretty simple approach (I was relieved it worked because it was by far not obvious that it will produce an answer). My elements will correspond to subsets with 9 elements out of 19 elements set (then I will multiply some primes to get actual numbers). I implicilty create edges between all pairs of subsets that their intersection is empty and I use a backtrack to find an induced path of 500 vertices. Fortunately, works very fast :).

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

Never mind, Invalid testcase!

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

I wondered why div2 easy was so hard and didn't realize I was in div1 during contest ...