When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

cgy4ever's blog

By cgy4ever, history, 7 years ago, In English

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.

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

| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 years ago, # |
Rev. 4   Vote: I like it +13 Vote: I do not like it

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.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

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

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

cgy4ever is this time correct for SRM 706?

»
7 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Can someone login to arena.topcoder.com?

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    I usually open arena in Incognito to avoid cache issues and stuff — works for me at the moment.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
7 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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 :)

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

    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.

»
7 years ago, # |
  Vote: I like it +6 Vote: I do not like it

How to solve Div 2 1000 ? Thanks in advance.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    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.

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

      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?

»
7 years ago, # |
Rev. 2   Vote: I like it +73 Vote: I do not like it

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)
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      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?
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          7 years ago, # ^ |
          Rev. 3   Vote: I like it 0 Vote: I do not like it

          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

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

            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.

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

              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.

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

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

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

                  yes

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

                  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)

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

                  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.

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

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

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

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

»
7 years ago, # |
  Vote: I like it +31 Vote: I do not like it

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 :).

»
7 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Never mind, Invalid testcase!

»
7 years ago, # |
  Vote: I like it +19 Vote: I do not like it

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