ko_osaga's blog

...And another boring OI solving stream
By ko_osaga, history, 6 years ago, In English

To jump on a bandwagon, I'll run a boring stream, where I'll virtual participate JOI Spring Camp 2019 Day2 (or Day1 if that's harder). The time will be 3/21 Thursday 7:30 PM UTC+9 (KST)

https://www.twitch.tv/koosaga

If this works out well, I'll maybe continue streaming after WF. I'll try to solve problems that is both hard and annoying, something like this.

See you!

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

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

How to write these contests virtual, not at 1:00 (UTC)?

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

    I assumed they will hold an analysis session. If they don't, I'll just solve other hard JOI problems instead.

    → Reply
»
6 years ago, # |
  Vote: I like it -65 Vote: I do not like it

Please [ subscribe & follow & like ] wookje tv (^-^)

https://twitch.tv/wookje

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

    WoW woookje tv is very fun! I won't miss the live broadcast!

    → Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Still no 100pt solution for that one problem from IOI 2003...

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

    lol is it even possible to score > 88

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

      That's what I'd like to know. After all, it's strange that there would be a problem without a 100pt solution. Spoiler alert: the only official(ish?) solution I found describes something that seems to score 88.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 2   Vote: I like it +45 Vote: I do not like it

        I don't think it's possible in 5 hours, but overall it's possible... I was given the task about 1-2 years ago, and gave it 2 weeks, after which I got 100.

        I also lost the source code (this is the only thing I have left), but if you want to challenge me to rewrite it (maybe given a judge?) then sure.

        I barely remember the idea, but it doesn't give away the solution;

        • Try to maintain values to print, but don't print necessarily right away.
        • You can reorder elements (not necessarily an increasing sequence) for easier implementation.

        Edit: Well apparently I have some source code that is incomplete, and some of the output files for some inputs. This is one of them, solving n=255 using upto 4 consecutive S operations at any time. I think this expresses all that's necessary to solve for fullscore.

        Specifically, the bounds I kind of remember are:

        8, 44, (I think 97 or 101), (I think 137 or 173), 257.

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

          The judge is Yandex IOI archive.

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

            Done :) (you can view in the standings)

            The first time I solved the problem I wrote a lot of case analysis to do the best thing I found on paper. This time I tried to write something more general, which was able to solve with 1 operation upto 44, 2 operations upto 101 and 4 operations upto 257. For some reason it bugs for 3 operations (bound should be around 180-190 I think), but I tried submitting without it (solving either with 1,2,4). Jury's answers are weak enough to let this pass with 99 points, and then I had to improve just n=112 so I did the stupid thing that solves in 8 + 36T for some limit T.

            tl;dr: My code is not general, just solves whatever is good enough for the jury. I couldn't bother fixing it, as it was unnecessary (my general solution improves jury's answers for tests 12,13).

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

              Wow, good job! I really thought it was impossible, now I know that I can improve my total score in that IOI archive and that it makes for a good challenge to others.

              → Reply
»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Pretty please, just use Science & Technology category!

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow, it's super fun. Maybe you guys can compete for writing annoying problems.

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

    Well, everyone can have their guilty pleasures...

    But I have the criteria. I don't like long and annoying problems (or cheats by compressing with formulas). Good annoying problems should have a short or motivating statement, and knowing it's annoyingness should be nontrivial, or quite hard. I'm not sure my examples are "good" in that sense, though.

    → Reply
»
6 years ago, # |
  Vote: I like it -16 Vote: I do not like it

Hi, i'm having a question:

Assume we've done kruskal algorithm on a list of edges of a connected graph. Then can we check if an edge were in the minimum spanning tree in O(1) with disjoint set we've created? Assume that checking edges exist in edge list.

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

    Use set/unordered_set.

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

      Thank you. Using set/map may be the only way to do it.

      → Reply
»
6 years ago, # |
  Vote: I like it -30 Vote: I do not like it

if you yourself know it's boring and useless don't waste both our and your time. what's so hard

→ Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Starts in 30 minutes!

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

13/10/100 :( See you next time!

→ Reply