hitman623's blog

By hitman623, 5 years ago, In English

Hello Codeforces!

I would like to invite you to Manthan, Codefest'19, which will take place on Sunday, August 25, 2019 at 8:05 PM IST. This is a combined Div. 1 + Div. 2 round and is rated for participants from both divisions.

The Department of Computer Science and Engineering, IIT (BHU) is conducting Codefest from 23rd August — 25th August. Manthan, the algorithmic programming contest under the banner of Codefest, is being held as a special Codeforces round. The round follows regular Codeforces rules.

All problems in this round were created and prepared by drastogi21, _shanky, Enigma27, _hiccup, KAN and me (hitman623).

A lot of thanks to KAN, 300iq, vintage_Vlad_Makeev, _overrated_, Rox for the testing and valuable comments, and to MikeMirzayanov for the awesome Codeforces and Polygon platforms!

Prizes -

  • 1st place — INR 25,000

  • 2nd place — INR 18,000

  • 3rd place — INR 12,000

  • 1st place in India — INR 6,000

  • 1st place in IIT(BHU) — INR 3,000

  • 1st place among freshers (1st/2nd Year) of IIT(BHU) — INR 1,000

  • Codeforces T-shirts to the participants who will be the first to solve each problem.

Participants will be offered 8 problems and 2 hours to solve them. As usual, the scoring distribution will be announced later.

Hope you guys enjoy the contest! See you on the leaderboard!

UPD: The scoring is 500 — 1000 — 1500 — 2000 — 2250 — 2500 — 3000 — 3750

UPD: The contest has ended. Congratulations to the winners.

1. tourist

2. Um_nik

3. jqdai0815

First place in India: cerberus97

Following are the participants who were the first to solve each problem and have won a Codeforces T-shirt. Congrats!

A. IgorI

B. Geothermal

C. icecuber

D. ILoLy

E. nocriz

F. GoGooLi

G. jqdai0815

H. tourist

UPD: We decided to give the 8th T-shirt to IgorI for problem A. Congrats!

The editorial has been published.

Hope to see you next year!

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

| Write comment?
»
5 years ago, # |
  Vote: I like it -56 Vote: I do not like it

Finally some Indian Contest ..waited for it ..hoping for great problems.. last one was great

»
5 years ago, # |
  Vote: I like it -131 Vote: I do not like it

Waited for the whole year! Hope the legacy of greatness continues!

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

    Lol, waited the whole year and didn't take part ....

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -32 Vote: I do not like it

      Well, Such comments are only supposed to get upvotes. I am glad they both got downvoted.

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

        Yeah lol, they "both" got downvoted.

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

Probably tourist will win the prize for 1st place ...

»
5 years ago, # |
  Vote: I like it -13 Vote: I do not like it

The Legends battle are coming

»
5 years ago, # |
  Vote: I like it -49 Vote: I do not like it

Hope that I'll become a candidate master after this round! Div.1 + Div.2 is a great chance to promote my rating and I only need +8 rating to become a candidate master :D. And also, good luck to everyone!

»
5 years ago, # |
  Vote: I like it +150 Vote: I do not like it

"Codeforces T-shirts to the participants who will be the first to solve each problem.", well, this gonna be interesting

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

    Yes,it will.And I think it doesn't matter if you do a great job or win a T-shirt or not,I think the
    feeling during the contest is the most exciting thing! And good luck to all of you!

»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Wow, an awesome contest ^_^

»
5 years ago, # |
  Vote: I like it +25 Vote: I do not like it

1st place is constant for tomorrow's contest if he participates.

»
5 years ago, # |
  Vote: I like it +15 Vote: I do not like it

8 problems, 4 for div 2, 4 for div 1 or another?

Sorry for my bad english

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

    There are 8 problems for all participants.
    Div1 + Div2 means that everybody can participate. For example above 2100 can't participate in Div2. or the same for above 1600 and Div3.

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

    it mean that the contest for all participants. I think if you can achieved rank 1 in this contest, you will be +800 rating =)) good luck for u ^^

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

I'm disappointed they scraped my e-mail from my profile and decided to send me spam.

It is an old e-mail, meaning that they did it some time ago and not just now near this contest, and I've never registered in their site.

The closest I got was participating in Codefest '18, here in Codeforces, but at that time, I used a different e-mail (a third one).

PS.: And even if they did it at that time (they didn't), nowhere it says they would send e-mails to registered participants.

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

Manthan, Codefest 18 (rated, Div. 1 + Div. 2) The Previous Manthan codefest contest .

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

8 problems for 2 hours?? Isn't that too tight?

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

    It's combined round (Div. 1 + Div. 2), the high rated coders will be bored if they solved all the problems quickly. you can see that tourist solved all the 8 problems of Good Bye 2018 in less than 2 hours, also few contestants solved all the 8 problems of last year Manthan, Codefest 18 in less than 2 hours.

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

I hope that I will raise my rating to 1500-1600

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

Wow.... Such a big prize

$$$出题人家里有矿_{泉水}$$$

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

Any update on scoring distribution?

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I relize that lots of people use anime avatar like me ^______________^

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

None of the other severs (m1.codeforces.com), (m2.codeforces.com), (m3.codeforces.com) seem to have the contest added in there?!

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

Have been participating regularly for the past 2 editions of this contest and had lots of fun.
Hope everyone has fun this time too :)

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

not able to register before 5 minutes of contest... why??

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

can someone submit? it keeps loading

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

It's legendary grandmaster battle. I can't wait to see that. All top 3 highest CF rating have already register, who will win???

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

    let's guess who will win .. tourist ofcourse

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

      He is on 1st place =))

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

R.I.P queue

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

VERY long queue

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

What was the pattern for 1208C - Magic Grid?

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

    Use subsquares 4x4 of numbers 0-15 MOD 16 like (0, 1, 2, 3), (4, 5, 6, 7), (8, 9, 10, 11), (12, 13, 14, 15) — it has zero XORs and prefixes are repeated 4 times, thus their XOR is also 0.

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

      Very nice solution bro, I also thought about that thing, I saw with n=4 and n=8 we can easily solve the problem, just write sequence 0..(n^2-1) from left to right and from top to bottom, but then I couldnt figure out how to use them for another multiple of 4 numbers and your solution helps me a lot. Thanks again!!!

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

    0 1 2 3__________16 17 18 19

    4 5 6 7__________20 21 22 23

    8 9 10 11________24 25 26 27

    12 13 14 15______28 29 30 31


    32 33 34 35_____48 49 50 51

    36 37 38 39_____52 53 54 55

    40 41 42 43_____56 57 58 59

    44 45 46 47_____60 61 62 63

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

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

      Why not doing it in a nice order?

       0  1  2  3
       4  5  6  7
       8  9 10 11
      12 13 14 15
      
    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Everyone is giving example of 8x8, how to extend this to 12x12?

      Edit: To extend, order doesnt matter, just place those new 4x4 matrices anywhere. All will be 0. Good god.

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

        It is simple: every 4x4 subsquare has 0 XORs, so you can arrange them in any way.

»
5 years ago, # |
Rev. 2   Vote: I like it -36 Vote: I do not like it

B question was good. Took more than 1 and half hour to understand it what's it trying to say and implement it.

Thanks for this contest IIT BHU :) . Cheers!

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

    It also took me 1 and a half hour. I am not even sure whether it is correct or not. Let's see the system testing results.

»
5 years ago, # |
  Vote: I like it +23 Vote: I do not like it

How to solve C, it seems much harder than D and E

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

    Fill that array in increments of 4 like 0 4 8 12 1 5 9 13 2 6 10 14 3 7 11 15

    This way xor will always be zero of all rows and columns.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      not necessarily zero. When n%8 equals 0 then it will be zero else it will be 13.

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

    Some one here said that B was harder than C. And you say that C is harder than D and E. It took me more than one and a half hours to get the B pretests correct. I am thinking whether I should I have skipped B.

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

tourist achieved top 1 is really very normal =))

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

How to solve C?

I feel D was easier than C :(((

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

    Oh dear, I got bug at D.

    Dunno whether my C is correct. Btw I use the fact that I can construct a grid for numbers 0->15, then I could construct numbers for 16k->16k+15

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

    U can find a pattern that if you break the given nxn matrix into 4x4 matrices with increasing values (For ex: 0 to 15, 16 to 31 etc) , you can make all the rows and columns have xor sum = 0.
    Find my submission here :)

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

      nice trick, thanks

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

        Could you please share your idea for D? :)

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

          Mine is Nlog^2(N)

          basically binary search + segment tree

          I start filling the answer array in reverse order, Binary search on all feasible values to check the following condition

          if array[mid]+query(0,mid-1) == mid(mid-1)/2, then mid is at current position
          
          else array[mid]+query(0,mid-1) >= mid(mid-1)/2, then lo=mid+1
          
          else hi=mid-1
          

          I used pbds for convenience. thats not needed.

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

      How did you find this pattern ?

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

        They had emphasized that n is a multiple of 4. So I wrote down the binary representation of 0 to 3 ( i.e first 4 numbers, and realized their xor was 0).
        That was the beginning of the idea, and developed the pattern.

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

    This is my approach:

    Divide the whole matrix into 4 * 4 matrices. Then fill every matrix with slight modification of a valid answer for a 4 * 4 matrix. I used the result of test case 1 of the problem statement. Keep a variable that tells us the number of matrices that has been processed. Left shift counter variable by 4 and then perform bitwise OR operation with the corresponding number of the initial matrix while assigning.

    Will it be correct? Yes, because the XOR of each row and column of every 4 * 4 matrix will be the same. So, if you use test case 1, then the XOR of each row and column of the whole matrix will be 13 or 0.

    Will any number repeat? No, because we are using counter variable. Every number has 4 initial bits with 2 ^ 4 possible combinations. These are covered by the initial matrix. We just need to cover the extra bits. The counter gives us new combinations of the extra bits, starting from the lowest. By performing bitwise OR, we are reaching each bitwise combination. So, we will hit each number once.

    My submission can be found here.

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

How to solve D ?

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

    I did it with a lazy segment tree, but there seems to be a way to do it with just a regular segtree/fenwick tree. In the sequence you get, the last 0 is always the 1 in the original. If you imagine that you remove the 1 you found and subtract 1 from every item after that you would get a similar sequence for 2..N. Then you find the last zero again, which now is the 2 and you subtract 2 from everything after etc. You use a lazy min segment tree to find the last zero (order by value and index) and to do the range subtractions.

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

      I thought of this idea last 5 mins before contest end, indeed can't implement it.
      Thank you anyway :)

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

        Pretty much the same. Thought of it 15 mins before, but min segment tree + lazy, gave up there itself >.<

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

          I also got the solution quite late, but I copy pasted the segment tree from kactl. It's a really nice repo with lots of standard CP things.

  • »
    »
    5 years ago, # ^ |
    Rev. 6   Vote: I like it 0 Vote: I do not like it
    Spoiler
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh dear, that's so simple. I don't know I have done.

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

      Fenwick tree with range query and point update I think

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

most of the WA10 because of something like this :

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

What is test #5 of D?

»
5 years ago, # |
  Vote: I like it -8 Vote: I do not like it

I was able to solve C but couldn't solve B. :( Was B more tough than it is supposed to be??

»
5 years ago, # |
  Vote: I like it +59 Vote: I do not like it

Thanks for the short statements

»
5 years ago, # |
  Vote: I like it -15 Vote: I do not like it

I must be crazy. I think the problem should be like ABEDCFGH...

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

Is there any way to solve D without converting it into a Segment tree RMQ problem? I saw the number of submissions and thought I probably need to think simpler.

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

    You can use fenwick tree with range update and point query.

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

    I only used std::priority_queue.

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

      Could you explain your solution?

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

        I break each range into two “operations” one is insertion and another one is deletion. Then I sort the operations in ascending order of position to solve it offline

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

          Can it be done offline? Don't you need to update every range to know the next range to be updated?

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

            I divided the array into 2k non overlapping interval, where k is the width of the bar. So we can update them in any order

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

When in the last 20 minutes of the contest you start doing problem D but in the last 9 seconds you submit it without any tests, because you just finished coding it, and you misstyped a -=, instead of typing +=. I've neve felt this bad before ;(

PS: Submission during the contest: https://codeforces.net/contest/1208/submission/59484539

Submission after the contest, after changing the signal: https://codeforces.net/contest/1208/submission/59486030

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

hard contest for me but I enjoy it very much. Thanks :)

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

How to solve E in time? I had a made a sparse table solution and then just iterated over all of the columns but I couldn't figure out the final optimization. At the end I tried to use a lazy seg tree to propogate the maximum over all columns where the the array can take all of it's values. Is this the right approach?

»
5 years ago, # |
Rev. 2   Vote: I like it -35 Vote: I do not like it

B and D are not good problems. C is nice

»
5 years ago, # |
  Vote: I like it +81 Vote: I do not like it

I love how tourist was able to get 500 on A (submision time 52s) :-)

  • »
    »
    5 years ago, # ^ |
      Vote: I like it -14 Vote: I do not like it

    Keep up to date (hipozhor)

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

    3 miniutes for D and 2 minutes for C is unbelieveable

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

    Guys, I know what happened. tourist obviously cheated. See for yourself:

    How can he start coding at 17:33:16 if the contest started at 17:35:00? I knew something wasn't right about him, but now he gave himself away!

    I would disqualify everybody whose handle starts with t as a warning.

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

      majk Come on. It can be possible that he might have created pre template file for A problem before the contest. We all do a little preparation.

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

        How would he know there's a problem A? You're only making this worse.

»
5 years ago, # |
  Vote: I like it +72 Vote: I do not like it

The best utilization of last ( extra ) five minutes : tourist submitting H at 2:03

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone give a quick editorial of B.

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

    You can delete either:

    1. some prefix
    2. some suffix
    3. something in the middle

    You will be left with (respectively):

    1. some suffix
    2. some prefix
    3. some prefix + some suffix

    Basically, (1) and (2) are the same as (3) if you assume that there is an empty prefix/suffix.

    So, what you can try to do is for each prefix (empty, too) find the largest suffix satisfying the conditions -- what is left between them is exactly what you delete, take the minimum of all such gaps.

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

    The simplest way, according to the given constraints would be to add each element in the array to a set. Then for every index i starting from 0, we traverse j left to right from i, generating every subarray starting at i, and trying to remove each element from the set and check if size of the set at any point is N- (j-i+1). We stop the first time it happens and we've found the smallest subarray starting at i. Then we increment i again, but before doing that make sure you add back the i'th element to the set. It will be O(N^2 lgN) There's also an O(N) solution by the way, that I used.

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

    you can try two pointers to solve that...i am not sure,but I have passed the pretest

»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Okay, why lot of system test fail on B?

»
5 years ago, # |
  Vote: I like it +26 Vote: I do not like it

I solved C with something really easy: I print all even numbers first then I print what is left. For example for n=4 my output will be :

0 2 4 6 
8 10 12 14 
1 3 5 7 
9 11 13 15
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Incredible.

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

    Definitely the best solution here :D.

    It is also easy to prove that it is correct — lines have XOR of 0 trivially (split them by 4) and every consecutive even-odd pair in each column have XOR of 1. There is even number of such pairs, so the total XOR is also 0.

»
5 years ago, # |
  Vote: I like it -8 Vote: I do not like it

so sad I thought C xor will be zero because it looked impossible to guess some number but didn't know how :'(

»
5 years ago, # |
  Vote: I like it +183 Vote: I do not like it

At least 3 persons on my friend list who got F accepted fail this test:

3
2 4 2

Please look into this.

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

    I got uphacked (59479538) by

    3
    0 0 1
    

    Because I looped the number to or with up to the last number, instead of to the third-to-last. The tests were definitely pretty weak :P

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

why codeforces don't compare codes like this 59482093 and this 59481769

tihs is not fare

»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Can we solve B using Binary Search?

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

    Yes. I solved it using binary search. Code Search space is the answer range i.e. [0,n]. isValid function checks if it's possible to delete 'mid' number of values such that rest of them are distinct. I used map to store the values and their frequencies in the 'undeleted' array. If the size of map is n-mid for some undeleted part, it means that all the undeleted elements are distinct.

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

    I think you can.If deleting a large portion from a given position gives you a valid sequence then you can check for even smaller portion.

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

What id test 54 for B ?

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

Guys, I've found a really nice solution for C.

The Ideea is this: Put even numbers in increasing order on odd rows and odd numbers on even rows.

Ex: n=4 0 2 4 6 1 3 5 7 8 10 12 14 9 11 13 15 This is 100% correct and much easyer to implement. :)

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve F?

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

    Could anyone explain why this solution 59478005 for F works?

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

    My solution: We want to be able to fix a_i and compute the best (a_j&a_k) for that a_i quickly. To do so, we iterate through i from large to small, and maintain an array cnt[bit] which stores the number of elements among $$$a_{i+1}, a_{i+2}, ..., a_{n}$$$ that have bit as a submask. How to we update cnt? Note that we only need to know if cnt is >= 2 or not. Now, when we have a new element $$$x$$$ to be added, we do something like a dfs, starting by adding 1 to $$$cnt[x]$$$, and then recursing on all submasks of $$$x$$$ that are one bit away from $$$x$$$. If at any point of time we visited the same number or cnt[x]>=2, we can terminate because we know all submasks must also have cnt>=2. Thus, the complexity of updating cnt is amortized $$$O(n\log a_i)$$$. Finally, with the values of cnt you can also find the best answer for a fixed $$$i$$$ in $$$O(\log a_i)$$$ time.

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

      thank you a lot!!

      By the way is there any method which allows an update in sos dp?

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

can you tell, where my code for B fails?

My Solution

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

    Check this test case: 8 1 2 3 4 1 6 5 4 The correct answer is 2.But your code gives 4 as the output. I guess most of the solutions got failed at system testing in these type of test cases.My solution got failed too.

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

      Thanks, got your point.

      I think we went wrong in trying to implement B in o(n).

      Constraints are the real insights to the problems.

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

    Try this one:

    6
    3 2 5 3 1 5
    
»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Why does solution for B in $$$n^2 \log^n$$$ give TLE? I used both binary search and sets (I know it's not the most efficient), and couldn't get it accepted. TLE on test 18. Can anyone help?

$$$n^2\log^2n$$$ is roughly 43587196 ops at n=2000 which should work in under 2secs imo.

Submission

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

    You might have a miscalculation.

    4million*log*log is around 400 million, which might not pass because of set constant.

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

    You took the log to the base 10. Base 2 would be more realistic and then it's already $$$5*10^8$$$, also set::insert probably has some additional constant factors.

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

Can someone please point out the logic flaw in my solution for problem B?
PS: Found my mistake. Thanks everyone.

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

I didn't leak code to anyone but I receive system's message :'(. May be this is an accident

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

My Solution for B, fails on test 54 but I don't know why? Someone please help! LinkL: https://codeforces.net/contest/1208/submission/59459333

»
5 years ago, # |
  Vote: I like it +59 Vote: I do not like it

So tourist doesn't get two T-shirts? :sad:

»
5 years ago, # |
  Vote: I like it -128 Vote: I do not like it

It is totally unfair to me . I have solved the second problem completely with required time complexity even than your website is showing TLE . Why? Do something otherwise it is totally waste of time for me to participate in challenges on your website

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

    Maps are not constant complexity. Expected complexity was O(n²log(n)), not O(n²log(n)log(n))

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

    The CF judge is fair to everyone. It's just because your solution is too slow. Having a solution of intended time complexity does not necessarily mean it must pass.

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

    No one cares if you participate or not. This platform is for everyone to learn and improve. If you have done a mistake try to accept it and learn from it, instead of complaining.

»
5 years ago, # |
  Vote: I like it +51 Vote: I do not like it

I was able to pass pretests with my too complicated solution for G, but I got TLE on one of the pretests during system testing. Moreover, after the contest I submitted the same code 10 times, 9 of those 10 attempts got AC. Maybe solutions should not be rerun on pretests during final testing, to prevent such disappointing situations in the future xD

»
5 years ago, # |
  Vote: I like it +59 Vote: I do not like it

1179 contestants solved segment tree problem. It seems like CF is "growing up" or I am "growing down".

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

    I solved B in more than 13 minutes and solved D in less than 10 minutes.

    I think I need more "IQ"...

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

    I can't solve C because I'm not good at constructive problems. I think I should practise it more.

»
5 years ago, # |
  Vote: I like it +27 Vote: I do not like it

tourist returned to 3700+ in 31 months.

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

Can someone tell why my code 59471606 of B problem gave wrong answer on pretest 9? It gives same output as jury's output when I run it in my system.

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

How to solve D,I don't understand the editorial ?

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

    If the input is valid, as the problem statements says, there is always an answer and it will be unique.

    Let's build from the last element in the array to the first one. Also create a data structure that can query the sum of all values in range[0, r] and update a point in log.

    Whenever you try to put some number into the answer, it will have sum of all the other unused numbers, because they will be somewhere before it in the answer. Initially, all numbers are available. So you can do N updates like: update(i, +i).

    As you know the sum of all numbers before it in the array, just binary search what element have exactly the same sum as the input, then remove it from the answer like: update(i, -i).

    Suppose that you initially have 1, 2, 3, 4, 5. So, your data structure will be: 1, 3, 6, 10, 15.

    If you want to put an element with sum 6, you should put element 4 as the last one, then your data structure will look like this: 1, 3, 6, 6, 11.

    Keep doing this and you will end up with the answer.

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

      It seems a same approach with mine (and different with the editorial).

      However, I don't know how to deal with such condition:

      n=5, the sequence is 0 4 0 1 1

      0 1 3 6 10

      (the last one is 2)

      0 1 1 4 8

      (the last one is 3)

      0 1 1 1 5

      Now, there are three 1 can be chosen (in fact, the third 1 is correct), and how can my program deal with such condition in appropriate complexity.

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

        You should always try to find the last one element that have the same sum. If the data structure is like ... 0 1 1 1 1 2 ... And you are searching for 1, just get the last 1.

        If you put another value except from the last, you can't build the answer.

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

          Thx! I do exactly the same thing as you say and got WA on 9. However, it turned out to be that it is "long long" which made me get WA. QAQ

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

            You can also improve your answer by removing the binary search, just traversing the segment tree.

            If you are in a vertex searching for something with sum x, then:

            • if left node have sum >= x, then call left vertex with x

            • otherwise call right vertex with x - left_sum

»
5 years ago, # |
  Vote: I like it +54 Vote: I do not like it

How is it possible to solve A in 52 secs if statement loads for half a minute xD?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    I believe the writers of problems couldn't have beaten tourist for the first 7 problems if they implemented the solutions from scratch.

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

    Read the statement in 6s, write the code in 13s and submit in 3s

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

    You can open problem statements much faster using m1.codeforces.com

»
5 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Tourist is such a monster!

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

I think we should swap problem C and problem D.....

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

I tried to solve the second question using binary search on the length of segment to be removed. The pretests passed but I got TLE in the final testing.

http://codeforces.net/contest/1208/submission/59462841

Can someone tell me what went wrong ?

»
5 years ago, # |
  Vote: I like it -6 Vote: I do not like it

why I dont see the prize for first solve of problem H in the list above while there is someone has solved this in the contest, can anyone explain this for me?

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

How to solve G? It seems like a math problem about divisors, and the AC code looks very simple. However, I did not understand the behind logic yet. Anyone can help?

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

Can someone help me with the code for B problem? Here is my code:

#include <bits/stdc++.h>
#define ll long long int

ll n,m;
ll a[4004];
// set<int>s;
map<int,int>mp;
int last[4004];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        a[n+i] = a[i];
    }
    for(int i=1;i<=2*n;i++)
    {
        last[i] = mp[a[i]];
        mp[a[i]] = i;
        // cout<<last[i]<<" ";
    }
    // cout<<endl;
    int ans = 0;
    for(int i=1;i<=n;i++)
    {
        int cnt = 0;
        for(int j=0;j<n;j++)
        {
             if(last[i+j]<i)
             {
                cnt++;
                ans = max(ans,cnt);
             }       
             else{
                break;
             }
        }
    }
    cout<<n-ans<<endl;
    return 0;   

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

Can Any one explain Problem D ??

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

Request for future contests :: Please make large inputs downloadable

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

If you've solved problem D. And want to solve another interesting problem like this. Try Lightoj — Lining Up Students In Lightoj one need a account in case of view a problem. In case you don't have an account there you can read the problem here

»
5 years ago, # |
  Vote: I like it -34 Vote: I do not like it

asd

»
5 years ago, # |
  Vote: I like it -35 Vote: I do not like it

hello my fan

»
5 years ago, # |
  Vote: I like it -44 Vote: I do not like it

Codeforces is too easy to me

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

Can I get some help to solve B...This was my code https://codeforces.net/contest/1208/submission/59474361 ...Why am I getting TLE...As much as I can see, the solution will execute 6.4*10^7 instructions at max

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

    Operations on unordered_map are often more than 1 instruction, and the $$$O(n^{2}logn * map)$$$ will probably have a bad constant and run for longer than expected.

    Some improvements:

    The actual elements in the array don't matter, only that they're unique. Therefore, you can compress coordinates and use a boolean array (or bitset, if you really want) instead of a map. This alone should get you under TL.

    The binary search doesn't actually help you. Since the check function is $$$O(n)$$$ anyway, you may as well get rid of the $$$logn$$$ factor by just finding the first location, iterating from the right to r, that creates a duplicate (of course, include the elements to the left of l first and account for duplicates there)

    And because three is a good number, even though this isn't necessary, your loop in check skips over a lot of elements. Each continue can cost you, and it will be better to split check into two loops.

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

Was anyone able to get AC with binary search on B ? If yes can you share your solution ?

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

The problems are good.

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

Hmmm. Is the difficulty point of H right???

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

    It seems to be fixed now, I've messaged Mike about this.