chokudai's blog

By chokudai, history, 21 month(s) ago, In English

We will hold AtCoder Beginner Contest 259.

The point values will be 100-200-300-400-500-500-600-600. We are looking forward to your participation!

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

| Write comment?
»
21 month(s) ago, # |
  Vote: I like it -6 Vote: I do not like it

Loved problem D (^-^)

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    I did it by making a graph of connected circles and applying DFS on it , to know whether the two nodes (circles) were connected or not , i think it was not the intented approach (or may be it was), i am curious to know what was your approach towards the problem ?

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      My approach was also the same! Maybe someone else can share their different approach

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it -28 Vote: I do not like it

      Union-Find-Set and $$$\mathcal O(n^2)$$$ to get if any of the two circles are connected.

      You can see the two points as two circles which $$$r = 0$$$.

»
21 month(s) ago, # |
  Vote: I like it +78 Vote: I do not like it

Honestly, that A and B where worst problems I ever had on atcoder. Abc is supposed to be constest for beginner partitipants, not beginner problem setters.

I am disapointed because quality of atcoder contests was very good before.

»
21 month(s) ago, # |
  Vote: I like it +89 Vote: I do not like it

I would recommend whoever wrote B to consider never problemsetting again.

E and F were fun though.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    Why do people dislike geometry problems? Problem B can be solved by a simple use of https://en.wikipedia.org/wiki/Rotation_matrix and this is something that many people are expected to be familiar with.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Since when?

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +7 Vote: I do not like it

        Since 3D accelerators became a part of every computer. Anyone who tried to play with programming 3D graphics, learned about transformation matrices as one of the first things. Not to mention that every math/physics/cs university student probably has linear algebra in their curriculum.

        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it +32 Vote: I do not like it

          It's intended as a beginner contest, and I would argue more high schoolers take ABCs than not. I think you're probably in the minority on the 3D graphics too.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you help me find out what's wrong with my code? Thanks a lot.

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Judge Result shows that your solution gives WA on sample-input-3. Maybe when a=b=0, you will get l=0, and denominator=0 will lead to wrong answers.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +26 Vote: I do not like it

      The problem ask to receite or google a formular. This is kind of the lowest class of quality a problem can be categroized. It does not make a difference how difficult or simple that formular is.

»
21 month(s) ago, # |
  Vote: I like it +31 Vote: I do not like it

Found problem B harder than E. Maybe I need to pickup my high school mathsbook again.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain your approach for E please ?

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Lets consider the lcm of all numbers initially. We know that lcm is the maximum count of each prime among all the numbers. So we can store the maximum count of each prime in a map. The lcm will change only if the ai has a prime with its count equal to maximum count of same prime and no other ai has the same prime with the maximum count. We could do so by storing count of ai that have their count of that prime equal to maximum count. Lastly we need to check whether the lcm of the whole array is possible or not after performing any operation, we could do so by checking if for any ai there is no prime which has unique maximum count or we could just check if answer is less than n and than we could simply add 1 to our answer.

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        I did something similar but couldn't understand last part of your explanation can you provide me feedback on below here was my approach (obv wrong).

        • Maintain a vector of power of each prime and sort , so we know which number(s) in the input have this maximum power of prime. If there are two number with max power of considered prime our lcm won't change ever since there would always be one of the two numbers present. This needs to be checked across all primes for a given number.

        • If the above doesn't hold then a number has one or more primes with max power and removal of this number should change the lcm so add 1 to the answer there.

        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          Yeah so it maybe possible that the lcm wont change for a possible operation so we need to add 1 to our final answer for it, so we see that if the answer is n then every operation changed the lcm else if answer < n then there exists atleast 1 index for which our lcm won't change so we could just increment 1 to our answer.

»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

A: Statement is so hard to understand. Bruh

B: Why is this a problem???

C: Decent

D: Repeated problem but now with gEomeTRy

TLDR: This is actually WaCoder. The first half of problemset is shit

»
21 month(s) ago, # |
Rev. 4   Vote: I like it -32 Vote: I do not like it

I used bfs but 6 testcase are failing is it due to overflow im not getting idea?? Plzz help

Spoiler
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    maybe try using x*x instead of pow(x,2).

    I've had problems with that before.

»
21 month(s) ago, # |
  Vote: I like it +11 Vote: I do not like it

problem E can solved with divide and conquer + hashing. code

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you describe your solution a bit so its easier to go through the code ?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What is the expected solution?

    I solved it by marking each number if it has one of the most frequent e[i] values, but do not understand the editorial.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I tried using Multiset To store the current maximums before and after deletion and re-insertion of elements, but it seems that using a triple Hash did TLE, and got WA on one of the tests even, i tried double Hash and Got nowhere either, codes (1,2)

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      I submitted it using multisets and double hashes. Here is my code click.

»
21 month(s) ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In editorial of problem G:

Spoiler!!!

Shouldn't it be?:

Another Spoiler!!!

Also, I don't really understand why solution works :(

To be more precise, I don't understand why do we add edge from:

Same Spoiler!!!
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    It's problem G I think?

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah, sorry!

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        It's because in the problem statement, if the value of the intersection square of the two peoples' choices is less than 0, a very large penalty is added, so we cannot let them choose this intersection point. In the graph, cutting an edge corresponds to choosing an intersection square, and setting its capacity to infinity in a minimum cut ensures that it will never be cut(chosen).

        Also yeah I think they messed up the ordering on C and R.

        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          But why is it true that if $$$C_j$$$ and $$$R_i$$$ are both chosen, we'll always need to cut this edge with weight $$$inf$$$?

          • »
            »
            »
            »
            »
            »
            21 month(s) ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            If they are both chosen and we do not cut this edge, there will be a complete path from $$$S$$$ to $$$T$$$. Choosing $$$R_i$$$ means that there is a complete path from $$$S$$$ to $$$R_i$$$, but not from $$$R_i$$$ to $$$T$$$. The similar is true for $$$C_j$$$.

            • »
              »
              »
              »
              »
              »
              »
              21 month(s) ago, # ^ |
              Rev. 3   Vote: I like it 0 Vote: I do not like it

              okay, if there is a path from $$$S$$$ to $$$R_i$$$, also there's a path from $$$C_j$$$ to $$$T$$$, and also there's an edge from $$$C_j$$$ to $$$R_i$$$, why does it mean that there will be a path from $$$S$$$ to $$$T$$$? I'm very sorry for being stupid, but I really don't understand :(

              • »
                »
                »
                »
                »
                »
                »
                »
                21 month(s) ago, # ^ |
                Rev. 3   Vote: I like it 0 Vote: I do not like it

                I believe they fixed the editorial to " $$$R_i$$$ to $$$C_j$$$ " already.

                Edit: Oh they didn't, but just look at brunovsky's comment.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  21 month(s) ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  But author's code says otherwise:

                  g.add_edge(h+j, i, inf)

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  21 month(s) ago, # ^ |
                    Vote: I like it +8 Vote: I do not like it

                  What in the world... And when I change the edge to $$$R_i$$$ to $$$C_j$$$, it got WA... Now I'm confused too...

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  21 month(s) ago, # ^ |
                    Vote: I like it +3 Vote: I do not like it

                  My friend helped me to understand the author's solution. Actually, we take a row to the answer, if it's connected with T in the cut.(then we delete absolute sum of negative elemets) And we take a column to the answer if it's with S in the cut (also we delete absolute sum of negative elements)

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

                  Can u elaborate on this a little more bashkort, I am struggling to understand how this definition helps and how is it justified

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

                  I'll try to :)

                  In the beggining we added all positive elements to the answer. Then we want to create a graph, then find a minimum cut from $$$s$$$ to $$$t$$$ in this graph and subtract this value from the answer.

                  We will create graph as editorial says, and I'll show why this graph works.

                  So I say that we take some row $$$i$$$ to the answer if it is connected with $$$t$$$ in the minimum cut. Else if we don't take it, it will be connected with $$$s$$$ in the cut.

                  Also we take some column $$$j$$$ to the answer if it's connected with $$$s$$$ in the cut. Else if we don't take it, it will be connected with $$$t$$$ in the cut.

                  So why does this work: If we take a row $$$i$$$ to the answer, so it won't be connected with $$$s$$$ in the answer $$$=>$$$ then we already added every positive element from that row in the very beggining, so now if we take it to the answer, we have to add negative values too (so now we have to cut edge from $$$s$$$ to $$$i$$$, because as I said "we take some row i to the answer if it is connected with t in the minimum cut"). So because of this we create edge with weight = sum of absolute values of negative elements in the row $$$i$$$.

                  This edge will go from $$$s$$$ to $$$i$$$, so if it's in the answer, we subtracted this edge, or didn't subtract otherwise.

                  You can apply pretty much the same logic for columns.

                  Now let's have a look at edges between rows and columns. If we took both row $$$i$$$ and column $$$j$$$, then there is a path from $$$i$$$ to $$$t$$$, and also there is a path from $$$s$$$ to $$$j$$$. Then if a[i][j] < 0, we have to cut edge from $$$j$$$ to $$$i$$$ with weight $$$inf$$$. It's pretty obvious that's it's not optimal.

                  If we did't take both of $$$i$$$ and $$$j$$$, then need to subtract the edge between $$$i$$$ and $$$j$$$, because otherwise there will be a path between $$$s$$$ and $$$t$$$.

                  I hope you understand now :D

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Should be $$$R_i\to C_j$$$ with capacity $$$a_{ij}$$$ if $$$a_{ij}\geq 0$$$ else $$$+\infty$$$. For more context, see image segmentation on wikipedia.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks! But why do we add edge with capacity $$$+∞$$$ from $$$C_j$$$ to $$$R_i$$$, but not from $$$R_i$$$ to $$$C_j$$$?

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it -10 Vote: I do not like it

        Because we connect $$$S$$$ with $$$R$$$ and $$$C$$$ with $$$T$$$. Otherwise, You can swap the order but you must guarantee that the connected ways are flowing from $$$S$$$ to $$$T$$$.

        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Author's code says that we add edge from $$$C_j$$$ to $$$R_i$$$

          Then, if there is a path from $$$S$$$ to $$$R_i$$$, also there's a path from $$$C_j$$$ to $$$T$$$, and also there's an edge from $$$C_j$$$ to $$$R_i$$$, why does it mean that there will be a path from $$$S$$$ to $$$T$$$?

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        Ok it appears the construction in the editorial is a bit different from the usual segmentation setup. The later is probably easier to understand — see the submissions of those on top of the leaderboard.

        Here's my interpretation (see the article on wikipedia):

        • We earn $$$r_i=\sum_{j}a_{ij}$$$ if we assign row $$$i$$$ to the foreground, $$$0$$$ to the background.
        • We earn $$$c_j=\sum_{i}a_{ij}$$$ if we assign col $$$j$$$ to the background, $$$0$$$ to the foreground.
        • We pay $$$b_{ij}$$$ if we assign row $$$i$$$ to foreground and col $$$j$$$ to background, where $$$b_{ij}=a_{ij}$$$ if $$$a_{ij}\geq 0$$$ else $$$b_{ij}=\infty$$$ to prevent this altogether. This adds an edge from row $$$i$$$ to col $$$j$$$.

        Now we can build the standard segmentation graph and not think about this any further, but consider some row $$$i$$$. This would add either edge $$$s\to i$$$ with capacity $$$r_i$$$ if $$$r_i>0$$$ or edge $$$i\to t$$$ with capacity $$$-r_i$$$ if $$$r_i<0$$$. But in the second case the edge is completely useless ($$$r$$$ has no other incoming edges) so you may as well ignore it. Similarly for cols.

        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks!

        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          how do you model the flow graph if the $$$a_{i,j} < 0$$$ pay $$$10^{100}$$$ condition wasn't there, the condition seems very convenient as to setup the graph such that you don't double counting some cells

»
21 month(s) ago, # |
Rev. 2   Vote: I like it -63 Vote: I do not like it

Sorry but according to this post in Chinese(You don't have to understand Chinese but just see the code), GREEDY ALGORITHM can pass problem G, and there's just a hack data below.

Well if you can't see the code and the hack data, here I will copy it :

int main() {
    qread(n, m);
    rep(i, 1, n) rep(j, 1, m) qread(a[i][j]);

    rep(i, 1, n) {
        ll sum = 0;
        rep(j, 1, m) sum += a[i][j];
        if(sum > 0) ans1 += sum, v[i] = 1; 
    }
    rep(i, 1, m) {
        ll sum = 0;
        rep(j, 1, n) if(v[j] && a[j][i] < 0) {
            sum = -1;
            break;
        }
        else if(!v[j]) sum += a[j][i];
        if(sum > 0) ans1 += sum;
    }

    memset(v, 0, sizeof v);

    rep(j, 1, m) {
        ll sum = 0;
        rep(i, 1, n) sum += a[i][j];
        if(sum > 0) ans2 += sum, v[j] = 1; 
    }
    rep(i, 1, n) {
        ll sum = 0;
        rep(j, 1, m) if(v[j] && a[i][j] < 0) {
            sum = -1;
            break;
        }
        else if(!v[j]) sum += a[i][j];
        if(sum > 0) ans2 += sum;
    }

    cout << max(ans1, ans2) << '\n';
    return 0;
}
4 4
-1 -1 100 100
-1 100 100 100
100 100 -1000 -1000
100 100 -1000 -1000
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it -61 Vote: I do not like it

    Also, great thanks to the Sample 2 in problem D cause that reminds me if one circle is inside the other.

»
21 month(s) ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

Out of all problems from A to E, I think only C,D were Decent

»
21 month(s) ago, # |
  Vote: I like it +16 Vote: I do not like it

For problem F, my first idea is based on greedy algorithm (inspired by Kruskal's algorithm), i.e., sort edges in decreasing order of weight, and choose from large ones to small ones as long as the "rule of degree" is not broken. But, I really wonder why this does not work? What are the counter-examples?

By the way (I am sorry that this is off topic), I find KrK in the standings!!! I am sorry to disturb you here, but you are really a legend!! During past years, I kept practicing by virtual participation in codeforces, and I usually saw you in standings, and witness your persistence and improvement. Early codeforces rounds usually do not have detailed tutorials, and it is difficult for me to understand for most of the time. During that tough period, I learned a lot by reading your solutions. The codes are clean, simple, and it helps me understand the idea behind the solution quite a lot. I am very glad to attend a true contest with you this time.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Consider 1 — 2 — 3 — 4, with weights $$$2$$$, $$$3$$$, $$$2$$$ in order and $$$d_i=1$$$ for every $$$i$$$.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Wow, thank you so much for your simple counter-examples!

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Thank you for your nice words, SummerSky! :) I am glad to hear that following me has helped you to learn. I wish you all the best with competitive progamming!

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Thank you so much for your encouragement, and giving me motivation!! I will try my best to keep up learning and practicing!

»
21 month(s) ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Can anyone give me any test case for problem C that fails in my submission. My approach seems similar to the official editorial.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    You have declared cnt as a character variable in your function.

»
21 month(s) ago, # |
  Vote: I like it +11 Vote: I do not like it

This contest made me learn new functions like sqrtl, cosl, sinf, tan2 and other due to lack of accuracy. I've never had so many WAs during contests. Hope there will be less such problems, or at least not at that positions.

»
21 month(s) ago, # |
  Vote: I like it +7 Vote: I do not like it

Solving today's contest reminded me of my JEE days :)

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Typo?

1. ca*m* be chosen at most d_v times. 

Editorial of F, Line 13

plz fix it thx :)