Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

Errichto's blog

By Errichto, history, 16 months ago, In English,

The qualification round starts in 50 minutes. Let's share scores and discuss the problem after the contest. Useful links below.

Judge System
Official livestream
FAQ

Good luck!

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

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

Is it rated?

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

    boht hard boht hard

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

    this is literally the battle between "downvoting is it rated comments" and "upvoting reds no matter what".

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

      I trust the community and hope it's gonna be a net loss.

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

A — 2
B — 231,591
C — 1,426
D — 440,332
E — 417,896

Total 1,091,247

I guess we will be around top30. I would like to hear how to get around 1,2kk.

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

    A — 2
    B — 239,997
    C — 1,616
    D — 243,517
    E — 419,938

    D was simply too big to fit into our TSP solver on our machine.

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

      Which solver did you use? I tried LKH for B but it did nothing in 30 minutes so I decided to write some heuristics myself.

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

        TSP solvers are not as useful as other solvers. Just implement simple simulated annealing with random section reversal and you can get very good results. You can also control how much time you want to spend.

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

          I mean, what existing libraries are a good fit. I can implement some good stuff myself but sometimes it might be better to delegate some work to a professional :)

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

      Doesn't using TSP force you to hold all the graph? like n^2 edges?

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

        1) You can do it with enough memory.
        2) You don't have to store that. When you need to know the distance between two vertices, compute it.
        3) Or store only best 1000 edges from each vertex.

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

      A – 2 B – 228498 C – 1775 D – 441242 E – 560550

      In extended round ı tried so many things for B but no way, 228K.

      majk I think your 239997 is max score for B. Could you explain your approach?

      Thanks.

  • »
    »
    16 months ago, # ^ |
      Vote: I like it +79 Vote: I do not like it
    • A — 2
    • B — 237477
    • C — 1658
    • D — 440897
    • E — 473769

    Judging by your scores, you probably did the same mistake as we did :) Joining V's into pairs before arranging them into a path is not good enough, one has to create pairs while building the path. It is possible to get 561k+ on E.

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

      Makes perfect sense, thanks.

      EDIT: Yup. I've now implemented just the simplest O(N 2) greedy solution for E that takes the best next picture and got 550k.

      Edit2: I added penalizing for using pictures with a big number of tags, and the score jumped to 565k. That would give us the first place with 10k lead.

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

        These statements like "if i had implemented something i know postfactum to be correct [without affecting other scores] I'd have outplayed everyone by 10k" never stop being funny. Our team managed to increase the score by 65k 10 minutes after the end and 30k more after multiplying a magic constant by 2, but this doesn't necessarily mean that if the contest had last until :45 we'd have been top-dont-rememember-how-much-but-a-little.

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

          I don't see anything funny here. And certainly, I don't claim we would win after 20 more minutes because I implemented what tourist mentioned, not my own idea. I'm afraid we would only get lower and lower in the leaderboard, actually.

          Also, insert "let people enjoy things" meme.

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

        Can you give more details about the implementation? Don't you need to search for the best two pictures, which gives N^2 for a single step and N^3 in total? That seems to be too slow given the size of N. What am I missing?

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

          Build the slideshow greedy slide by slide. If the last slide is complete, just find the next one over all images (like considering all them as horizontal). Otherwise, the last slide contains 1 vertical image, so find the second one over all vertical images left, that gives the best score.

          Just this idea gets 547117 on E.

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

            Can you tell me on what basis you are selecting the best V pair (i.e. second V )

            We were choosing best V on basis of most number of common tags but its not good enough.

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

              He exactly explained that. Don't choose the whole pair at once. Choose best first picture, then best second picture.

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

                I just want to know on what basis you are selecting the "best" picture.

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

                  giving the best score so far

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

                  Thanks :).Implemented the solution and got 500K+ for E. Can you tell me how to improve more on it!!!

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

                  Read editorials/write-ups for similar competitions like topcoder marathon. You will learn new things that would be useful in hash code too. For example, read about simulated annealing. Or watch my video about hash code, link.

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

        Just by curiosity, how much time it took more or less to run the greedy solution on all testcases? (In which PC specs?)

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

          2 minutes per test on a good laptop. We used bitsets to store tags in D and E.

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

            So fast.... We used Python3 and it took us 4hrs on just test case E we used normal sets to store tags. On a good laptop

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

              Maybe pypy would help. And yeah, C++ is fast.

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

        Would who share your latest code? I'm struggling to get past the 1.17M mark

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

      Can you share your code

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

A — 2 B — 149475 C — 1582 D — 436321 E — 414517

We are the only team among all my friends who sucked so much at B :/

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

A — 2 B — 64428 — This one was a failure :V C — 1368 D — 388349 E — 323141

  • Sorted and paired be tags length.
  • Shuffled.
  • Construct each blocks of 1000 greedily.
  • Try to take blocks of 1000 and optimize them.

That about it~

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

What was the third test case for?

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

    At least other 3 cases mattered this time. Last year only one test had significant impact on overall score.

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

    It was good to quickly check if your solution broken or not

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

A — 2 B — 202830 C — 1470 D — 396293 E — 389426

We used a greedy approach to solving TSP. Our solution also involved some amount of randomization. We created the vertical pairs using the concept of choosing two pictures with least common tags.

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

    B — 202734 C — 1439 D — 398968 E — 366042

    With the same approach but the Vs are paired randomly.

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

    We used the same approach for pairing and used the same greedy approach mentioned above. Then just chose a random picture to start and add the picture with the maximum score next to it. It was enough to get A — 2 B — 225171 C — 1573 D — 434273 E — 412744 with some more optimizations.

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

A — 2

B — 202,740

C — 1,764

D — 439,070

E — 417,037

Total 1,060,613

Key to top50 — i7-8750H and a lot of different heuristics.

»
16 months ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it
A - 2
B - 204,465
C - 758
D - 237,168
E - 121,227

Total - 563,620

B had a large number of tags. From whatever limited checks we did, we found no tag repeated more than twice in the entire file. Good enough to write a custom solution where we make a inverted index tags to photos and then for a group of tags we find the photo that shares the as many tags as possible. Since there are not many tags in common, this results in OK enough score.

For C, D, E

We only allow edges between slides that have almost same number of tags and choose greedily.

Our V pairing function was very bad, we paired up images which have almost same number of tags which maximises union of tags of the pair (for a V image A with N tags, find another V image B with [N — t, N] tags where |Union(A.tags, B.tags)| is max)

Ultimately we decided to drop V images from C set.

Good contest, really wish we did better on C, D and E.

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

How do all you get 230k+ on B? We get our score on B using some greedy, then improved on D/E by a lot but didn't get a single extra point on B.

A 2
B 204630
C 1742
D 436266
E 551892

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

    Some thoughts in B: each tag occurred at most twice, and the intersection between any two photos had size either zero or three. This essentially reduces the problem to finding (or approximating) a Hamiltonian path in an undirected graph (with edges joining the pairs of intersecting photos).

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

How did you guys choose the first picture?

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

i am noob can someone submit give me solution link(C or C++)

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

.

  • »
    »
    16 months ago, # ^ |
    Rev. 3   Vote: I like it -8 Vote: I do not like it

    1> First i separate the horizontal and vertical pics. 2> For every nH (Total number of horizontal images).

    for(int i=0;i<nH;i++){
         int ind=i+1;
         int min=0;
          for(int j=i+1;j<nH;j++){
              score=TOtal points if I and J are adjacent pics.
              if(score > min)min=score and ind=i;
       }         
        swap (i+1, ind);
    }
    

    3> I do the above the same for vertical images but with taking combination with minimum overlap .

    Is it same as we do in the like selection sort method !!

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

...

»
5 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

Google has uploaded a copy of this contest on Kaggle where your solution can be judged. Only question D was uploaded however.

I have produced a solution that is very close to its theoretical maximum, with a reasonable runtime. - https://www.kaggle.com/huikang/441k-in-11-mins

I have also analysed the data for question D. https://www.kaggle.com/huikang/hc-2019q-eda-and-baseline-soln

More comments are available on the notebook themselves. Have fun!