Блог пользователя backo

Автор backo, история, 8 лет назад, По-английски

Hello everyone!

Here we go again.. writing a solution to a problem which supposedly works on my PC but delivers runtime error on the codeforces server.

The submission I'm talking about is this: 19567131. I've been reading about suffix trees and trying to solve a simple problem. The solution is pretty lengthy, but... Does anyone know what error code 255 is? I also tried custom tests and occasionally I get error code -1073741819. I compile under gcc 5.1.0 — the same as codeforces I think, using c++11. I tried using flags "-std=c++11 -Wextra -pedantic -Wall -O2" but didn't get anything interesting. I've been playing around with this for quite a while now, but I can't seem to get it to work.

I'd be grateful for any help anyone can provide!

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор backo, история, 8 лет назад, По-английски

Hello, recently I've come across a problem (not a competition task) and I'm wondering if there is an efficient solution to it. The task follows:

Given a structure like this [ (2,3), (1), (2,3,4) ] you can easily construct all possible combinations: (2,1,2),(2,1,3),(2,1,4),(3,1,2),(3,1,3),(3,1,4)

Now if you're given n tuples of length m, you need to group them in a way that minimizes the ammount of structures that you get as a result.

E.G. n=7,m=3 tuples: (5,3,10),(4,3,2),(0,4,7),(1,4,7),(5,3,2),(4,3,10),(5,2,9) can form groups [ (5,4),(3),(2,10) ], [ (5),(2),(9) ] and [ (0,1),(4),(7) ]

It kind of smells like set cover problem or something like that but I'm not sure.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

Автор backo, история, 9 лет назад, По-английски

Hello,

can anyone tell me how can I see how many people in a certain DIV2 contest are competing out-of-competition? Or how many people are actually in the competition?

For example when the contest ends, you get a final rank which I assume is your rank among other contestants who are NOT out-of-competition. But when you go in the contest final standings, people from DIV1 are there as well and the number of participants that's showed is also DIV1 included I think.

If this is not possible, it should be added because it's interesting to see how good you did against other DIV2 users (e.g. top 30% or whatever)

Полный текст и комментарии »

  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится

Автор backo, история, 9 лет назад, По-английски

Hello!

Can anyone tell me how to update my g++ compiler for C++ to the exact version that's used by the judge on codeforces? I'm using Windows 7 and I'm not using any IDE (i compile from the commandline). Currently I have g++ version 4.8.1 and I can't find where to download 5.1.0. Tried to download minGW but it keeps installing the old 4.8.1 version.

Before, I didn't care that the compiler versions didn't match, but this last competition (330 div 2) got me really pissed off. I figured out the solution to the B problem, but I kept getting WA on pretests. After the contest, I tried submitting the solution and I saw that my solution was giving the wrong answer on their machine, while I was getting the corrent answer on my PC. After some tweaking I figured it was the pow() function that was causing the trouble. After i manually calculated 10^k instead of calling pow(10,k), I got accepted.

This thing with different compiler versions is REALLY annoying and unpredictable because god knows how many more functions like pow() work differently on different compiler versions.

Also, what are the compiler options (like -Wall) used by the judge?

Thanks

Полный текст и комментарии »

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

Автор backo, история, 9 лет назад, По-английски

Hello everyone!

I've recently come across a problem and I can't seem to find an efficient solution. I didn't know what to title this post because I don't know which group of problems does it belong to (dp,greedy,...). The problem is as follows:

You're given a set of distinct values {a1,a2,a3,...,ak} (1<=k<=3*10^5). Lets denote this A.

Also, you're given an array of "slots" of size 10^5. For each slot, you're given a subset of A.

You have to place a value from set A in each of the slots such that value in each slot has to be from its subset. (The subset is a constraint on which elements can go inside). Different slots can have same values stored in them (and it is encouraged to do so)

Now you have to fill all slots BUT minimizing the ammount of distinct values from A used.

I don't know if I've been clear on this, so let's consider this simple example:

A = { 1,2,3 }

constraints (3 slots): (1,2) (1,3) (1,2)

Answer: You're going to fill the slots (1,1,1), thus using minimum number of distinct values from A (only 1). An alternate solution could be (1,3,2) but this uses 3 elements from A and thus it is not optimal. Filling (3,3,2) is not a valid solution because 3 cannot go into the first slot (because of the constraint).

This is actually a subproblem of a larger problem I've been trying to solve, and it might mean I have to take a different approach to solving the original problem in order to avoid solving this one. However, I think this is an interesting problem as is so I think it will be useful for many of you on this site if a solution is given.

Thanks in advance!

Backo.

p.s. If you want, I can post a link to the original problem (it's graph-related)

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится