MikeMirzayanov's blog

By MikeMirzayanov, 3 months ago, translation, In English,

Hello, Codeforces!

I'd like to invite you to Codeforces Round #436 (Div. 2). It'll be held on Monday, September 25 on 10:35 UTC and as usual Div. 1 participants can join out of competition. Note that round starts in the unusual time!

This round is held on the tasks of the school stage All-Russian Olympiad of Informatics 2017/2018 year in city Saratov. They were prepared by Perforator, MikeMirzayanov and fcspartakm. Many thanks to the testers: sdya и BledDest, and coordinators KAN and gritukan.

It will be a little unusual round — you will be given six problems and two hours to solve them.

Good luck and have fun!

Congratulations to winners!

Div. 2:

  1. ZJT_NOI2017_AK
  2. AngusRitossa
  3. Jha_The_ME_Coder
  4. cxh007
  5. Alexvsalex

Div. 1:

  1. Shik
  2. dreamoon
  3. black_horse2014
  4. orbitingflea
  5. NiroBC

Analysis is here.

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

»
3 months ago, # |
  Vote: I like it +28 Vote: I do not like it

why it starts on that time ?? can't it just be as usual ??

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

    At this time the Olympics in Saratov.

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

    I only hope this round is friendly

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

      I hope so. But surely I'll get every problem TLE or RE then.

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

    Oh My God,, I completely missed the round not even a minute

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    People from Far East are not able to participate in "usual" time for you. So this is this the one of few rounds in comfortable time for them. Please be patient :) P.S. But unusual time is in case of original olympiad time, to prevent cheating.

»
3 months ago, # |
  Vote: I like it +22 Vote: I do not like it

Similar contest of last year : http://codeforces.com/contest/723

»
3 months ago, # |
  Vote: I like it -6 Vote: I do not like it

unusual bad start time,just why???

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it +47 Vote: I do not like it

    It's also good start time for Chinese, Korean, Japanese, people live in Kamchatka, etc.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    there're still some people in asia

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

**It will be a little unusual round** — you will be given six problems and two hours to solve them what does it mean?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +206 Vote: I do not like it

    It means that you will be given six problems and two hours to solve them.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      It will be a little unusual round I have problem with this part.

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it +58 Vote: I do not like it

        In usual round you have five problems, not six.

»
3 months ago, # |
  Vote: I like it -10 Vote: I do not like it

Wooow 3 contest in 3 days

»
3 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Tough choice. Wake up at 3:30am or go to bed at 5:35am?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    very nice time for china

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

    another choice is no sleeping

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Can't you do both?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    we always stay up late to attend the test in summer,China.....

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      the best time for chinese

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        yes!:)

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          dalao哪里人?

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            please speak english

            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              why we must speak english?i mean between two chinese

              • »
                »
                »
                »
                »
                »
                »
                »
                2 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                ok,i'm chinese,too.but most of the users are not chinese and they cannot understand you

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  i mean some others who look the communication between you two

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  fine,actually,we're both mogicians,my qq:2632812444

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 months ago, # ^ |
                    Vote: I like it +6 Vote: I do not like it

                  Hey I don't think you should mh in cf(you know what I mean.) As this guy seems don't know what you are talking about.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  GLGJSSY,QYHFBQZ

              • »
                »
                »
                »
                »
                »
                »
                »
                2 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                what,you are a magician .what do you mean

»
3 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Hope I can become candidate master after this round.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it -38 Vote: I do not like it

    You won't. You will do badly and have 1833 rating right after.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      Really? So when I can finally become candidate master?

»
3 months ago, # |
  Vote: I like it -16 Vote: I do not like it

scoring ..??

»
3 months ago, # |
  Vote: I like it -10 Vote: I do not like it

Russia's time is one o'clock in the afternoon, but for China is six o'clock in the afternoon. This is a good time for us, but it may be for some other people who need to stay up late at night or get up early in the morning.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What does that mean?

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Well, in Most area in China, it's UTC+8. So it means if we want to join a contest which is held at six o' clock in evening in Moscow, it will be eleven'o clock in Beijing. In this case, most contests were hold in the midnight. To join it, we have to spend our sleeping time.

»
3 months ago, # |
Rev. 4   Vote: I like it -10 Vote: I do not like it

.

»
3 months ago, # |
  Vote: I like it +8 Vote: I do not like it

i hope clear and short statement.

»
3 months ago, # |
  Vote: I like it -52 Vote: I do not like it

round will be rate or not ??

»
3 months ago, # |
  Vote: I like it -11 Vote: I do not like it

Why so early. I'll be in school at this time(4

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Don't go to school (if you don't have any important exam).

»
3 months ago, # |
Rev. 2   Vote: I like it -7 Vote: I do not like it

I am a newbie and I wonder how to compare my rank profile to others in a picture? I need someone tell me plz. No down vote plz.

»
3 months ago, # |
  Vote: I like it +14 Vote: I do not like it

This round is very kind for China :)

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For Bangladesh too. It's going to be 4:30 at afternoon.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Ah! Really? I prefer the usual time. Why don't you?

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I said 'kind' not "The Best".In some countries there is going to be a lot of trouble. I also prefer the usual time.

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    Applese is so smart that he will solve all problems in this contest!

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I will take part in this,first time.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm having a BED time participating this round...

»
3 months ago, # |
  Vote: I like it -44 Vote: I do not like it

is it rated?

»
3 months ago, # |
  Vote: I like it -13 Vote: I do not like it

Scoring?

»
3 months ago, # |
  Vote: I like it +2 Vote: I do not like it

hope to be green :(

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    After System testing, not green yet but heading towards it.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can not hack

»
3 months ago, # |
Rev. 2   Vote: I like it +49 Vote: I do not like it

3chenruiyangcsh, are you really a human???

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

FAQ: Why at this time?

Answer: The same problems were used at the school stage All-Russian Olympiad of Informatics, so it's important that it's participants shouldn't participate in this round, because they had the same problems 4.5 hours earlier.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

nice pretests :)

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hack page is not loading properly.

»
3 months ago, # |
Rev. 5   Vote: I like it +15 Vote: I do not like it

RIP E. :(

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I have a question on Problem A, why answer of this is not yes?

4 2 1 1 3 First one will choose 2 & second one will choose 1, then first one will choose 3. So both of them will have same numbers of card.

»
3 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Kept getting Wrong Answer on pretest 3, Problem E. Any hints?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think it's just some small random test. I got wa on test 3 because I didn't maintain parent array correctly.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    well pretests are weak i guess i sorted the values by d before dp and another one in my room sorted by t both pretest passed

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    This test help me:

    5
    1 2000 1
    1 2000 4
    1 2 19
    1 4 18
    1 3 17
    
    Ans:
    59
    5
    3 5 4 1 2
    
    • »
      »
      »
      3 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      The question's language is so bad :( I explicitly sorted :( WA

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I took dp[i][j] to be the min time required to get value of j from first i items. If I dont sort according to deadline I get wrong ans, but if I do I get right answer. I dont know how sorting is helping. Can u pls tell?

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

          Firstly, I mentioned sorting for the final part, when we have to print the answer.

          Coming to your question, sorting with deadline is necessary because if you don't, you might miss out some optimal combinations.

          Try running your code on mentioned test and realise:

          2

          2 5 3

          2 3 5

          ans:

          8

          2

          2 1

»
3 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Missed a stupid edge case in problem C,ACed in the last 7 minutes ;/ Also guys,how to solve problem D ? I thought about it for a full hour,came up with 3 non working greedy solutions,

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    D seemed ad hoc, I got AC in pretests. The number of changes is just n-number of unique integers in the input. And change the first duplicate to 1 and then the second duplicate to the next smallest possible element that's not in the array till now and fill like this. I hope it doesn't fail O.O

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      wont your approach fail at test case number one, because the first duplicate is "3" at i = 1,so you will replace that 3 with "1" as "1" is not in the initial array, Next at i = 2, we get a[i] = 2 which is also a duplicate,so we will replace that with 4, yours should give answer 1 4 2 3 in this case.. I think I dont clearly understand your approach,please elaborate,thanks!!

      • »
        »
        »
        »
        3 months ago, # ^ |
        Rev. 2   Vote: I like it +1 Vote: I do not like it

        I passed the system tests yay! So yeah, I told a bit wrong. What I did was....

        Let the element to be replaced(in pace of a[i]) be cnt; if current element(2 in this case) is less than cnt, then I check if I have left any 2 before, if I have then I will change current 2 to cnt or else I will leave it and go to the next index and mark 2 as done. Code here: http://codeforces.com/contest/864/submission/30711359

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Pretest 6 problem C?

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Guys, I am new here at Codeforces, can anyone plz tell where i'll find the editorials to the contest problems ?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Editorials will be avialable soon , link will be given in thi post after update. Also you can view editorial directly from problem page once they are released. Usually editorials are avialable with few hours .

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    its takes time.

»
3 months ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

Problem C

01:40:22 Pretests passed [pretests] → 30719776

01:53:58 Problem locked

01:55:26 Hacked by lyllyl

:( :( :(

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

C — https://pastebin.com/nE1gS3Wd

Why WA at pretest 6?

»
3 months ago, # |
  Vote: I like it -7 Vote: I do not like it

CF — Predictor are it`s working with any one ??

i want to know my expected rate :( :(

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why do I like this contest so much?)

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hack for C: 10 8 6 2 Answer : 2

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve the problem E?

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

    Sort items by deadline:

    dp[j][t] — maximum value you can get, when you select from first j items, when you are at time t.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How would you go about recovering the indices of the chosen items?

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Remember what are you doing in the state (if it is invalid — i.e. t >= d[i], move to dp(i,d[i]-1)). Then you can either take item i or do not take it and move to dp(i-1,t). When you recover the soultion, just follow the same decisions.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I took dp[i][j] to be the min time required to get value of j from first i items. If I dont sort according to deadline I get wrong ans, but if I do I get right answer. I dont know how sorting is helping. Can u pls tell?

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I noticed that this guy: ILIAz is accessing uninitialized variable in case the ans = 0: http://codeforces.com/contest/864/submission/30720468

Unfortunately my hack with 1 item did not work...

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How do we do F?can anyone tell me please?

»
3 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

@admin I submitted E about a minute before the end of the contest. I straightaway got WA on pretest 1 which works fine on my system. Moreover, my submission can not be seen on the standings page. Please fix this. KAN

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

    Submissions not passing the first test are not shown on the standings and are not counted in penalty.

»
3 months ago, # |
  Vote: I like it +15 Vote: I do not like it

When you were about to solve E first time in your life but then you get WA because you wrote x instead of a[x][3]

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I myself did a silly mistake , corrected it , as i went for submit -->>> contest ends :-(

»
3 months ago, # |
  Vote: I like it -18 Vote: I do not like it

fuck shit man

»
3 months ago, # |
  Vote: I like it +3 Vote: I do not like it

For problem D,I'd like to know how my method is wrong...Thank you in advance.

Firstly count the unnecessary number in the sequence,(for example 2 2 then one of the 2 is not necessary ,it must be replaced by other number) and then set i =1 loop in range[1,n],when find a number which has appeared 2 or more times in the sequence then try to replace it,but if even the smallest number which haven't come up in the sequence is larger than this unnecessary number then we don't replace it;otherwise,replace the unnecessary number with the smallest number which haven't came up yet.

And for those number still not appear in the sequence(let them be a set),set i=n down to 1 loop,then perform the replace operation from the bigger to lower in the set then output the sequence

And I got WA on test 8,until the ending of the contest I didn't pass pretests and just lose the scores of the unsuccessful submissions and got a terrible standing ...As I'm not perform well in several current contests I don't want this bad condition continue I'm so sad...

  • »
    »
    3 months ago, # ^ |
    Rev. 5   Vote: I like it +3 Vote: I do not like it

    I tried the same approach as you and I cannot come with a test that makes my solution fail. Let's wait until tests are visible... :(

    upd: wrong answer 3183rd numbers differ — expected: '3390', found: '125991'

    I think it is better to continue thinking about it XD

    upd2: try this one

    5
    1 2 2 4 4
    

    Note that the missing numbers are 3 and 5. On the forward iteration we will replace the first 4 with our 3, and on the backwards one we will replace the second 2 with our 5. This will leave the array 1 2 5 3 4. However, note that we can get the array 1 2 3 4 5 by changing two numbers, too.

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

      Ouch...I got it now...Thank you(you are so clever...I didn't find such test cases before reading your comment by myself...

»
3 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Me After seeing superfast system tests Image

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    looks like you haven't been participating in cf rounds since more than a month bcoz these days its fast.

»
3 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Solved 3. Good for me or else i would have gone to depression.

»
3 months ago, # |
  Vote: I like it +30 Vote: I do not like it

How to solve F?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Consider the arrays of short ints reach[3001][3001] and nex[3001][3001][13]. Define

    • reach[i][j] = 1 implies there exists a path from i to j. Easily generated with DFS.
    • nex[i][j][k] is the 2k + 1-th node on the optimal path from i to j,  or infinity if it does not exist. First generate nex[i][j][0] from reach,  and then generate nex[i][j][k + 1] from the values of nex[i][j][k].

    For a query (s, t, k) first check nex[s][t][12] and nex[s][t][0] to see if there is an infinite cycle, or a path does not exist. If none of these are equal to infinity, we can just compute the k-th node on the path in a similar manner to LCA.

    Of course, it is easier to just compute the answers in an offline fashion.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I just read your code. I was amazed to see you use "short" while I received MLE using "int" in the contest.:( However,it seems that the time limit is so loose that I passed the problem by only storing nex[3001][3001][6] and brutishly use nex[x][y][5] when k is too large. Maybe it looks like a sqrt deviding.:)30738221

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    A solution which probably uses a bit less memory than Benq's.

    After reading the input, sort adjacency lists by the endpoint node: this way doing a DFS traversal will result in ideal paths.

    Group all queries by the starting node. We'll answer each group separately with a separate DFS that starts from the starting node.

    Doing the traversal maintain some additional data structures:

    • A stack of the nodes on the current path (append the current node to it at the beginning of the recursive function and remove at the end).
    • An array to tell if a node is currently on the stack (in current path). We can reuse the same array that we use to mark whether the node has been visited.
    • Unordered set of nodes that form a loop: whenever we find an edge to a node that is currently on the stack, we add it to this set; before we end analyzing the node we remove it from this set (at the same time as we remove it from the stack).

    Whenever we reach a node which is an end point in any of the queries with our starting node and we did not compute the answers for them yet:

    • if the set is not empty, set the answer to -1 (we know that there is a loop that we can use to continue making the path to this node lexicographically smaller indefinitely);
    • otherwise, set the kth element of the stack as an answer for each of the corresponding queries.
»
3 months ago, # |
  Vote: I like it -15 Vote: I do not like it

Is this round rated?

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

KAN MikeMirzayanov My code is giving error on problem D. (Exit code is -1073741819). Solution It is giving error on this test case: 2 2 2 I have checked it on my pc and also at custom invocation at Codeforces it is working fine. UPD:Sorry, there was some minor error, I have fixed now.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am also getting the same error on test case 4. Input: 6 5 5 5 6 4 6

    however on my pc it is giving correct output

»
3 months ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

Sorry, I've just made a mistake.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone explain me the test case for F?

7 7 5
1 2
2 3
1 3
3 4
4 5
5 3
4 6
1 4 2 // 2
2 6 1 // -1
1 7 3 // -1
1 3 2 // 2
1 3 5 // -1

Here query(1, 4, 2) == 2. However, there is no ideal path from 1 to 4 (1-2-3-4 > 1-2-3-1-2-3-4 > ...).

Where am I wrong?

»
3 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Is it real to solve problem E by random-based solution?

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Cant load the pages . Is sys test over?

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem C?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Greedy + Simulation. Suppose you are at 0, if you can go to 0--->a---->f without refueling go, otherwise go to f first refuel and carry on. Vice versa for a to 0. Carefully implement it.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks!!

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It is giving wrong output on testcase 7. Can you help what corner case I am missing?

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You can see the test case on which your code is giving wrong answer. BTW, your condition for -1 is wrong. It should be if b < max(f,a-f) return -1.

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    One way to solve problem C is using Dynamic Programming approach.

    Think on this function F( i, j ) = maximum amount of gas that I can have if I have had i journeys using j times gas station before.

    See my code for more details: 30708352

»
3 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Why is the cf predictor not showing today's round ?

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Rating update is taking so long. It seems it is compensating for fast system testing.

»
3 months ago, # |
  Vote: I like it +19 Vote: I do not like it

No mention of winners :( . Don't know I will ever come under 5 or not again :(

»
3 months ago, # |
Rev. 2   Vote: I like it +15 Vote: I do not like it

Lately, I'm constant af...

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you god for helping me not make systest failing bugs today. :)

»
3 months ago, # |
  Vote: I like it +16 Vote: I do not like it

It seems that there is only one people (me) confused by the definition of "lexicographical order" in Problem C.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    Sorry...I mean Problem D...(will I get lots of downvotes? scared:(

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I got hacked at a problem today. Can someone explain how hacking a problem works and how can I hack someone? Also, when will the editorial be posted?

»
3 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Finally, I became candidate master!!!

»
3 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

I'm blocked on something silly and am unable to figure out whats wrong. Would be great if any of you could help! For problem E, In this submission, I have clearly sorted my vector before printing it. Yet, it somehow prints a non-sorted sequence. (Check verdict for test case 3)

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Test case 3) Participant's output 1 2 4 5 6 7 8 9 looks sorted to me

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    deathsurgeon

    "In the third line print m distinct integers — numbers of the saved items in the order Polycarp saves them."

    The answer isn't necessarily sorted x)

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Firstly, I misinterpreted the question. Secondly, I also got confused between "output" and "answer" in submission. Ahh, I'm getting old at this :/ Anyways, thanks NMouad21!

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone got the idea of problem F test 13 query 24?

I saw many people failing on it... (including me...)

I was wondering if the algorithm was incorrect...

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    That could be because of incorrect algorithm. At least mine fails thereat.

    Test your solution with

    3 2 1
    1 2
    1 3
    1 3 2
    

    It should output 3

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oops, my solution passed this test...

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I found a data that can cause me WA now

      7 7 1
      3 4
      4 5
      5 1
      5 2
      1 6
      6 1
      2 7
      3 7 5
      

      Thanks for your help!

»
3 months ago, # |
Rev. 4   Vote: I like it +1 Vote: I do not like it

in problem 864E — Fire

I can't understand why it's right to sort the input by d and then calculate the answer with dp ,, t is also affecting the answer as t can be large and d small so i should take this value after other values with large d ?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Consider any two items. If in the optimal answer, I am only going to take one of them, then their relative ordering doesn't matter.

    But if both of them are in my optimal answer, then which one would you take first? It makes sense to take the one which is ending first (i.e. has a smaller d value) than the one which is ending later (i.e. has a higher d value).

    Since if you first took the one which is ending later, and then took the one which is ending earlier, then you can also do the inverse, i.e. take the one which is ending earlier and then take the one which is ending later.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Its about the order of choosing of course its better to choose the items with less d first so they wont be expired

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Imagine that d[i] + 1 is a moment when explosion hits i-th item. And DP approach here is just a process of caching recursive brute-force which would traverse items in increasing order of d[i] because it optimizes order preserving O(n!) bruteforce and overcomes 0-1 preserving O(2^n) bruteforce (there is no other simple bruteforces I've thinked about here).

»
2 months ago, # |
  Vote: I like it -11 Vote: I do not like it

Is there going to be a tutorial?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why my program not work in task B. In my computer its working good! http://codeforces.com/contest/864/submission/3075

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

It seems Tutorial link under contest is wrong

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Kindly add the correct tutorial link to the contest material section. It is opening Manthan's editorial link.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Please hack my submission on problem D(Although someone helped me with my earlier idea about this problem right after contest but I came up eith a new method and passed the case he provided but got WA on test8...)I really don't know why this method got wrong answer...submission30755521 Thank you in advance.

The main idea I came up is to count the times every numbers appear int the sequence,and maintain a set containing all the missing numbers didn't come up in the sequence yet,and set a loop from 1 to n just to do such operation: if the number appear in this position is counted more than once,then replace it with the smallest number which didn't came up yet and decrease the counter of the original number in this position by 1(You will say this must be wrong but please go on reading...)After doing this we set a loop from 1 to n again and if find a position that the new number I just filled in it is larger than the original number in there before,then replace this number to the original number,push the replaced number(the bigger one) into a vector which contains all the numbers that must be replaced to more left position,at the same time maintain a vector to push back the last position of the original number in this sequence(it means that the bigger number will be put in sequence with the index as big as possible),then sort the position and the replaced numbers,and fill these pool numbers in these positions one by one.(Sorry for my bad English and description...

Thank you again for hacking this solution....

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    try this case

    7
    6 1 1 6 1 1 6
    

    Your output

    5
    2 1 3 5 4 7 6
    

    Answer

    5
    2 1 3 4 5 7 6
    

    What's more...I failed to analyze the code so no solution or reason to be provided. :(

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you very much...

      And now I think the reason why this code got wrong answer is just because in this method the sequence maybe have some missing numbers already in some positions which they are not going to be. (What a bad solution I created...:-(

»
2 months ago, # |
  Vote: I like it -10 Vote: I do not like it

Thanks for the information. I would like to introduce ourselves as one of the Best Digital Marketing Companies in India to see our creative work please visit our website.